assignment4.mdwn

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