Week 9: Exercises

1. Mapping and Filtering

Recall the signatures of the built-in functions map and filter :

map :: (a -> b) -> [a] -> [b]
filter :: (a -> Bool) -> [a] -> [a]

Write these functions using foldl and/or foldr.

2. takeWhile

takeWhile returns the longest prefix of elements that satisfy a predicate:

> takeWhile (\i -> i * i < 30) [1 ..]
[1,2,3,4,5]

What is the type of takeWhile?
Write takeWhile recursively.
Write takeWhile using foldr.

3. Folding Minus

What are the values of these expressions?

foldl (-) 0[1,2,3]
foldr (-) 0[1,2,3]

4. Tree Values

Consider this definition of a binary tree:

data Tree a = Nil | Node (Tree a) a (Tree a)

Write a function treeVals that takes a binary search tree and returns a list of all its values in order:

treeVals :: Ord a => Tree a -> [a]

How efficient is your function?

5. Valid Search Tree

Write a function isSearchTree that determines whether a binary tree is a valid binary search tree. Assume that duplicate values are not allowed in the tree.

6. Tree Fold

Write a function treeFoldr that performs a right fold of a function over the values in a binary tree:
```
treeFoldr :: (b -> a -> a) -> a -> Tree b -> a
```
Use treeFoldr to write functions that
- add all the values in a binary tree of numbers;
- generate a list containing all the values in a binary tree

7. Algebraic Expressions

a) Design a data type Exp that can represent any arithmetic expression involving integer constants, named variables, and the +, - and * operators. Such expressions include

(x + y) * (x – y)
z * (z – 2)
14
0 + (1 + (2 + 3))

b) Write a function eval :: Exp -> [(String, Int)] -> Int that evaluates an expression given an environment, which is an association list that holds the variables of the variables in the expression.

8. Infix Expressions

Write a function parse :: String -> Exp that can parse an expression written in prefix notation, such as

* + x y - x y
* z - z 2
14
+ 0 + 1 + 2 3

You may assume that (as in the examples above) all input tokens are separated by spaces.

9. Simplifying Expressions

Write a function simplify :: Exp -> Exp that simplifies an expression by combining constants wherever possible, and by eliminating additions/subtractions with 0 or multiplications with 1.

For example, 0 + (x + (2 + 3)) should simplify to x + 5.

10. Lists

Pretend that Haskell does not have a built-in list type.

a) Implement lists using an abstract data type DList a. Comparison operators (e.g. ==, /=, >, <) should work on your class and should compare lists lexicographically.

b) Write a function that computes the sum of all values in a DList Int.

c) Write a function that performs a right fold over a DList a.

11. Natural Numbers

Pretend that Haskell does not have the built-in types Int and Integer.

a) Implement natural numbers (i.e. non-negative integers) using an abstract data type Nat. Comparison operators (e.g. ==, /=, >, <) should work correctly on your class.

b) Implement an addition function add :: Nat -> Nat -> Nat.

c) Implement a multiplication function mul :: Nat -> Nat -> Nat.

12. Pythagorean Triples

Write a function triples that takes an integer N and returns a list of integer triples (a, b, c) with 0 < a < b < c ≤ N such that a² + b² = c². If two triples are multiples of each other (e.g. (3, 4, 5) and (6, 8, 10)), only the smaller of them (e.g. (3, 4, 5)) should appear in the list.

> triples 15

[(3,4,5),(5,12,13)]

13. Words

Write a function words :: String → [String] that breaks a string into words. For the purposes of this exercise, a word is any sequence of characters that are not spaces. Words may be separated by any number of spaces.