A new list type

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) can add size information as they build it. If map is applied to a list who's size is known, the size of the result is known. (Interestingly, if it isn't known, then presumably asking for the size of the result also computes and stores the size of the source list - if anybody still has it.) The really interesting case is select (which is equivalent to Prelude.filter, but with a less brain-dead name).

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." Especially when it's infinite. See Things to avoid for why you should try to avoid calling length. Although it probably requires quite a change of mindset for a non-Haskeller to appreciate that.

Remi