assignment4.mdwn

   1 #Reversing a list#
   2
   3 <OL>
   4 <LI>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 (See [[hints/Assignment 4 hint 1]] if you need some hints.)
  10 </OL>
  11
  12
  13 #Comparing lists for equality#
  14
  15 <OL start=2>
  16 <LI>blah
  17 </OL>
  18 <!--
  19 let list_equal =
  20     \left right. left
  21                 ; here's our f
  22                 (\hd sofar.
  23                     ; deconstruct our sofar-pair
  24                     sofar (\might_be_equal right_tail.
  25                         ; our new sofar
  26                         make_pair
  27                         (and (and might_be_equal (not (isempty right_tail))) (eq? hd (head right_tail)))
  28                         (tail right_tail)
  29                     ))
  30                 ; here's our z
  31                 ; we pass along the fold a pair
  32                 ; (might_for_all_i_know_still_be_equal?, tail_of_reversed_right)
  33                 ; when left is empty, the lists are equal if right is empty
  34                 (make_pair
  35                     true ; for all we know so far, they might still be equal
  36                     (reverse right)
  37                 )
  38                 ; when fold is finished, check sofar-pair
  39                 (\might_be_equal right_tail. and might_be_equal (isempty right_tail))
  40 -->
  41
  42 #Mutually-recursive functions#
  43
  44 <OL start=3>
  45 <LI>blah
  46 </OL>
  47
  48
  49 #Enumerating the fringe of a leaf-labeled tree#
  50
  51 [[Implementing trees]]
  52
  53
  54 <OL start=4>
  55 <LI>blah
  56 </OL>
  57