From 0ee4fffb00fe8d2ea489416173909e6ef06fbefb Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sun, 3 Oct 2010 17:35:58 -0400 Subject: [PATCH] assignment4: reverse Signed-off-by: Jim Pryor --- assignment4.mdwn | 13 ++++++++----- hints/assignment_4_hint_1.mdwn | 42 ++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 50 insertions(+), 5 deletions(-) create mode 100644 hints/assignment_4_hint_1.mdwn diff --git a/assignment4.mdwn b/assignment4.mdwn index 34fb044d..74238062 100644 --- 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 index 00000000..e95f96cc --- /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)) + + -- 2.11.0