One thing that’s cool about the Y combinator is that it lets you “overload” recursion with extra stuff. So instead of doing normal recursion, like this:
# let rec fac n = if n = 1 then 1 else n * fac (n - 1);; val fac : int -> int = <fun> # fac 12;; - : int = 479001600
You can do this, where you “factor the recursion out” into a separate function:
# let rec y f x = f (y f) x;; val y : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> # let fac_ fac n = if n = 1 then 1 else n * fac (n - 1);; val fac_ : (int -> int) -> int -> int = <fun> # y fac_ 12;; - : int = 479001600
That lets you define higher-order functions you can pass these y-ified single-recursive-step functions into, which can augment each recursive call with, for example, a side effect:
# let trace name f_ f x = let r = f_ f x in Printf.printf "%d <- %s %d\n%!" r name x; r;; val trace : string -> ('a -> int -> int) -> 'a -> int -> int = <fun> # y (trace "fac called on" fac_) 12;; 1 <- fac called on 1 2 <- fac called on 2 6 <- fac called on 3 24 <- fac called on 4 120 <- fac called on 5 720 <- fac called on 6 5040 <- fac called on 7 40320 <- fac called on 8 362880 <- fac called on 9 3628800 <- fac called on 10 39916800 <- fac called on 11 479001600 <- fac called on 12 - : int = 479001600
But given that Y is forward-recursive, you blow up your stack if you use this technique with large inputs:
# y (trace "fac called on" fac_) 5000000;; Stack overflow during evaluation (looping recursion?).
I was wondering, has anyone come up with a trick for implementing a version of Y that uses constant stack space? There isn’t an obvious way to naively make Curry’s definition tail recursive with the recursive call to
y in the middle of those two
f-s. Maybe with some weird imperative thing? I played around a little with a while loop, but I’m also not sure what (if anything!) the imperative analogue of Curry’s mind-bendy recursive definition would be.