Skip to content

Latest commit

 

History

History
83 lines (59 loc) · 2.18 KB

16.md

File metadata and controls

83 lines (59 loc) · 2.18 KB
Raw

Recursive types

List is a recursive type. This means that at least one of the data constructors have a field with its own type. In the case of list it is the second operand of (:).

Working with recursive types

One way of working with recursive data types is to use recursive functions. Let's have a look at examples with the built in List type.

myLast :: [a] -> Maybe a
myLast [] = Nothing
myLast (x:[]) = Just x
myLast (x:xs) = myLast xs

The last element of an empty list does not exist. In the second line we pattern match on the cons constructor if the tail is an empty list. This means that the last element is x, so we return with it. The last line can only match if the list is not empty and the tail (xs) is not an empty list. In this case we ask for the last element of tail.

Exercise

  • Write a function that picks the second last element of a list. (Hint: Try to use consecutive (:) constructors in one pattern.)

Binary tree

Binary trees can be defined in Haskell like this:

data BinaryTree a = Node {elem :: a, left :: BinaryTree a, right :: BinaryTree a}
                  | Nil
                  deriving (Eq, Show)

Exercise

  • Create the following binary tree value.
exampleTree = Node 5 (Node 2 Nil Nil) (Node 10 (Node 7 Nil Nil) (Node 15 Nil Nil))
  • Implement the following functions:
inOrder :: BinaryTree a -> [a]
inOrder exampleTree == [2, 5, 7, 10, 15]

preOrder :: BinaryTree a -> [a]
preOrder exampleTree == [5, 2, 10, 7, 15]

postOrder :: BinaryTree a -> [a]
postOrder exmpleTree == [2, 7, 15, 10, 5]

Extra homework

If you are bored, you can solve the following exercise. Although this might take more time to finish.

Rose tree or multi-way tree is another example of recursive types.

Create RoseTree.hs with the following content.

data RoseTree a = RoseTree a [RoseTree a] deriving (Show, Eq)
  • Create the following tree.
exampleTree = RoseTree 10 [RoseTree 1 [],RoseTree 2 [RoseTree 12 []],RoseTree 3 []]
  • Implement the following function.
traverseRose :: RoseTree a -> [a]
(traverseRose exampleTree) == [1, 12, 2, 3, 10]