Introduction to Functional Programming – Exercises Week 6: "Recursive Data Types"TDA555 / DIT440, LP1 2017
Home | Schedule | Labs | Lectures | Exercises | Exam | About | FAQFire | WaitList | Group | TimeEdit | YouTube | Links
Introduction to Functional Programming – Exercises Week 6: "Recursive Data Types"TDA555 / DIT440, LP1 2017
Home | Schedule | Labs | Lectures | Exercises | Exam | About | FAQFire | WaitList | Group | TimeEdit | YouTube | Links
Here are some exercises designed to help you practice programming with data structures and higher-order functions.

Please prepare yourself for these exercises by printing them out, and also printing out the code samples and documentation that is referred to by links.

If you do not have time to do all these exercises, don't worry. The exercises are intended to provide enough work to keep the most experienced students busy. If you do all exercises marked with an (*) you have probably understood this week's material.

Good luck!

1 (*). Exercises from The Craft of Functional Programming


Take a look at the following datatype:

  data Expr = Num Int
            | Add Expr Expr
            | Mul Expr Expr

A. Define a function size :: Expr -> Int that counts the number of operators in an expression.

B. Add Sub (subtraction) and Div (integer division) to the datatype Expr and modify the functions eval, show, and size accordingly. What do you in eval when you divide by 0?

C. Implement one version of eval with the result type Maybe Int. (You return Nothing when division by 0 occurs somewhere in the expression.)

Integer Trees

Take a look at the following datatype:

  data Tree = Leaf Int
            | Split Tree Tree

D. Implement a function collapse :: Tree -> [Int] that returns all integers in a given tree as a list, in the same order as they occurred in the tree.

E. Implement a function mirror :: Tree -> Tree that mirrors a tree (i.e. swaps the left and right subtrees everywhere).

F. State a QuickCheck property that expresses what happens when a tree is mirrored twice.

G. State a QuickCheck property that expresses the relationship between mirror, collapse and reverse.

(In order to be able to test your properties, you have to make Tree an instance of Arbitrary.)

2 (*). Exercises on type Expr from the Lecture

(This exercise consists of writing QuickCheck properties, and checking them using QuickCheck. Define the properties in the groups exercises, but you can leave the QuickChecking of them until a later time, if you do not have access to a computer in your group room.)

Take a look at the datatype Expr for expressions with variables from the lecture: ExprVar.hs.

In the lecture, there was a function for differentiating expressions, called diff (Swedish: "derivat").

diff :: Expr -> Name -> Expr
diff (Num n)   x = Num 0
diff (Add a b) x = Add (diff a x) (diff b x)
diff (Mul a b) x = Add (Mul a (diff b x)) (Mul b (diff a x))
diff (Var y)   x
  | x == y       = Num 1
  | otherwise    = Num 0

A. Define a property that checks that, for each expression e, the derivative of e to x does not contain more variables than e.

Does the opposite hold also?

The result of the diff function often contains expressions that can be enormously simplified.

B.(*) Define a function simplify that, given an expression e, creates an expression that is equivalent to e, but simplified. Examples of simplifications you could do are:

  • 2+3 --> 5

  • 2*x+6+5*x+6 --> 7*x+12

  • 0*x+-2+5*y+3 --> 5*y+1
  • You can decide yourself how ambitious you want to be!

    We have made a small start for you in the file ExprVar.hs

    Hint: This exercise is more open-ended.

    You can try to define simplify recursively. You will however notice that it is difficult to accomplish many simplifications.

    (A different, but more ambitious, approach is to design a new type, that represents a normal form for expressions, for example polynomials. Your simplify function could simply transform an expression into a polynomial, and back into expressions again. How would you model polynomials over multiple variables as a type in Haskell?)

    Make sure that the following property holds for your simplify function: For each expression e, evaluating it in an environment generates the same result before and after simplifying:

      prop_SimplifyCorrect e (Env env) =
        eval env e == eval env (simplify e)

    C. Define a property:

      prop_SimplifyNoJunk :: Expr -> Bool
    that checks that the result of simplification does not "leave any junk". In other words, the result of simplification should for example not have subexpressions of the form:

  • Add (Num n) (Num m)

  • Mul (Num 0) b

  • Add a a
  • And so forth. What is allowed as "junk" and what is not of course depends on your simplification function, and what you expect from it.

    This property boils down to defining a function noJunk:: Expr -> Bool. We have already made a small start for you in ExprVar.hs.

    D. Define a property:

      prop_SimplifyDiff :: Expr -> Bool
    that checks that differentiating an expression and then simplifying it should have the same result as simplifying it first, then deriving, and then simplifying.

    Do you expect it to hold? Does it actually hold for your simplification function?

    3 (*). File Systems

    A file either contains data or is a directory. A directory contains other files (which may themselves be directories) along with a name for each one.

    A. Design a data type to represent the contents of a directory. Ignore the contents of files: you are just trying to represent file names and the way they are organised into directories here.

    B. Define a function to search for a given file name in a directory. You should return a path leading to a file with the given name. Thus if your directory contains a, b, and c, and b is a directory containing x and y, then searching for x should produce b/x.

    4. Exercises on Propositional Logic

    A proposition is a boolean formula of one of the following forms:

    where p and q are propositions. For example, p | ~p is a proposition.

    A. Design a data type Proposition to represent propositions.

    B. Define a function

    vars :: Proposition -> [String]

    which returns a list of the variables in a proposition. Make sure each variable appears only once in the list you return.

    Suppose you are given a list of variable names and their values, of type Bool, for example, [("p",True),("q",False)]. Define a function

    truthValue :: Proposition -> [(String,Bool)] -> Bool

    which determines whether the proposition is true when the variables have the values given.

    C. Define a function

    tautology :: Proposition -> Bool

    which returns true if the proposition holds for all values of the variables appearing in it.

    Congratulations! You have implemented a simple theorem prover.

    5. Approximating 0-solutions of functions

    Define a function:

    solve0 :: (Double -> Double) -> (Double,Double) -> Double

    The idea is that solve f (x0,x1) finds a value x in between x0 and x1 such that f x == 0.0.


      Main> solve0 (+1) (-3,3)
      Main> solve0 cos (2,5)
      Main> solve0 (\x -> x ^ 2 - 10) (1,10)
      Main> solve0 (\x -> x ^ 3) (1,1)
      Program error: no solution!
    If needed, you may assume the following reasonable assumptions:
  • f is continuous
  • f x0 <= 0 <= f x1
  • So, you may produce an error when this does not hold:
      Main> solve0 (\x -> x ^ 2) (1,10)
      Program error: bad interval!
    Your program has to approximate this value. For example, the answer to the first example above might be -0.999999999941792 instead of -1.0, and that is OK.

    One way to do this is to use the "halving" method: Calculate x that lies somewhere in between x0 and x1. Investigate f x. Then recursively solve f on either the interval (x0,x) or (x,x1).

    There are other methods too!