Lecture 22-1

COMP105 Lectures 2020-11-30

Recursive Types

We have seen types which contain other types. In a recursive custom type, some constructors contain the type itself.

data IntList = Empty | Cons Int IntList deriving(Show)

Some examples using this type:

Empty -- []
Cons 1 (Empty) -- [1]
Cons 1 (Cons 2 Empty) -- [1,2]

Here is a more general list using a type variable:

data List a = Empty | Cons a (List a) deriving(show)

This is the same as the previous example but using any type (provided that it is the same type all the way through the list). To use this as an infix operator like : you would do the following:

> 1 `Cons` (2 `Cons` Empty)
Cons 1 (Cons 2 Empty)

Functions with Recursive Types

We can write functions for our custom list type:

our_head :: List a -> a

our_head Empty		= error "Empty list"
our_head (Cons x _)	= x

This takes the first item in our custom list type and prints it.

To get the tail you would use this function:

our_tail :: List a -> List a

our_tail Empty		= error "Empty list"
our_tail (Cons _ x)	= x

Recursing on Recursive Types

We can also write recursive functions to process our recursive types. This is exactly the same as recusing on a list:

our_sum :: List Int -> Int

our_sum Empty 		= 0
our_sum (Cons x xs) = x + our_sum xs

Custom Lists

Here is a new list type that can contain two different types.

data TwoList a b = TwoEmpty
				| ACons a (TwoList a b)
				| BCons b (TwoList a b)
					deriving(show)

This is the type when making a list that contains a Char and a Bool:

> :t 'a' `ACons`(False `BCons` TwoEmpty)
TwoList Char Bool

This is not the same as a list with tuples as the next item in the list can be of type a or type b not of both all the time. There is a cost also as you have to explicitly say if it is type a or type b.

Exercises

1.  ourElem :: Eq a => List a -> a -> Bool
    ourElem Empty _ = False
    ourElem (List x xs) y
        | x == y 	= True
        | otherwise = ourElem xs
   

2.  ourRange :: Int -> List Int
    ourRange 0 = Empty
    ourRange x = Cons x (ourRange (x - 1))
   

3.  data ThreeList a b c = ThreeEmpty
                         | ACons a (ThreeList a b c)
                         | ACons b (ThreeList a b c)
                         | ACons c (ThreeList a b c)
                         deriving(show)