# TallCat Webpage of the Compositional Systems and Methods group at TalTech.

# Functional Programming Exercise Session 6

The idea of this exercise set is to give you lots of things to write using the fold functions for datatypes we have seen in class. Recall:

``````foldNat : b -> (b -> b) -> Nat -> b
foldNat z s Z = z
foldNat z s (S n) = s (foldNat z s n)

foldList : (a -> b -> b) -> b -> List a -> b
foldList = foldr

data Tree : Type -> Type where
Leaf : Tree a
Node : Tree a -> a -> Tree a -> Tree a

foldTree : b -> (b -> a -> b -> b) -> Tree a -> b
foldTree l n Leaf = l
foldTree l n (Node tl x tr) = n (foldTree l n tl) x (foldTree l n tr)
``````

You should try to use these folds to solve the exercises. Note that it is often easier to write a solution that does not use a fold first, and then try again once you understand how to do it without one.

1. (<– this should say “0”!) Write functions
``````andList : List Bool -> Bool
orList  : List Bool -> Bool
``````

such that `(andList xs)` is `True` if and only if each element of `xs` is `True` and, dually, `(orList xs)` is `False` if and only if each element of `xs` is `False`.

Now, write functions

``````multList : List Nat -> Nat
addList  : List Nat -> Nat
``````

such that `(multList xs)` is the result of multiplying all the elements of `xs` together, and `(addList xs)` is the result of adding all the elements of `xs` together.

Do your answers to parts a and b suggest a relatoinship between logical conjunction / disjunctoin and arithmetic product / sum? What is the connection?

1. Write a function
``````exp : Nat -> Nat -> Nat
``````

such that `(exp a b)` is `a ^ b`, that is, `a` to the power of `b`.

2. Write a function
``````flatten : List (List a) -> List a
``````

such that, for example

`````` > flatten [[1,2,3],[],[4,5]]
> [1,2,3,4,5]
``````
3. Write the `filter` function
``````filter : (a -> Bool) -> List a -> List a
``````

The idea is that `(filter p xs)` is the list consisting of those elements of `xs` such that `p xs` is `True`, in the same order they occured in `xs`. For example

`````` > filter (<=5) [7,1,6,3,1,4]
> [1,3,1,4]
``````
4. Write a function
``````reverseTree : Tree a -> Tree a
``````

that reverses a tree in the following sense: (tilt head 45 degrees to the left to read trees)

``````4--5                      4--2--1
|                         |  |
2--3  |---reverseTree-->  5  3
|
1
``````
5. Write functions
``````andTree  : Tree Bool -> Bool
orTree   : Tree Bool -> Bool
addTree  : Tree Nat -> Tree Nat
multTree : Tree Nat -> Tree Nat
``````

that do for `Tree`s what the functions you wrote in part 1 did for lists.

6. Implement the in-order, pre-order, and post-order traversals for trees (using a fold):
``````in-order   : Tree a -> List a
pre-order  : Tree a -> List a
post-order : Tree a -> List a
``````
7. Write a function
``````beadthFirst : Tree a -> List a
``````

that returns the breadth-first traversal of the input tree.

That’s the end of the exercise set, but remember that you should try to do all of these using folds!