Y combinator in Swift

ycombinator.swift

// You can have a recursive function
func fact(n: Int) -> Int {
  if n < 2 { return 1 }
  return n * fact(n - 1)
}

// But you cannot have a recursive closure
// let fact2: Int -> Int = { n in
//   if n < 2 { return 1 }
//   return n * fact2(n - 1) // ERROR: Variable used within its own initial value
// }

// You can use an implicit unwrapped optional, and create it
// in two steps. But you need to use a var, so it is 
// reassignable.
var fact3 : (Int -> Int)!
fact3 = { n in
  if n < 2 { return 1 }
  return n * fact3(n - 1) // no error
}

// But you can also build the Y combinator (using the same trick inside with
// the implicit unwrapped optional)
func Y<A,B>(y: (A -> B) -> (A -> B)) -> (A -> B) {
  var yy: (A -> B)!
  yy = y { yy($0) }
  return yy
}

// And create your closure receiving itself in one step
let factY: Int -> Int = Y { f in
  return { n in
    if (n < 2) { return 1 }
    return n * f(n - 1)
  }
}