hints/assignment_4_hint_2.mdwn

   1 Hints for `list_equal`.
   2
   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.)
   4
   5 *       Suppose on the other hand that `left` has head `left_hd` and tail `left_tl`.
   6
   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>
  12
  13 *       Can you now write a recursive definition of the `list_equal` function?
  14 What's your base case?
  15
  16
  17 <!--
  18 eql [] l2        = empty l2
  19 eql (l1h:l1t) l2 = and (not (empty l2))
  20                        (l1h == head l2)
  21                        (eql l1t (tail l2))
  22
  23 Simple rearangement:
  24
  25 eql []        = \l2 -> empty l2
  26 eql (l1h:l1t) = \l2 -> and (not (empty l2))
  27                        (l1h == head l2)
  28                        (eql l1t (tail l2))
  29
  30 and another one rearrangement:
  31
  32 eql []        = \l2 -> empty l2
  33 eql (l1h:l1t) = let prev = eql l1t
  34                 in \l2 -> and (not (empty l2))
  35                               (l1h == head l2)
  36                               (prev (tail l2))
  37
  38 Now it fits the pattern of foldr
  39
  40 So, the end result:
  41
  42 eql = foldr f z
  43  where
  44  z = empty
  45  f h z = \l2 -> and (not (empty l2))
  46                     (h == head l2)
  47                     (z (tail l2))
  48 -->
  49
  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 -->
  73