Search
Exercise 1: Define a type representing binary trees storing data in leaves of a general type a. Each non-leaf node has always two children. Make your type an instance of the class Show so that it can be displayed in an XML-like format. A leaf node containing a datum x should be displayed as <Leaf x/> and an inner node <Node>…children nodes…</Node>. E.g. the following tree
a
Show
x
<Leaf x/>
<Node>…children nodes…</Node>
* / \ * 'd' / \ 'a' * / \ 'b' 'c'
<Node><Node><Leaf 'a'/><Node><Leaf 'b'/><Leaf 'c'/></Node></Node><Leaf 'd'/></Node>
Solution: We will declare a recursive parametric data type Tree a over a general type a. There will be two data constructors Leaf and Node. The leaf contains a datum of type a and the node has a left subtree and a right subtree.
Tree a
Leaf
Node
data Tree a = Leaf a | Node (Tree a) (Tree a)
To make Tree a an instance of the Show class. We have to constrain type a to be an instance of Show otherwise it would not be clear how to display the data stored in the tree. The definition of the function show is then straightforward.
show
Code
instance (Show a) => Show (Tree a) where show (Leaf x) = "<Leaf " ++ show x ++ "/>" show (Node left right) = "<Node>" ++ show left ++ show right ++ "</Node>"
Now we can define the tree from the above picture as
tree :: Tree Char tree = Node (Node (Leaf 'a') (Node (Leaf 'b') (Leaf 'c'))) (Leaf 'd')
Exercise 2: Consider the Tree a data type from the previous exercise. Write a function
treeDepth :: Tree a -> Int
Solution: The tree depth can be computed recursively as $treeDepth(t) = 1$ if $t$ is a leaf and $treeDepth(t)=1+\max(treeDepth(left),treeDepth(right))$ if $t$ has two subtrees $left$ and $right$. This is a recursive definition which can be directly rewritten into Haskell as follows:
treeDepth :: Tree a -> Int treeDepth (Leaf _) = 1 treeDepth (Node left right) = 1 + max (treeDepth left) (treeDepth right)
For the tree from the previous exercise we have
> treeDepth tree 4
Exercise 3: Consider again the Tree a data type from Exercise 1. Write a function
labelTree :: Tree a -> Tree (a, Int)
(x,n)
* * / \ / \ * 'd' * ('d',3) / \ => / \ 'a' * ('a',0) * / \ / \ 'b' 'c' ('b',1) ('c',2)
Solution: To traverse through the nodes (in particular leaves) can be easily done recursively. The problem is with the counter for labels. In an imperative programming language, we could introduce a variable counter and initialize it by 0. Once we would encounter a leaf, we would label it by counter and modify counter = counter + 1. Unfortunately, we cannot do that in a purely functional language like Haskell.
counter
counter = counter + 1
We need an accumulator in the signature of the labeling function holding the counter value. So we could think of a helper function
labelHlp :: Tree a -> Int -> Tree (a, Int)
labelHlp :: Tree a -> Int -> (Tree (a, Int), Int)
labelHlp :: Tree a -> Int -> (Tree (a, Int), Int) labelHlp (Leaf x) n = (Leaf (x, n), n+1) labelHlp (Node left right) n = let (left', n') = labelHlp left n (right', n'') = labelHlp right n' in (Node left' right', n'')
Finally, we wrap the helper function in the definition of labelTree. This definition just set the counter value to 0, call the helper function and then project into the first component via the function fst.
labelTree
fst
labelTree :: Tree a -> Tree (a, Int) labelTree t = fst (labelHlp t 0)
Task 1: Define a recursive data type Polynomial a representing univariate polynomials with an indeterminate $x$ whose coefficients are of a general type a. The definition will have two data constructors. First, Null represents the zero polynomial. Second, Pol whose parameters are a monomial and recursively the rest of the polynomial. Monomial should be represented as pairs of type (a, Int) where the first component is the coefficient and the second is the exponent. E.g. (c,e) represents $cx^e$. You can define a new name for that type as follow:
Polynomial a
Null
Pol
(a, Int)
(c,e)
type Monomial a = (a, Int)
> Null 0 > Pol (3, 2) Null 3*x^2 > Pol (-2, 0) Null (-2) > Pol (-1, 0) (Pol (-2, 1) (Pol (1, 3) Null)) (-1) + (-2)*x^1 + 1*x^3
Hint: Make first a function
format :: (Show a, Ord a, Num a) => Monomial a -> String
x^0
format
Task 2: Write a function
getDegree :: Polynomial a -> Int