hints/assignment_4_hint_1.mdwn

   1 Hints for reverse.
   2
   3 *       If left and right are two v3 lists, what is the result of:
   4
   5                 left make_list right
   6
   7 *       What is `reverse []`? What is `reverse [c]`? What is `reverse [b;c]`? How is it related to `reverse [c]`?
   8
   9 *       How is `reverse [a;b;c]` related to `reverse [b;c]`?
  10
  11 *       Getting any ideas?
  12
  13
  14 Another strategy.
  15
  16 *       Our version 3 lists are _right_-folds. That is, `[a;b;c]` is implemented as:
  17
  18                 \f z. f a (f b (f c z))
  19
  20         which is the result of first combining the base value `z` with the rightmost element of the list, using `f`, then combining the result of that with the next element to the left, and so on.
  21
  22         A _left_-fold on the same list would be:
  23
  24                 \f z. f (f (f z a) b) c
  25
  26         which is the result of first combining the base value `z` with the leftmost element of the list, then combining the result of that with the next element to the right, and so on.
  27
  28         It's conventional for `f` to take the accumulated value so far as its second argument when doing a right-fold, and for it to take it as its first argument when doing a left-fold. However, this convention could be ignored. We could also call this the left-fold of `[a;b;c]`:
  29
  30                 \f z. f c (f b (f a z))
  31
  32 *       Getting any ideas?
  33
  34 *       Our `make_list` function for taking an existing, right-fold-based list, and a new element, and returning a new right-fold-based list, looks like this:
  35
  36                 let make_list = \hd tl. \f z. f hd (tl f z)
  37
  38         How would you write a `make_left_list` function, that takes an existing, left-fold-based list, like `\f z. f c (f b z)`, and a new element, `a`, and returned the new, left-fold based list:
  39
  40                 \f z. f c (f b (f a z))
  41
  42