# A new list type

### From HaskellWiki

(Just an interesting scribble.) |
(True, true...) |
||

(One intermediate revision by one user not shown) | |||

Line 54: | Line 54: | ||

[[User:MathematicalOrchid|MathematicalOrchid]] 13:28, 14 February 2007 (UTC) | [[User:MathematicalOrchid|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 <hask>length</hask>. Although it probably requires quite a change of mindset for a non-Haskeller to appreciate that. | ||

+ | |||

+ | [[User:Remi|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. | ||

+ | |||

+ | [[User:MathematicalOrchid|MathematicalOrchid]] 15:32, 14 February 2007 (UTC) | ||

[[Category:Code]] | [[Category:Code]] |

## Latest revision as of 15:32, 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.,

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

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)