transducer-type.swift

import Foundation

// A bunch of convenience things
func const <A, B> (b: B) -> A -> B {
    return { _ in b }
}
func repeat <A> (n: Int) -> A -> [A] {
    return { a in
        return map(Array(1...n), const(a))
    }
}
infix operator |> {associativity left}
func |> <A, B> (x: A, f: A -> B) -> B {
    return f(x)
}
func |> <A, B, C> (f: A -> B, g: B -> C) -> A -> C {
    return { g(f($0)) }
}
func append <A> (xs: [A], x: A) -> [A] {
    return xs + [x]
}
func square (x: Int) -> Int {
    return x*x
}
func isPrime (p: Int) -> Bool {
    if p <= 1 { return false }
    if p <= 3 { return true }
    for i in 2...Int(sqrtf(Float(p))) {
        if p % i == 0 {
            return false
        }
    }
    return true
}
func incr (x: Int) -> Int {
    return x + 1
}


// Here's the good stuff

struct Transducer <A,B,R> {
    let step: (_: (R, A) -> R) -> (R, B) -> R
}

func composition<A,B,C,R>(lhs: Transducer<B,C,R>, rhs: Transducer<A,B,R>) -> Transducer<A,C,R> {
    return Transducer { reducer in
        lhs.step(rhs.step(reducer))
    }
}

func |> <A, B, R> (reducer: (R, A) -> R, transducer: Transducer<A, B,R>) -> (R, B) -> R {
    return transducer.step(reducer)
}

func |> <A, B, C, R> (lhs: Transducer<A, B, R>, rhs: Transducer<B, C, R>) -> Transducer<A, C, R> {
    return composition(rhs, lhs)
}

func map<B,A,R>(f: A -> B) -> Transducer<B,A,R> {
    return Transducer { reducer in
        { accum, a in
            reducer(accum, f(a))
        }
    }
}

func flatMap<B,A,R>(f: A -> [B]) -> Transducer<B,A,R> {
    return Transducer { reducer in
        { accum, a in
            return reduce(f(a), accum, reducer)
        }
    }
}

func filter<A,R>(p: A -> Bool) -> Transducer<A,A,R> {
    return Transducer { reducer in
        { accum, a in
            return p(a) ? reducer(accum, a) : accum
        }
    }
}


let xs = Array(1...100)
let result = reduce(xs, [], append
    |> flatMap(repeat(3))
    |> filter(isPrime)
    |> map(square |> incr)
)

let compositeTransducer: Transducer<Int,Int,Int> = flatMap(repeat(3)) |> filter(isPrime) |> map(square |> incr)
reduce(xs, 0, (+) |> compositeTransducer)