Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Lambda Calculus in Swift
//
// main.swift
// church
//
// Created by Dan Kogai on 6/15/14.
// Copyright (c) 2014 Dan Kogai. All rights reserved.
//
/* Operators */
// SUCC := λnfx.f (n f x)
// ((t1 -> t) -> t2 -> t1) -> (t1 -> t) -> t2 -> t
func succ<T1,T,T2>(n:(T1->T)->T2->T1)->(T1->T)->T2->T {
return {(f:T1->T)->T2->T in {(x:T2)->T in f(n(f)(x))}}
}
// ADD := λm n f x. m f (n f x)
// (t2 -> t1 -> t) -> (t2 -> t3 -> t1) -> t2 -> t3 -> t
func add<T2,T1,T,T3>(m:T2->T1->T)->(T2->T3->T1)->T2->T3->T {
return {(n:T2->T3->T1)->T2->T3->T in
{(f:T2)->T3->T in {(x:T3)->T in m(f)(n(f)(x))}}}
}
// MUL := λm n f. m (n f)
// (t1 -> t) -> (t2 -> t1) -> t2 -> t
func mul<T1,T,T2>(m:T1->T)->(T2->T1)->T2->T {
return {(n:T2->T1)->T2->T in {(f:T2)->T in m(n(f))}}
}
// POW
// t1 -> (t1 -> t) -> t
func pow<T1,T>(m:T1)->(T1->T)->T {
return {(n:T1->T)->T in n(m)}
}
// 0
func c0<T>(f:(T)->T)->(T)->T {
return {(x:T)->T in x}
}
// 1
func c1<T>(f:(T)->T)->(T)->T {
// return {(x:T)->T in f(x)}
return {(x:T)->T in succ(c0)(f)(x)}
}
// 2
func c2<T>(f:(T)->T)->(T)->T {
// return {(x:T)->T in f(f(x))}
return {(x:T)->T in succ(c1)(f)(x)}
}
// 3
func c3<T>(f:(T)->T)->(T)->T {
// return {(x:T)->T in f(f(x))}
return {(x:T)->T in add(c1)(c2)(f)(x)}
}
// see if it works
let v = succ(succ(mul(add(c2)(c3))(pow(c2)(c3))))({x in x+1})(0)
println(v)
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.