Werk College 10

FP

Extra Exercises

  • In lecture 9 we have introduced a data structure which can be used to map all integers [0..] onto a function value. If we are prepared to treat the value 0 sperately, we can also place all integers in a tree as follows:
                                1
                 2                             3
          4            6               5            7
     8       12  10    14     9     13   11  15
    ...........................................................
    
    • copy the tree and write the bit patterns for each integer
    • find the recursive structure
    • define the corresponding data type which can be used as a map
    • reformulate the memo function given in the lecture such that it works for [1..], 0, and [-1,-2..]
  • Given a list of stamp values in monotonic order, write a function which computes in how many different ways one can construct a given value from these.

-- DoaitseSwierstra - 17 Oct 2010