assignment4.mdwn

   1
   2 #Reversing a list#
   3
   4 How would you define an operation to reverse a list? (Don't peek at the
   5 [[lambda_library]]! Try to figure it out on your own.) Choose whichever
   6 implementation of list you like. Even then, there are various strategies you
   7 can use.
   8
   9
  10
  11 <!--
  12 let list_equal =
  13     \left right. left
  14                 ; here's our f
  15                 (\hd sofar.
  16                     ; deconstruct our sofar-pair
  17                     sofar (\might_be_equal right_tail.
  18                         ; our new sofar
  19                         make_pair
  20                         (and (and might_be_equal (not (isempty right_tail))) (eq? hd (head right_tail)))
  21                         (tail right_tail)
  22                     ))
  23                 ; here's our z
  24                 ; we pass along the fold a pair
  25                 ; (might_for_all_i_know_still_be_equal?, tail_of_reversed_right)
  26                 ; when left is empty, the lists are equal if right is empty
  27                 (make_pair
  28                     (not (isempty right))
  29                     (reverse right)
  30                 )
  31                 ; when fold is finished, check sofar-pair
  32                 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
  33 -->
  34
  35 [[Implementing trees]]