Webpage of the Compositional Systems and Methods group at TalTech.

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.

- (<– 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?

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

such that

`(exp a b)`

is`a ^ b`

, that is,`a`

to the power of`b`

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

such that, for example

`> flatten [[1,2,3],[],[4,5]] > [1,2,3,4,5]`

- 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]`

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

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

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