Warning

This page is located in archive.
Go to the latest version of this course pages.

**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

* / \ * 'd' / \ 'a' * / \ 'b' 'c'is displayed as

<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.

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.

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 -> Inttaking a tree and returning its depth.

*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)labeling the leaves of a tree by consecutive natural numbers in the infix order. So it should replace a leaf datum

`x`

with the pair `(x,n)`

for some natural number. So we would like to obtain something like that:
* * / \ / \ * 'd' * ('d',3) / \ => / \ 'a' * ('a',0) * / \ / \ 'b' 'c' ('b',1) ('c',2)

The idea behind this function will be useful in your homework assignment. So try to understand it well.

*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.

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)taking as input the second argument representing the counter. Unfortunately, this is still not enough because such an accumulator can depend only on the path leading from the root node into a leaf. However, the accumulator has to depend on the previously labeled leaves. So we must enrich the output of the helper function as well so that we send the counter value back when returning from a recursive call. So we actually need to return not only the labeled tree but also the counter value as follows:

labelHlp :: Tree a -> Int -> (Tree (a, Int), Int)Now, when we encounter a leaf node, we label it by the counter accumulator and return a labeled leaf together with the increased counter value. For the non-leaf nodes, we first label the left subtree by the numbers starting with the counter value. This results in a labeled tree and a new counter value. Second, we label the right subtree with the numbers starting from the new counter value.

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 :: 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:

type Monomial a = (a, Int)Make your type an instance of show class. Polynomials should be displayed as follows:

> 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 -> Stringthat returns a string representing a given monomial. Note the constraint on the type

`a`

. We assume that coefficients are numeric values that can be added and subtracted and can be ordered. The reason for this is that we need to find out whether the given coefficient is negative and in that case, we have to wrap it into parentheses, i.e., we need to compare it with 0. Further, note that a constant monomial has no `x^0`

.
Then define the instance of `Show`

for `Polynomial a`

. You need to constrain the `show`

function
in the same way as `format`

.
**Task 2:** Write a function

getDegree :: Polynomial a -> Intreturning the degree of a given polynomial. The zero polynomial has degree $-1$ by definition. Otherwise, you have to find the highest exponent occurring in the polynomial.

courses/fup/tutorials/lab_9_-_haskell_types.txt · Last modified: 2022/04/08 12:14 by xhorcik