assignment4: reverse

Signed-off-by: Jim Pryor <profjim@jimpryor.net>

diff --git a/assignment4.mdwn b/assignment4.mdwn
index 34fb044..7423806 100644 (file)
--- a/assignment4.mdwn
+++ b/assignment4.mdwn
@@ -1,13 +1,12 @@
-Assignment 4
-------------
-
 #Reversing a list#
 
-How would you define an operation to reverse a list? (Don't peek at the
+1.     How would you define an operation to reverse a list? (Don't peek at the
 [[lambda_library]]! Try to figure it out on your own.) Choose whichever
 implementation of list you like. Even then, there are various strategies you
 can use.
 
+(See [[hints/Assignment 4 hint 1]] if you need some hints.)
+
 
 #Comparing lists for equality#
 
@@ -28,13 +27,17 @@ let list_equal =
                 ; (might_for_all_i_know_still_be_equal?, tail_of_reversed_right)
                 ; when left is empty, the lists are equal if right is empty
                 (make_pair
-                    (not (isempty right))
+                    true ; for all we know so far, they might still be equal
                     (reverse right)
                 )
                 ; when fold is finished, check sofar-pair
                 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
 -->
 
+#Mutually-recursive functions#
+
+
+
 #Enumerating the fringe of a leaf-labeled tree#
 
 [[Implementing trees]]

diff --git a/hints/assignment_4_hint_1.mdwn b/hints/assignment_4_hint_1.mdwn
new file mode 100644 (file)
index 0000000..e95f96c
--- /dev/null
+++ b/hints/assignment_4_hint_1.mdwn
@@ -0,0 +1,42 @@
+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))
+
+