# A new list type

### From HaskellWiki

Does anybody find this amusing?

module XList where import Prelude hiding (length, head, tail, foldr, foldl, map, zip, zipWith, replicate) data List t = Node {length_ :: Int, head :: t, tail :: List t} | End deriving (Eq, Show) length End = 0 length n = length_ n infixr 5 #: x #: xs = Node (1 + length xs) x xs foldr _ v (End) = v foldr f v (Node _ x xs) = f x (foldr f v xs) foldl _ v (End) = v foldl f v (Node _ x xs) = foldl f (v `f` x) xs foldl' _ v (End) = v foldl' f v (Node _ x xs) = (foldl' f $! v `f` x) xs map _ (End) = End map f (Node n x xs) = Node n (f x) (map f xs) zipWith f (End) _ = End zipWith f _ (End) = End zipWith f (Node n0 x xs) (Node n1 y ys) = Node (n0 `min` n1) (f x y) (zipWith f xs ys) zip = zipWith (\x y -> (x,y)) join (End) ys = ys join (Node n x xs) ys = Node (n + length ys) x (join xs ys) merge = foldr join End select _ End = End select f (Node n x xs) = case f x of True -> x #: select f xs False -> select f xs replicate 0 _ = End replicate n x = Node n x (replicate (n-1) x)

Somebody (a non Haskeller) said that having to traverse a potentially large linked list merely to compute its size is unnecessarily wasteful. Whether or not you agree with that statement, the above (which is obviously incomplete) is what I came up with to address this criticism. (You might argue that linked lists just plain aren't a good idea for very large structures.)

Of course, in the presence of lazy evaluation, all is not*quite*that simple. Functions that generate known-size lists (e.g.,

replicate

map

select

Prelude.filter

Anybody else have any insightful or amusing comments?

MathematicalOrchid 13:28, 14 February 2007 (UTC)

"*traversing a potentially large linked list merely to compute its size is unnecessarily wasteful.*"

length