Last active
January 13, 2019 13:41
-
-
Save rjchatfield/14e2869b0c572696ea3c to your computer and use it in GitHub Desktop.
Transducers & Reducers in Swift 2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //-- 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 | |
| */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Very interesting. I suggest to replace:
let isOdd : Int -> Bool = { $0 % 2 == 1 }
by:
let isOdd : Int -> Bool = { $0 % 2 != 0 }
in order to make isOdd compatible with negative integers.