X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=hints%2Fassignment_4_hint_1.mdwn;fp=hints%2Fassignment_4_hint_1.mdwn;h=0000000000000000000000000000000000000000;hp=e95f96cc69cc0a2839f29d5ca5e459a9895b2a75;hb=fd698b815e417dec463cb0f0e9ed056ab83daed6;hpb=573a8b36ce653c84c2aecb2b81ef99128cb41d13 diff --git a/hints/assignment_4_hint_1.mdwn b/hints/assignment_4_hint_1.mdwn deleted file mode 100644 index e95f96cc..00000000 --- a/hints/assignment_4_hint_1.mdwn +++ /dev/null @@ -1,42 +0,0 @@ -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)) - -