How do I define y-combinator without “let rec”?

by

As the compiler points out, there is no type that can be assigned to x so that the expression (x x) is well-typed (this isn’t strictly true; you can explicitly type x as obj->_ – see my last paragraph). You can work around this issue by declaring a recursive type so that a very similar expression will work:

type 'a Rec = Rec of ('a Rec -> 'a)

Now the Y-combinator can be written as:

let y f =
  let f' (Rec x as rx) = f (x rx)
  f' (Rec f')

Unfortunately, you’ll find that this isn’t very useful because F# is a strict language,
so any function that you try to define using this combinator will cause a stack overflow.
Instead, you need to use the applicative-order version of the Y-combinator (\f.(\x.f(\y.(x x)y))(\x.f(\y.(x x)y))):

let y f =
  let f' (Rec x as rx) = f (fun y -> x rx y)
  f' (Rec f')

Another option would be to use explicit laziness to define the normal-order Y-combinator:

type 'a Rec = Rec of ('a Rec -> 'a Lazy)
let y f =
  let f' (Rec x as rx) = lazy f (x rx)
  (f' (Rec f')).Value

This has the disadvantage that recursive function definitions now need an explicit force of the lazy value (using the Value property):

let factorial = y (fun f -> function | 0 -> 1 | n -> n * (f.Value (n - 1)))

However, it has the advantage that you can define non-function recursive values, just as you could in a lazy language:

let ones = y (fun ones -> LazyList.consf 1 (fun () -> ones.Value))

As a final alternative, you can try to better approximate the untyped lambda calculus by using boxing and downcasting. This would give you (again using the applicative-order version of the Y-combinator):

let y f =
  let f' (x:obj -> _) = f (fun y -> x x y)
  f' (fun x -> f' (x :?> _))

This has the obvious disadvantage that it will cause unneeded boxing and unboxing, but at least this is entirely internal to the implementation and will never actually lead to failure at runtime.

Leave a Comment