assignment4.mdwn

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