Transducers & Reducers in Swift 2

transducers.swift

//-- This is an introduction to Transducers in Swift, inspired by
//   Talk: https://www.youtube.com/watch?v=estNbh2TF3E
//   Code: https://github.com/mbrandonw/learn-transducers-playground
//   Updated with Swift 2

/**
 * Define a few test methods
 */
/// REDUCER
func append <A> (xs: [A], x: A) -> [A] { return xs + [x] }
/// FILTERABLE
let isOdd : Int -> Bool = { $0 % 2 == 1 }
/// MAPPABLE
let incr  : Int -> Int  = { $0 + 1 }
let square: Int -> Int  = { $0 * $0 }


/**
 * Define operators: |>  <|  <<|
 */
infix operator |>  {associativity left}
infix operator <|  {associativity right}
infix operator <<| {associativity right}
// x |> f = f(x)
//--  apply f to x
func |> <A, B> (x: A, f: A -> B) -> B { return f(x) }
// f <| x = f(x)
//-- apply f to x (right associativity)
func <| <A, B> (f: A -> B, x: A) -> B { return f(x) }
// (f |> g)(x) = f(g(x))
//-- apply g to f of x
func |> <A, B, C> (f: A -> B, g: B -> C)(x: A) -> C { return g(f(x)) }
// (f <| g)(x) = g(f(x))
//-- apply f to g of x (right
func <| <A, B, C> (f: B -> C, g: A -> B)(x: A) -> C { return f(g(x)) }
// xs <<| transducer -> ys
//-- Improve syntax for chaining reducers
func <<| <A, B> (xs: [A], transducer: (([A], A) -> [A]) -> ([B], A) -> [B]) -> [B] {
    return xs.reduce([], combine: transducer(append))
}


/**
 * Build curried functions
 */
func map <A, B> (f: A -> B)    (xs: [A]) -> [B] { return xs.map(f)    } // (2 times)
func filter <A> (p: A -> Bool) (xs: [A]) -> [A] { return xs.filter(p) } // (1 time)
func reduce <A, B> (initial: B, reducer: (B, A) -> B)(xs: [A]) -> B {
    return xs.reduce(initial, combine: reducer)
}
func take <A> (n: Int)(xs: [A]) -> [A] {
    return xs.reduce([]) { acc, x in acc.count < n ? acc + [x] : acc } // (1001 times)
}


/**
 * Build functions using reducers
 */
func map <A, B, C> (f: A -> B)(reducer: (C, B) -> C)(acc: C, x: A) -> C {       // (2000 times)
    return reducer(acc, f(x))
}
func filter <A, C> (p: A -> Bool)(reducer: (C, A) -> C)(acc: C, x: A) -> C {    // (2001 times)
    return p(x) ? reducer(acc, x) : acc
}
func take <A, C> (n: Int)(reducer: ([C], A) -> [C])(acc: [C], x: A) -> [C] {    // (1000 times)
    return acc.count < n ? reducer(acc, x) : acc
}


/**
 * Let's test them out
 */

let xs = Array(0...2000)

//-- Using chained Standard Library functions
xs  |> filter(isOdd)
    |> map(incr)
    |> map(square)
    |> take(30)
/*
That required 4 passes of xs (one per function).
where:
  x => take limit
  n => xs.count
map     -> 2 times
filter  -> 1 time
take    -> 1001 times???
*/

//-- Using Transducers
xs <<| filter(isOdd)
    <| map(incr)
    <| map(square)
    <| take(30)
/*
That only required 1 pass of xs, calling each function on each value.
However, this is slower since our take function doesn't short circuit and
our Transducers are not as optimised as Apple's Standard Library functions.
where:
  x => take limit
  n => xs.count
map     -> n times
filter  -> n + 1 times
take    -> 1000 times
*/




/**
 * Let's build a short circuiting reduce
 */
enum Cir<T> {
    case Continue(T)
    case Shorted(T)
    var val: T {
        switch self {
        case .Shorted(let val):  return val
        case .Continue(let val): return val
        }
    }
    func attempt (f: T -> Cir<T>) -> Cir<T> {
        switch self {
        case .Shorted:           return self                // (1939 times)
        case .Continue(let val): return f(val)              // (185 times)
        }
    }
}
func short_append <A> (xs: Cir<[A]>, x: A) -> Cir<[A]> {    // (30 times)
    return xs.attempt { val in
        return .Continue(val + [x])
    }
}

/**
 * Define a new operator, again
 */
infix operator <<<| {associativity right}
func <<<| <A, B> (xs: [A], transducer: ((Cir<[A]>, A) -> Cir<[A]>) -> (Cir<[B]>, A) -> Cir<[B]>) -> [B] {
    return xs.reduce(Cir.Continue([]), combine: transducer(short_append)).val
}

/**
* Define the functions, again
* Note: Playgrounds had a hard time using type inference to pick the right
*       function, so I've rename severything :)
*/
func shortMap <A, B, C> (f: A -> B) (reducer: (Cir<C>, B) -> Cir<C>) (acc: Cir<C>, x: A) -> Cir<C> {    // (62 times)
    return acc.attempt { _ in
        return reducer(acc, f(x))
    }
}
func shortFilter <A, C> (p: A -> Bool) (reducer: (Cir<C>, A) -> Cir<C>) (acc: Cir<C>, x: A) -> Cir<C> { // (2001 times)
    return acc.attempt { _ in
        return p(x) ? reducer(acc, x) : acc                                                             // (62 times)
    }
}
func shortTake <A, C> (n: Int) (reducer: (Cir<[C]>, A) -> Cir<[C]>) (acc: Cir<[C]>, x: A) -> Cir<[C]> { // (31 times)
    return acc.attempt { val in
        return (val.count < n)
            ? reducer(acc, x)
            : .Shorted(val)
    }
}

//-- Using short circuiting
xs <<<| shortFilter(isOdd)
     <| shortMap(incr)
     <| shortMap(square)
     <| shortTake(30)
/*
where:
  x => take limit
  n => xs.count
map     -> 2(x + 1) times
filter  -> n + 1 times
take    -> x + 1 times
*/