Back to Questions
2.7k
views1
comment
Y Combinator and Unification
f#

Before I begin I will post my code to save time in the event that this question is obvious:

let doAtoB (a,b) =

if b < 0 then

1

else

1 + a(a,(b-1))

print_any (doAtoB(doAtoB,5))

I was recently learning about the Y Combinator and was interested in implementing it in F#. I kept getting the same error:

"Type Mismatch: Expecting a 'a but given a 'a * 'b -> int. The resulting type would be infinite when unifying 'a and 'a * 'b -> int"

As the error suggests the type would be growing as:

'a*int -> int

('a*int -> int) * int -> int

(('a*int -> int) *int -> int) * int -> int

So I get that the type is infinite, but there seems to be no way around this. The code should work just fine, it just can't be handled by the type inferencing mechanism. Scheme claims to be able to do this. Is this functionality simply not availible in F#? Is there no way to write a Y Combinator in the language?

Thank you very much to anyone who has an idea what the answer here might be.

.

It is not possible to write the Y combinator in typed lambda calculus. However you need the Y combinator in order to write any useful programs, so typed functional languages like F#/OCaml get around this problem by introducing the let rec construct. Essentially let rec is the Y combinator built in to the language itself.

So a normal F# programmer would write your function as

1

let rec doAtoB b = if b < 0 then 1 else 1 + doAtoB (b-1)

However, with the presence of letrec you can of course write a fixed point combinator in terms of letrec. So a type-theoretic F# programmer could write

1
2
3
4

let rec fix f = f (fun x -> fix f x)

let a f b = if b < 0 then 1 else 1 + f (b-1)
let doAtoB = fix a

Where fix is the Y combinator you are looking for and you can isolate all use of letrec to this one function.

By on 12/5/2007 10:17 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper