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.
7         <OL type=a>
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?
11         </OL>
13 *       Can you now write a recursive definition of the list_equal function?
14 What's your base case?
17 <!--
18 eql [] l2        = empty l2
19 eql (l1h:l1t) l2 = and (not (empty l2))
21                        (eql l1t (tail l2))
23 Simple rearangement:
25 eql []        = \l2 -> empty l2
26 eql (l1h:l1t) = \l2 -> and (not (empty l2))
28                        (eql l1t (tail 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))
36                               (prev (tail l2))
38 Now it fits the pattern of foldr
40 So, the end result:
42 eql = foldr f z
43  where
44  z = empty
45  f h z = \l2 -> and (not (empty l2))
47                     (z (tail l2))
48 -->
50 <!--
51 let list_equal =
52     \left right. left
53                 ; here's our f
54                 (\hd sofar.
55                     ; deconstruct our sofar-pair
56                     sofar (\might_be_equal right_tail.
57                         ; our new sofar
58                         make_pair
59                         (and (and might_be_equal (not (isempty right_tail))) (eq? hd (head right_tail)))
60                         (tail right_tail)
61                     ))
62                 ; here's our z
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
66                 (make_pair
67                     true ; for all we know so far, they might still be equal
68                     (reverse right)
69                 )
70                 ; when fold is finished, check sofar-pair
71                 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
72 -->