1 Hints for `list_equal`.
3 * If `left` is `[]`, what does `right` have to be for `left` and `right` to be equal? (Come on, it's not too hard, you can figure it out.)
5 * Suppose on the other hand that `left` has head `left_hd` and tail `left_tl`.
8 <LI>If `right` is then `[]`, are `left` and `right` equal?
9 <LI>If `right` isn't `[]`, and its head isn't equal to `left_hd`, are `left` and `right` equal?
10 <LI>If `right` isn't `[]` and its head *is* equal to `left_hd`, what else has to be the case for `left` and `right` to be equal?
13 * Can you now write a recursive definition of the `list_equal` function?
14 What's your base case?
19 eql (l1h:l1t) l2 = and (not (empty l2))
25 eql [] = \l2 -> empty l2
26 eql (l1h:l1t) = \l2 -> and (not (empty l2))
30 and another one rearrangement:
32 eql [] = \l2 -> empty l2
33 eql (l1h:l1t) = let prev = eql l1t
34 in \l2 -> and (not (empty l2))
38 Now it fits the pattern of foldr
45 f h z = \l2 -> and (not (empty l2))
55 ; deconstruct our sofar-pair
56 sofar (\might_be_equal right_tail.
59 (and (and might_be_equal (not (isempty right_tail))) (eq? hd (head right_tail)))
63 ; we pass along the fold a pair
64 ; (might_for_all_i_know_still_be_equal?, tail_of_reversed_right)
65 ; when left is empty, the lists are equal if right is empty
67 true ; for all we know so far, they might still be equal
70 ; when fold is finished, check sofar-pair
71 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))