From 809b76fd4dfff7b2a54ebfd84a6f92ac6ae131ee Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sat, 16 Oct 2010 16:41:43 -0400 Subject: [PATCH] alternate Y1,Y2 tweak Signed-off-by: Jim Pryor --- hints/assignment_4_hint_3_alternate_1.mdwn | 40 ++++++++++++++++++++++-------- 1 file changed, 30 insertions(+), 10 deletions(-) diff --git a/hints/assignment_4_hint_3_alternate_1.mdwn b/hints/assignment_4_hint_3_alternate_1.mdwn index 99a4202b..b0c06735 100644 --- a/hints/assignment_4_hint_3_alternate_1.mdwn +++ b/hints/assignment_4_hint_3_alternate_1.mdwn @@ -11,23 +11,43 @@ Alternate strategy for Y1, Y2 is implemented using regular, non-mutual recursion, like this (`u` is a variable not occurring free in `A`, `B`, or `C`): - let rec u g x = (let f = u g in A) - in let rec g y = (let f = u g in B) - in let f = u g in + let rec u g x = (let f = u g in A) in + let rec g y = (let f = u g in B) in + let f = u g in C or, expanded into the form we've been working with: - let u = Y (\u g x. (\f. A) (u g)) in - let g = Y ( \g y. (\f. B) (u g)) in - let f = u g in + let u = Y (\u g x. (\f. A) (u g)) in + let g = Y ( \g y. (\f. B) (u g)) in + let f = u g in C + We abstract the Y1 and Y2 combinators from this as follows: + + let Yu = \ff. Y (\u g. ff ( u g ) g) in + let Y2 = \ff gg. Y ( \g. gg (Yu ff g ) g) in + let Y1 = \ff gg. (Yu ff) (Y2 ff gg) in + let f = Y1 (\f g. A) (\f g. B) in + let g = Y2 (\f g. A) (\f g. B) in + C + + * Here's the same strategy extended to three mutually-recursive functions. `f`, `g` and `h`: - let u = Y (\u g h x. (\f. A) (u g h)) in - let w = Y ( \w h x. (\g. (\f. B) (u g h)) (w h)) in - let h = Y ( \h x. (\g. (\f. C) (u g h)) (w h)) in + let v = Y (\v g h x. (\f. A) (v g h)) in + let w = Y ( \w h x. (\g. (\f. B) (v g h)) (w h)) in + let h = Y ( \h x. (\g. (\f. C) (v g h)) (w h)) in let g = w h in - let f = u g h in + let f = v g h in D + + Or in Y1of3, Y2of3, Y3of3 form: + + let Yv = \ff. Y (\v g h. ff ( v g h) g h) in + let Yw = \ff gg. Y ( \w h. (\g. gg (Yv ff g h) g h) ( w h)) in + let Y3of3 = \ff gg hh. Y ( \h. (\g. hh (Yv ff g h) g h) (Yw ff gg h)) in + let Y2of3 = \ff gg hh. Yw ff gg (Y3of3 ff gg hh) in + let Y1of3 = \ff gg hh. Yv ff (Y2of3 ff gg hh) (Y3of3 ff gg hh) in + D + -- 2.11.0