hints/assignment_4_hint_2.mdwn

   1
   2 <!--
   3 let list_equal =
   4     \left right. left
   5                 ; here's our f
   6                 (\hd sofar.
   7                     ; deconstruct our sofar-pair
   8                     sofar (\might_be_equal right_tail.
   9                         ; our new sofar
  10                         make_pair
  11                         (and (and might_be_equal (not (isempty right_tail))) (eq? hd (head right_tail)))
  12                         (tail right_tail)
  13                     ))
  14                 ; here's our z
  15                 ; we pass along the fold a pair
  16                 ; (might_for_all_i_know_still_be_equal?, tail_of_reversed_right)
  17                 ; when left is empty, the lists are equal if right is empty
  18                 (make_pair
  19                     true ; for all we know so far, they might still be equal
  20                     (reverse right)
  21                 )
  22                 ; when fold is finished, check sofar-pair
  23                 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
  24 -->