A new list type

From HaskellWiki

Current revision

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.)

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."

Remi

Agreed; trying to count the elements in an infinite list would be a Bad Idea. ;-)

This came up in a discussion of sorting algorithms. You might want to choose which algorithm to apply depending on how big the list is - but not much point doing that if it takes longer to figure out how big the list is then to just use the first algorithm to hand! (Note that a sorting algorithm can never work on an infinite list.)

For the special case of a sorting algorithm, it might be simpler to just count the size of the list once, and then manually manage that information throughout the sorting process. (Rather than, as above, defining a whole new datatype and redefining all of the prelude on it.)

I thought I would post it because it's an interesting idea though.

MathematicalOrchid 15:32, 14 February 2007 (UTC)

Category: Code