Y combinator in Swift!

gistfile1.swift

/* The Y combinator in Swift!

For a discussion of what the heck this is all about, see http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

The nifty thing is that it allows us to implement recursion without the ability for a function to refer to itself from within its own definition. 

Note how we manage a recursive definition of factorial without any function referring to its own name.

Thanks to @eridius for help with the SelfToUnderlying<T> type.
*/

func Y<Domain,Range>(almost:(Domain->Range)->(Domain->Range))->(Domain->Range) {
    typealias DtoR = Domain->Range
    return {
        (next:SelfToUnderlying<DtoR>)->DtoR in
        return almost({
            (args:Domain)->Range in
            return next.value(next)(args)
            })
        }(SelfToUnderlying<DtoR>(value:{
            (next:SelfToUnderlying<DtoR>)->DtoR in
            return almost({
                (args:Domain)->Range in
                return next.value(next)(args)
                })
            }))
}

class SelfToUnderlying<T> {
    var value : SelfToUnderlying<T>->T
    init(value:SelfToUnderlying<T>->T) {
        self.value = value
    }
}

func almostFactorial(recur: Int -> Int)(n: Int) -> Int {
    switch n {
        case 0: return 1
        case _: return n * recur(n-1)
    }
}

let factorial = Y(almostFactorial)
println(factorial(5))


// a way easier function that has the same effect as Y, but uses its own name
// this bootstraps recursion for all off of recursion for one.
func fixedPoint<S,T>(f:(S->T) -> (S->T)) -> (S->T) {
    return {
        (x : S) -> T in
        return f(fixedPoint(f))(x)
    }
}

let factorial2 = fixedPoint(almostFactorial)
println("\(factorial2(6))")