projects
/
lambda.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
continuing assignment4
[lambda.git]
/
assignment3.mdwn
diff --git
a/assignment3.mdwn
b/assignment3.mdwn
index
50495f5
..
289f818
100644
(file)
--- a/
assignment3.mdwn
+++ b/
assignment3.mdwn
@@
-14,32
+14,30
@@
Recall that version 1 style lists are constructed like this (see
let false = \x y. y in
let and = \l r. l (r true false) false in
let false = \x y. y in
let and = \l r. l (r true false) false in
- ; version 1 lists
let make_pair = \f s g. g f s in
let make_pair = \f s g. g f s in
- let fst = true in
- let snd = false in
+ let
get_
fst = true in
+ let
get_
snd = false in
let empty = make_pair true junk in
let empty = make_pair true junk in
- let isempty = \x. x fst in
+ let isempty = \x. x
get_
fst in
let make_list = \h t. make_pair false (make_pair h t) in
let make_list = \h t. make_pair false (make_pair h t) in
- let head = \l. isempty l err (l
snd
fst) in
- let tail = \l. isempty l err (l
snd
snd) in
-
+ let head = \l. isempty l err (l
get_snd get_
fst) in
+ let tail = \l. isempty l err (l
get_snd get_
snd) in
+
; a list of numbers to experiment on
let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
; a list of numbers to experiment on
let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
-
- ; a fixed-point combinator for defining recursive functions
- let Y = \f. (\h. f (h h)) (\h. f (h h)) in
-
+
; church numerals
let iszero = \n. n (\x. false) true in
let succ = \n s z. s (n s z) in
; church numerals
let iszero = \n. n (\x. false) true in
let succ = \n s z. s (n s z) in
- let mult = \m n s. m (n s) in
- let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
- let pred = \n. iszero n 0 (length (tail (n (\p. make_list junk p) empty)))
- in
+ let mul = \m n s. m (n s) in
+ let pred = (\shift n. n shift (make\_pair 0 0) get\_snd) (\p. p (\x y. make\_pair (succ x) x)) in
let leq = \m n. iszero(n pred m) in
let eq = \m n. and (leq m n)(leq n m) in
let leq = \m n. iszero(n pred m) in
let eq = \m n. and (leq m n)(leq n m) in
-
+
+ ; a fixed-point combinator for defining recursive functions
+ let Y = \f. (\h. f (h h)) (\h. f (h h)) in
+ let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
+
eq 2 2 yes no
eq 2 2 yes no
@@
-51,7
+49,7
@@
Then `length mylist` evaluates to 3.
function, write a function that computes factorials. (Recall that n!,
the factorial of n, is n times the factorial of n-1.)
function, write a function that computes factorials. (Recall that n!,
the factorial of n, is n times the factorial of n-1.)
-Warning: it takes a long time for my browser to compute factorials larger than 4!
+
Warning: it takes a long time for my browser to compute factorials larger than 4!
3. (Easy) Write a function `equal_length` that returns true just in case
two lists have the same length. That is,
3. (Easy) Write a function `equal_length` that returns true just in case
two lists have the same length. That is,
@@
-108,7
+106,8
@@
whether the length of the list is less than or equal to 1. This will
be your base case for your recursive functions that operate on these
trees.
be your base case for your recursive functions that operate on these
trees.
-1. Write a function that sums the number of leaves in a tree.
+<OL start=6>
+<LI>Write a function that sums the values at the leaves in a tree.
Expected behavior:
Expected behavior:
@@
-131,5
+130,7
@@
Expected behavior:
sum-leaves tc ~~> 6
sum-leaves tc ~~> 6
-2. Write a function that counts the number of leaves.
+<LI>Write a function that counts the number of leaves.
+
+</OL>