Skip to content

Instantly share code, notes, and snippets.

@kongtomorrow
Last active August 31, 2022 16:20
Show Gist options
  • Save kongtomorrow/e95bea13162ca0e29d4b to your computer and use it in GitHub Desktop.
Save kongtomorrow/e95bea13162ca0e29d4b to your computer and use it in GitHub Desktop.
Y combinator in 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))")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment