Uncategorized Swift

A YCombinator Implementation in Swift

Definition: A Y Combinator is a pattern allowing a non-recursive functional implementation of a recursive function.

It is not particularly useful: a trivial recursive implementation requires half of the computation cost required by a Y Combinator.

That is so much easier compared to the Y-Combinator pattern!

What is the use of this thing?
Absolutely None; I did this thing two years ago for fun. I tried some of the approaches from the Rosetta Code, and they didn’t work anymore in modern Swift.
I solved this puzzle just for fun. This version correctly declares escaping closures and handles the Swift syntax correctly.
Swift is pedantic; this code is much simpler in Haskell, but we don’t program iPhones in Haskell, do we? Well, Haskell does have quite an advantage on Swift when it comes to clarity about functional approaches.

Here is my implementation in Swift, tested on Swift 5.7 in Xcode 12.4, on a Swift Playground:

import Foundation

struct RecursiveFunc<T> {
    let o : (RecursiveFunc<T>) -> T
}

func Y<A, B>(f: @escaping (@escaping (A)  -> B)  -> (A) -> B) -> (A) -> B {
    let r = RecursiveFunc<(A) -> B> {  w in f { w.o(w)($0) } }
  return r.o®
}

// defining factorial with Y-Combinator
let fac = Y { (f: @escaping (Int) -> Int) in
  { $0 <= 1 ? 1 : $0 * f($0-1) }
}

// traditional recursive implementation of a Factorial
func fact (_ n: Int) -> Int {
    if n == 0 { return 1 }
    else { return n * fact (n-1) }
}

print (fact(19))
print (fac (19))


Leave a Reply

Your email address will not be published. Required fields are marked *