Swift Y Function

Swift Y Function.swift

// We define a Y function such that we can use recursion within an anonymous closure

// Note that this function Y is not a combinator because it recursively refers to itself
// There's not much reason to have an actual combinator in Swift, so we're not going to
// worry about it, it's just as useful.

/*
 * Takes as input a function that takes in a function and returns a function of the same type
 * and returns a function of that return type by feeding that function back into itself
 * infinite times. Note that we use a closure to guard looping due to applicative order evaluation.
 * Esentially, Y(f) == f(f(f(f(f(...)))))
 */
func Y<T, R>( f: (T -> R) -> (T -> R) ) -> (T -> R) {
    return { t in f(Y(f))(t) }
}

// Now we can recurse within an anonymous closure by defining the closure as taking itself as input
// and using that function to recurse on. Then, you can call Y on such a closure to provide the
// function as its own input

// Examples

let factorial = Y {
    f in {
        x in x > 0 ? x * f(x - 1) : 1
    }
}

factorial(5) // -> 120

let fibbonacci = Y {
    f in {
        x in x > 1 ? f(x - 1) + f(x - 2) : 1
    }
}

fibbonacci(5) // -> 8
fibbonacci(6) // -> 13

let series = Y {
    f in {
        (x: Float) -> Float in x + ((x > 0) ? f(x / 2) : 0)
    }
}

series(1) // -> 2.0