Personal tools

A new list type

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Just an interesting scribble.)
(Refer to Things to Avoid)

Revision as of 15:03, 14 February 2007

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.,
) can add size information as they build it. If
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
(which is equivalent to
, 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
. Although it probably requires quite a change of mindset for a non-Haskeller to appreciate that.