[Haskell-cafe] lists of arbitrary depth

Chaddaï Fouché chaddai.fouche at gmail.com
Wed Jul 14 05:09:12 EDT 2010

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"


More information about the Haskell-Cafe mailing list