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. (\f x. A) (u g)) in
+ let g = Y ( \g. (\f y. B) (u g)) in
+ let f = u g in
C
+ We could abstract 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. (\f x. A) (v g h)) in
+ let w = Y ( \w h. (\g. (\f y. B) (v g h)) (w h)) in
+ let h = Y ( \h. (\g. (\f z. 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
+ let f = Y1of3 (\f g h. A) (\f g h. B) (\f g h. C) in
+ let g = Y2of3 (\f g h. A) (\f g h. B) (\f g h. C) in
+ let h = Y3of3 (\f g h. A) (\f g h. B) (\f g h. C) in
+ D
+ -->
+