Real World Haskell

haskell, programming

Feb 15, 2018

Real World Haskell chapter 3 is about recursive data types, and includes an example of creating a list-like data structure.

data List a = Cons a (List a)
            | Nil
              deriving (Show)

fromList (x:xs) = Cons x (fromList xs)
fromList []     = Nil

It also has an example tree:

data Tree a = Node a (Tree a) (Tree a)
            | Empty
              deriving (Show)

Exercise 1:

Write the converse of fromList for the List type: a function that takes a List a and generates a [a].

toList (Cons a (b)) = a:toList b
toList Nil          = []

*Main> fromList [1..3]
Cons 1 (Cons 2 (Cons 3 Nil))
*Main> toList it
[1,2,3]

Exercise 2:

Define a tree type that has only one constructor, like our Java example. Instead of the Empty constructor, use the Maybe type to refer to a node’s children.

data Tree a = Node a (Maybe (Tree a)) (Maybe (Tree a))
              deriving (Show)

*Main> Node 1 (Just (Node 2 Nothing Nothing)) Nothing
Node 1 (Just (Node 2 Nothing Nothing)) Nothing