FP examples in Swift

fp.swift

// Just spending Saturday afternoon rewriting FP examples from Backus in Swift.
// http://worrydream.com/refs/Backus-CanProgrammingBeLiberated.pdf
//
// Surprising fact: reasonably possible with only one major problem (tuples are not collections)
// Unsurprising fact: you shouldn't write Swift this way
// Other unsurprising fact: Rob should probably get out more
// Don't judge me

// For future research: is it possible to build this without arrayFormHack and the arity 2 ∘?
// Basically, can we do this entirely with tuples or entirely with arrays? Currently almost everything
// is an array (with un-checked lengths), because otherwise things like 𝛼 and distr require
// an overload for every vector length. But distl can't easily be an array, since it's not homogeneous.
// In the matrix multiplication example, distr takes <vector,matrix>

// Making everything generic forces us to do some explicit typing we wouldn't otherwise have to,
// but it's nice to show that it works. If "A" were locked to "Int" then some of the code could be a 
// little closer to FP.
typealias Vector<A> = [A]
typealias Matrix<A> = [Vector<A>]

//
// Operations
//

// Application. 11.2.2. FP: :
infix operator ∶ { associativity right } // Note: this is RATIO, not COLON (COLON can't be an operator).
func ∶ <A,B> (f: (A) -> B, x: A) -> B {
    return f(x)
}

//
// Functions 11.2.3
//

// Selector (startIndex=1). FP: 1
func sel<A>(_ n: Int) -> ([A]) -> A {
    return { $0[n - 1] }
}

// Identity
func id<A>(x: A) -> A { return x }

// Equals
func eq <A: Equatable>(x: [A]) -> Bool {
    return x[0] == x[1]
}

// Distribute from left. (Note arity 2.)
func distl<A,B>(x: (A,[B])) -> [(A,B)] {
    return x.1.map { (x.0, $0) }
}

// Distribute from right. (Note arity 2.)
func distr<A,B>(x: ([A],B)) -> [(A,B)] {
    return x.0.map { ($0, x.1) }
}

// Arithmetic
prefix operator + {}
prefix func + <A: IntegerArithmetic>(x: [A]) -> A {
    return x[0] + x[1]
}

prefix operator - {}
prefix func - <A: IntegerArithmetic>(x: [A]) -> A {
    return x[0] - x[1]
}

prefix operator * {}
prefix func * <A: IntegerArithmetic>(x: [A]) -> A {
    return x[0] * x[1]
}

// Transpose
func trans<A>(rows: Matrix<A>) -> Matrix<A> {
    return rows.first!.indices.map { colIndex in
        rows.map { $0[colIndex] }
    }
}

//
// Functional Forms 11.2.4
//

// Compose. The arity handlers are so that we can pass tuples for Construct
// We usually use arrays for Construct, but then mixed types, like in distr, are difficult
infix operator ∘ { precedence 10 associativity left }
func ∘ <A,B,C>(f: (B) -> C, g: (A) -> B) -> (A) -> C { // Arity 1
    return { f(g($0)) }
}

func ∘ <A, B, C, D> (f: (B, C) -> D, g: ((A) -> B, (A) -> C)) -> (A) -> D { // Arity 2
    return { f(g.0($0), g.1($0)) }
}

// Construction. FP: []
func cons<A,B>(_ fs: [(A) -> B]) -> (A) -> [B] {
    return { x in fs.map { $0(x) } }
}

// Condition
infix operator ⟶ { associativity left }
func ⟶ (predicate: (Int) -> Bool, result: (ifTrue: (Int) -> Int, ifFalse: (Int) -> Int)) -> (Int) -> Int {
    return { x in predicate(x) ? result.ifTrue(x) : result.ifFalse(x) }
}

// Constant. FP: overbar x̅
func constant<A, B>(_ x: A) -> (B) -> A { return { _ in x } }

// Insert
prefix operator / {}
prefix func /<A>(f: (A, A) -> A) -> ([A]) -> A {
    return { $0.dropFirst().reduce($0.first!, combine: f) }
}

// Apply to all. (Wish this could be an operator.)
func 𝛼 <A,B>(_ f: (A) -> B) -> ([A]) -> [B] {
    return { $0.map(f) }
}

//
// Swift-related hacks
//
// Recursion helper. Delays instantiation until evalution. See Factorial.
func recurse<A, B>(_ f: () -> (A) -> B) -> (A) -> B {
    return { x in f()(x) }
}

// Convert from 2-tuples to arrays
func arrayFormHack<A>(x: [(A, A)]) -> [[A]] {
    return x.map { z in [z.0, z.1] }
}

//
// EXAMPLES 11.3
//

//
// Factorial. 11.3.1 (Who says you can't have recursive closures in Swift?)
//

let fact: (Int) -> Int = {
    let eq0 = eq ∘ cons∶[id, constant(0)]
    let sub1 = (-) ∘ cons∶[id, constant(1)]
    func factF() -> (Int) -> Int {
        return eq0 ⟶ (constant∶1, (*) ∘ cons∶[id, recurse∶factF ∘ sub1])
    }
    return factF()
}()

print(fact∶4)


//
// Inner Product 11.3.2
//

// Swift doesn't have higher-kinded types. dotProduct can't be generic, so we need to specify a type here. (See below)
let IP: ([Vector]) -> Int = /(+) ∘ 𝛼(*) ∘ trans

let a = [1,2,3]
let b = [6,5,4]

print(IP∶[a, b])

// We can create an "innerProduct factory" that will build it generically, but the calling syntax is awkward: f()∶[a,b]
func innerProductF<A: IntegerArithmetic>() -> ([[A]]) -> A { return /(+) ∘ 𝛼(*) ∘ trans }
print(innerProductF()∶[a,b])


//
// Matrix multiply 11.3.3
//

let A = [[1,2,3], [3,2,1], [2,1,3]]
let B = [[4,5,6], [6,5,4], [4,6,5]]
// result: [[28,33,29], [28,31,31], [26,33,31]]

let MM: ([Matrix<Int>]) -> Matrix = 𝛼∶𝛼∶IP ∘ 𝛼∶arrayFormHack ∘ 𝛼∶distl ∘ distr ∘ (sel∶1, trans ∘ sel∶2)
print(MM∶[A,B])