exercises/assignment1.mdwn

   1 1.  Define a function `zero?` that expects a single number as an argument, and returns `'true` if that number is `0`, else returns `'false`. Your solution should have a form something like this:
   2
   3         let
   4           zero? match lambda x. FILL_IN_THIS_PART
   5         in zero?
   6
   7     You can use the `if...then...else` construction if you like, but it will make it easier to generalize to later problems if you use the `case EXPRESSION of PATTERN1 then RESULT1; PATTERN2 then RESULT2; ... end` construction instead.
   8
   9 2.  Define a function `empty?` that expects a sequence of values as an argument (doesn't matter what type of values), and returns `'true` if that sequence is the empty sequence `[]`, else returns `'false`. Here your solution should have a form something like this:
  10
  11         let
  12           empty? match lambda xs. case xs of
  13                                      FILL_IN_THIS_PART
  14                                   end
  15         in empty?
  16
  17 3.  Define a function `tail` that expects a sequence of values as an argument (doesn't matter what type of values), and returns that sequence with the first element (if any) stripped away. (Applying `tail` to the empty sequence `[]` can just give us back the empty sequence.)
  18
  19 4.  Define a function `drop` that expects two arguments, in the form (*number*, *sequence*), and works like this:
  20
  21         drop (0, [10, 20, 30])  # evaluates to [10, 20, 30]
  22         drop (1, [10, 20, 30])  # evaluates to [20, 30]
  23         drop (2, [10, 20, 30])  # evaluates to [30]
  24         drop (3, [10, 20, 30])  # evaluates to []
  25         drop (4, [10, 20, 30])  # evaluates to []
  26
  27     Your solution should have a form something like this:
  28
  29         letrec
  30           drop match lambda (n, xs). FILL_IN_THIS_PART
  31         in drop
  32
  33     What is the relation between `tail` and `drop`?
  34
  35 5.  Define a function `take` that expects two arguments, in the same form as `drop`, but works like this instead:
  36
  37         take (0, [10, 20, 30])  # evaluates to []
  38         take (1, [10, 20, 30])  # evaluates to [10]
  39         take (2, [10, 20, 30])  # evaluates to [10, 20]
  40         take (3, [10, 20, 30])  # evaluates to [10, 20, 30]
  41         take (4, [10, 20, 30])  # evaluates to [10, 20, 30]
  42
  43 6.  Define a function `split` that expects two arguments, in the same form as `drop` and `take`, but this time evaluates to a pair of results. It works like this:
  44
  45         split (0, [10, 20, 30])  # evaluates to ([], [10, 20, 30])
  46         split (1, [10, 20, 30])  # evaluates to ([10], [20, 30])
  47         split (2, [10, 20, 30])  # evaluates to ([10, 20], [30])
  48         split (3, [10, 20, 30])  # evaluates to ([10, 20, 30], [])
  49         split (4, [10, 20, 30])  # evaluates to ([10, 20, 30], [])
  50
  51     Here's a way to answer this problem making use of your answers to previous questions:
  52
  53         letrec
  54           drop match ... ; # as in problem 4
  55           take match ... ; # as in problem 5
  56           split match lambda (n, xs). let
  57                                         ys = take (n, xs);
  58                                         zs = drop (n, xs)
  59                                       in (ys, zs)
  60         in split
  61
  62     However, we want you to instead write this function from scratch. The method displayed above would traverse the sequence (at least, its first `n` members) *twice*. Can you do it in a way that only traverses (that part of the) sequence once?
  63
  64 7.  Write a function `filter` that expects two arguments. The second argument will be a sequence `xs` with elements of some type *t*, for example numbers. The first argument will be a function `p` that itself expects arguments of type *t* and returns `'true` or `'false`. What `filter` should return is a sequence that contains exactly those members of `xs` for which `p` returned `'true`. For example, helping ourself to a function `odd?` that works as you'd expect:
  65
  66         filter (odd?, [11, 12, 13, 14])  # evaluates to [11, 13]
  67         filter (odd?, [11])              # evaluates to [11]
  68         filter (odd?, [12, 14])          # evaluates to []
  69
  70 8.  Write a function `partition` that expects two arguments, in the same form as `filter`, but this time evaluates to a pair of results. It works like this:
  71
  72         partition (odd?, [11, 12, 13, 14])  # evaluates to ([11, 13], [12, 14])
  73         partition (odd?, [11])              # evaluates to ([11], [])
  74         partition (odd?, [12, 14])          # evaluates to ([], [12, 14])
  75
  76 9.  Write a function `double` that expects one argument which is a sequence of numbers, and returns a sequence of the same length with the corresponding elements each being twice the value of the original element. For example:
  77
  78         double [10, 20, 30]  # evaluates to [20, 40, 60]
  79         double []            # evaluates to []
  80
  81 10.  Write a function `map` that generalizes `double`. This function expects a pair of arguments, the second being a sequence `xs` with elements of some type *t*, for example numbers. The first argument will be a function `f` that itself expects arguments of type *t* and returns some type *t'* of result. What `map` should return is a sequence of the results, in the same order as the corresponding original elements. The result should be that we could say:
  82
  83         letrec
  84           map match lambda (f, xs). FILL_IN_THIS_PART;
  85           double match lambda xs. map ((lambda x. 2*x), xs)
  86         in ...
  87
  88 11. Write a function `map2` that generalizes `map`. This function expects a triple of arguments: the first being a function `f` as for `map`, and the second and third being two sequences. In this case `f` is a function that expects *two* arguments, one from the first of the sequences and the other from the corresponding position in the other sequence. The result should behave like this:
  89
  90         map2 ((lambda (x,y). 10*x + y), [1, 2, 3], [4, 5, 6])  # evaluates to [14, 25, 36]
  91
  92
  93 ###Extra credit problems###
  94
  95 *   In class I mentioned a function `&&` which occupied the position *between* its arguments, rather than coming before them (this is called an "infix" function). The way that it works is that `[1, 2, 3] && [4, 5]` evaluates to `[1, 2, 3, 4, 5]`. Define this function, making use of `letrec` and the simpler infix operation `&`.
  96
  97 *   Write a function `unmap2` that is something like the inverse of `map2`. This function expects two arguments, the second being a sequence of elements of some type *t*. The first is a function `g` that expects a single argument of type *t* and returns a *pair* of results, rather than just one result. We want to collate these results, the first into one sequence, and the second into a different sequence. Then `unmap2` should return those two sequences. Thus if:
  98
  99         g z1  # evaluates to (x1, y1)
 100         g z2  # evaluates to (x2, y2)
 101         g z3  # evaluates to (x3, y3)
 102
 103     Then `unmap2 (g, [z1, z2, z3])` should evaluate to `([x1, x2, x3], [y1, y2, y3])`.
 104
 105 *   Write a function `takewhile` that expects a `p` argument like `filter`, and also a sequence. The result should behave like this:
 106
 107         takewhile ((lambda x. x < 10), [1, 2, 20, 4, 40]) # evaluates to [1, 2]
 108
 109     Note that we stop "taking" once we reach `20`, even though there are still later elements in the sequence that are less than `10`.
 110
 111 *   Write a function `dropwhile` that expects a `p` argument like `filter`, and also a sequence. The result should behave like this:
 112
 113         dropwhile ((lambda x. x < 10), [1, 2, 20, 4, 40]) # evaluates to [20, 4, 40]
 114
 115     Note that we stop "dropping" once we reach `20`, even though there are still later elements in the sequence that are less than `10`.
 116
 117 *   Write a function `reverse` that returns the reverse of a sequence. Thus, `reverse [1, 2, 3, 4]` should evaluate to `[4, 3, 2, 1]`.
 118