projects
/
lambda.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
04bcf24
)
edits
author
Chris Barker
<barker@omega.(none)>
Tue, 18 Jan 2011 04:11:50 +0000
(23:11 -0500)
committer
Chris Barker
<barker@omega.(none)>
Tue, 18 Jan 2011 04:11:50 +0000
(23:11 -0500)
hints/assignment_4_hint_3_alternate_2.mdwn
patch
|
blob
|
history
diff --git
a/hints/assignment_4_hint_3_alternate_2.mdwn
b/hints/assignment_4_hint_3_alternate_2.mdwn
index
1a86fa6
..
b2ddef8
100644
(file)
--- a/
hints/assignment_4_hint_3_alternate_2.mdwn
+++ b/
hints/assignment_4_hint_3_alternate_2.mdwn
@@
-7,8
+7,9
@@
rest on your own.
Let's remind ourselves of how the ordinary Y combinator works, since
we're going to attack mutual recursion in the same way.
Let's remind ourselves of how the ordinary Y combinator works, since
we're going to attack mutual recursion in the same way.
-First, we define a recursive proto-function that takes the true
-function (the fixed point) as an argument, then calls that argument.
+First, we define a recursive proto-function called `protomonoeven`
+that takes the true even function (the fixed point) as an argument,
+then calls that argument:
<pre>
let true = \y n . y in
<pre>
let true = \y n . y in
@@
-22,8
+23,8
@@
Y protomonoeven 3
</pre>
So in the equation `X = Y T`, `X`, the function that computes whether
</pre>
So in the equation `X = Y T`, `X`, the function that computes whether
-a number is even or not, is the fixed point of the
protoeven
function,
-i.e., `X = Y protoeven`.
+a number is even or not, is the fixed point of the
`protomonoeven`
function,
+i.e., `X = Y proto
mono
even`.
Obviously, we don't need mutual recursion to define the "even"
function (since we just defined it without mutual recursion).
Obviously, we don't need mutual recursion to define the "even"
function (since we just defined it without mutual recursion).
@@
-35,7
+36,7
@@
But we *can* define it using mutual recursion, as shown in assignment
Since we have two functions, we'll need two fixed points (`X1` and
`X2`), and therefore two fixed point combinators to compute them (`Y1`
Since we have two functions, we'll need two fixed points (`X1` and
`X2`), and therefore two fixed point combinators to compute them (`Y1`
-and `Y2`), and two protofunction (`protoeven` and `protoodd`) to feed
+and `Y2`), and two protofunction
s
(`protoeven` and `protoodd`) to feed
to the combinators. Furthermore, since the fixed points depend on
both the even function and the odd function, the combinators will need
to take two arguments, namely, both of the protofunctions:
to the combinators. Furthermore, since the fixed points depend on
both the even function and the odd function, the combinators will need
to take two arguments, namely, both of the protofunctions:
@@
-44,13
+45,13
@@
to take two arguments, namely, both of the protofunctions:
odd = X2 = Y2 protoeven protoodd
Writing protoeven and protoodd is easy. Analogously to the ordinary
odd = X2 = Y2 protoeven protoodd
Writing protoeven and protoodd is easy. Analogously to the ordinary
-case, they will take a
rguments that we want to find fixed points
for:
+case, they will take a
s arguments the very fixed points we're looking
for:
protoeven = \e o n . iszero n true (o (pred n))
protoodd = \e o n . iszero n false (e (pred n))
protoeven = \e o n . iszero n true (o (pred n))
protoodd = \e o n . iszero n false (e (pred n))
-Notice that
protoeven doesn't make use of its first argument (the one
-
that will eventually correspond to the even function itself)
. This is
+Notice that
`protoeven` doesn't make use of its first argument.
+
Likewise, `protoodd` doesn't make use of its second argument
. This is
an expository weakness in the choice of the example, which is
particularly simple.
an expository weakness in the choice of the example, which is
particularly simple.