Skip to content

Instantly share code, notes, and snippets.

@lldong
Created January 5, 2015 05:57
Show Gist options
  • Save lldong/756df02479395a2d183d to your computer and use it in GitHub Desktop.
Save lldong/756df02479395a2d183d to your computer and use it in GitHub Desktop.
Church Numerals in Swift
// Playground - noun: a place where people can play
import UIKit
func zero<N>(succ: N -> N) -> N -> N {
return { (z: N) in
return z
}
}
func one<N>(succ: N -> N) -> N -> N {
return { (z: N) in
return succ(z)
}
}
func two<N>(succ: N -> N) -> N -> N {
return { (z: N) in
return succ(succ(z))
}
}
func three<N>(succ: N -> N) -> N -> N {
return { (z: N) in
return succ(succ(succ(z)))
}
}
func int2Church<N>(n: Int) -> (N -> N) -> N -> N {
if n == 0 {
return zero
}
return { (succ: (N -> N)) -> N -> N in
return { (z: N) -> N in
return succ(int2Church(n - 1)(succ)(z))
}
}
}
func church2Int<N>(n: (Int -> Int) -> Int-> N) -> N {
return n({$0 + 1})(0)
}
func plus<N>(a: (N -> N) -> N -> N)-> ((N -> N) -> N -> N) -> (N -> N) -> N -> N {
return { (b: (N -> N) -> N -> N) in
return { (succ: N -> N) in
return { (z: N) in
return a(succ)(b(succ)(z))
}
}
}
}
church2Int(plus(one)(two))
func mult<N>(a: (N -> N) -> N -> N) -> ((N -> N) -> N -> N) -> (N -> N) -> N -> N {
return { (b: (N -> N) -> N -> N) in
return { (succ: (N -> N)) -> N -> N in
return { (z: N) -> N in
return a(b(succ))(z)
}
}
}
}
church2Int(mult(two)(three))
func pow<A, B, C>(a : A) -> (A -> B -> C -> C) -> B -> C -> C {
return { (b : (A -> B -> C -> C)) -> B -> C -> C in
return { (succ : B) -> C -> C in
return { (z : C) -> C in
return b(a)(succ)(z)
}
}
}
}
church2Int(pow(two)(three))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment