Week 11: Exercises

1. foldl1 and foldr1

foldl1 and foldr1 are versions of foldl and foldr that take no accumulator argument: they simply apply a binary operator to all elements in a list. They cannot be applied to empty lists. For example,

foldl1 (+) [1, 2, 3] == 6
foldr1 (+) [1, 2, 3] == 6

1. What are the types of foldl1 and foldr1?

2. Write these functions.

2. Integers with Infinity

1. Write a data type IntX that represents an integer, positive infinity, or negative infinity. Write functions less and greater on this type.

2. Generalize IntX to work with any appropriate base type, not just integers.

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

4. Tree Values

Write a function that takes a binary search tree and returns a list of all its values in order. Your function should run in time O(N), where N is the number of nodes in the tree.

5. Tree Fold

1. Write a function treeFoldr that performs a right fold of a function over the values in a binary tree.

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

6. Balance Test

Define a balanced tree as follows: for any node, the number of nodes in the left and right subtrees differ by at most 1.

Write a function isBalanced that determines whether a tree is balanced.

7. Arithmetic Expressions

1. Write a Haskell datatype that can represent arithmetic expressions composed from integers, variables, and the operators +, - and *.

2. Write a function eval that takes an environment, which is an assocation list mapping variables to values, plus an expression. The function should evaluate the expression in the given environment and return its value.