Functional Programming

Distance Course (1DL027)
Uppsala University, Sweden

Assignment 2

D. Fruit

There are three kinds of fruit; apples, bananas and lemons. Bananas and apples are sold by the kilogram but a lemon has always the same price, regardless of weight,
  1. Give a datatype declaration for the type fruit. The datatype should reflect that there are three kinds of fruit, so the datatype definition should have three cases. For apple and bananas there should be an associated weight (given as a real value).
  2. Define (and specify) the function
    sumPrice(fruit list * real * real * real) -> real
    The function should take a list of fruit, the price of apples (per kilogram), bananas (per kilogram) and the price of lemons (per unit) and return the total cost of the items in the list.
Examples

Suppose the price of apples and bananas is 10 and 14 crowns per kilogram, and that a lemon costs 2 crowns.

If we do not buy any fruits, the price for the fruit is 0.0. 

- sumPrice([], 10.0, 14.0, 2.0);
val it = 0.0 : real
Suppose we buy only one apple (weight 0.1 kilograms) 
- sumPrice([Apple(0.1)], 10.0, 14.0, 2.0);
val it = 1.0 : real
If we buy two apples (weight 0.1 and 0.09 kilograms): 
- sumPrice([Apple(0.1), Apple(0.09)], 10.0, 14.0, 2.0);
val it = 1.9 : real
One banana: 
- sumPrice([Banana(0.15)], 10.0, 14.0, 2.0);
val it = 2.1 : real
One banana and one lemon: 
- sumPrice([Banana(0.15), Lemon], 10.0, 14.0, 2.0);
val it = 4.1 : real
-

E. Binary Trees

The file bTree.sml has the beginning of the realisation of a polymorphic abstract datatype (ADT) for binary trees, specified on slides 6.19 and 6.20. The file trees.sml has sample trees for your tests and the examples below. Extend that ADT with the following functions, but declare it as a non-abstract datatype, just to ease the testing:
  1. nbLeaves b: the number of leaves of binary tree b
    Example: nbLeaves smallIntTree = 3
  2. isLeafOf x b: true if and only if x is a leaf of binary tree b
    Example: isLeafOf 7 smallIntTree = true
  3. descendants x b: the list of descendants of x in binary tree b, and exception NotFound raised if x is not in b
    Example: descendants 2 smallIntTree = [5,3,7]
    Example: descendants 7 smallIntTree = []
    Example: descendants 9 smallIntTree raises NotFound
  4. preorder b: the preorder walk, as a list, of binary tree b
    Example: preorder smallIntTree = [1,2,5,7,3,6,10,13]
    Requirements: Do not use any help functions. Is your function tail-recursive? Why / Why not?
  5. preorder' b: same specification as preorder
    Requirements: Perform a descending generalisation, that is use a help function employing the accumulator technique. Is your function tail-recursive? Why / Why not?
  6. Which of the functions preorder, and preorder' is the most efficient in run-time? in memory consumption? Why?