Hints for reverse.

• If left and right are two v3 lists, what is the result of:

  left make_list right
  

• What is reverse []? What is reverse [c]? What is reverse [b;c]? How is it related to reverse [c]?

• How is reverse [a;b;c] related to reverse [b;c]?

• Getting any ideas?

Another strategy.

• Our version 3 lists are right-folds. That is, [a;b;c] is implemented as:

  \f z. f a (f b (f c z))
  

  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.

  A left-fold on the same list would be:

  \f z. f (f (f z a) b) c
  

  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.

  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]:

  \f z. f c (f b (f a z))
  

• Getting any ideas?

• 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:

  let make_list = \hd tl. \f z. f hd (tl f z)
  

  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:

  \f z. f c (f b (f a z))