index: remove test
[lambda.git] / 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