Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Swift Y Function
// 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.