[Haskell-cafe] lists of arbitrary depth

[Chaddaï Fouché]

On Tue, Jul 13, 2010 at 11:28 AM, Shlomi Vaknin <shlomivaknin at gmail.com> wrote:
> Thank you Bob,
> your example clarified how actually using such data type would appear in
> haskell. I naively thought it would be as simple as defining a regular list,
> but i see it is slightly more strict than that. I appreciate your help!
> Vadali

Well it _is_ as simple as defining a regular list, which would be
(fictionally since (:) and [] are reserved identifiers) :

> data [] a = [] | a : [a]

Which is the same as :

> data List a = Empty | Cons a (List a)

You can then handle lists with pattern matching :

> map f [] = []
> map f (x:xs) = f x : map f xs

Or for our List type :

> map f Empty = Empty
> map f (Cons x xs) = Cons (f x) (map f xs)


His definition of a tree :

> data Tree a = Leaf | Branch a [Tree a]

follows the same idea and is as easy to handle with pattern matching :

> treeMap f Leaf = Leaf
> treeMap f (Branch x xs) = Branch (f x) (map (treeMap f) xs)


As you see, an user defined type is manipulated with the same
mechanism as a "primitive" type, this uniformity is part of the power
of Haskell in that it encourages users to create their types and
allows seamless integration of external library types with "primitive"
types.

-- 
Jedaï