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 let list_equal =
  19     \left right. left
  20                 ; here's our f
  21                 (\hd sofar.
  22                     ; deconstruct our sofar-pair
  23                     sofar (\might_be_equal right_tail.
  24                         ; our new sofar
  25                         make_pair
  26                         (and (and might_be_equal (not (isempty right_tail))) (eq? hd (head right_tail)))
  27                         (tail right_tail)
  28                     ))
  29                 ; here's our z
  30                 ; we pass along the fold a pair
  31                 ; (might_for_all_i_know_still_be_equal?, tail_of_reversed_right)
  32                 ; when left is empty, the lists are equal if right is empty
  33                 (make_pair
  34                     true ; for all we know so far, they might still be equal
  35                     (reverse right)
  36                 )
  37                 ; when fold is finished, check sofar-pair
  38                 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
  39 -->
  40
  41 <!--
  42 list_equal [] right      = isempty right
  43 list_equal (hd:tl) right = and (not (isempty right))
  44                             (hd == head right)
  45                             (list_equal tl (tail right))
  46
  47 Rearangement:
  48
  49 list_equal []      = \right -> isempty right
  50 list_equal (hd:tl) = let prev = list_equal tl
  51                      in \right -> and (not (isempty right))
  52                                    (hd == head right)
  53                                    (prev (tail right))
  54
  55 Now it fits the pattern of fold_right
  56
  57 let list_equal = \left. left (\hd sofar. \right. and (and (not (isempty right)) (eq hd (head right))) (sofar (tail right))) isempty
  58
  59 -->
  60