assign 4: hints for list_equal

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

diff --git a/hints/assignment_4_hint_2.mdwn b/hints/assignment_4_hint_2.mdwn
index 78cb1bd..5ee63f5 100644 (file)
--- a/hints/assignment_4_hint_2.mdwn
+++ b/hints/assignment_4_hint_2.mdwn
@@ -1,4 +1,51 @@
-Hints for list\_equal.
+Hints for `list_equal`.
+
+*      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.)
+
+*      Suppose on the other hand that `left` has head `left_hd` and tail `left_tl`.
+       
+       <OL type=a>
+       <LI>If `right` is then `[]`, are `left` and `right` equal?
+       <LI>If `right` isn't `[]`, and its head isn't equal to `left_hd`, are `left` and `right` equal?
+       <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?
+       </OL>
+
+*      Can you now write a recursive definition of the `list_equal` function?
+What's your base case?
+
+
+<!--
+eql [] l2        = empty l2
+eql (l1h:l1t) l2 = and (not (empty l2))
+                       (l1h == head l2)
+                       (eql l1t (tail l2))
+
+Simple rearangement:
+
+eql []        = \l2 -> empty l2
+eql (l1h:l1t) = \l2 -> and (not (empty l2))
+                       (l1h == head l2)
+                       (eql l1t (tail l2))
+
+and another one rearrangement:
+
+eql []        = \l2 -> empty l2
+eql (l1h:l1t) = let prev = eql l1t
+                in \l2 -> and (not (empty l2))
+                              (l1h == head l2)
+                              (prev (tail l2))
+
+Now it fits the pattern of foldr
+
+So, the end result:
+
+eql = foldr f z
+ where
+ z = empty
+ f h z = \l2 -> and (not (empty l2))
+                    (h == head l2)
+                    (z (tail l2))
+-->

 
 <!--
 let list_equal =
 
 <!--
 let list_equal =


@@ -23,3 +70,4 @@ let list_equal =
                 ; when fold is finished, check sofar-pair
                 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
 -->
                 ; when fold is finished, check sofar-pair
                 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
 -->

+

diff --git a/lambda_library.mdwn b/lambda_library.mdwn
index 5623b9f..6441d3b 100644 (file)
--- a/lambda_library.mdwn
+++ b/lambda_library.mdwn
@@ -314,7 +314,7 @@ 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
                 ; (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
                     (reverse right)
                 )
                 ; when fold is finished, check sofar-pair