How to get a transducer type without higher kinds

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

class Transducer <A, B> {
  func step <R> (_: (R, A) -> R) -> (R, B) -> R {
    fatalError("should be overriden")
  }
}

class CompositionTransducer <A, B, C> : Transducer <A, C> {
  let lhs: Transducer<B, C>
  let rhs: Transducer<A, B>

  init (_ lhs: Transducer<B, C>, _ rhs: Transducer<A, B>) {
    self.lhs = lhs
    self.rhs = rhs
  }

  override func step <R> (reducer: (R, A) -> R) -> (R, C) -> R {
    return self.lhs.step(self.rhs.step(reducer))
  }
}

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

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

class Mapping <B, A> : Transducer <B, A> {
  let f: A -> B
  init(_ f: A -> B) {
    self.f = f
  }

  override func step <R> (reducer: (R, B) -> R) -> (R, A) -> R {
    return { accum, a in
      return reducer(accum, self.f(a))
    }
  }
}

class FlatMapping <B, A> : Transducer <B, A> {
  let f: A -> [B]
  init(_ f: A -> [B]) {
    self.f = f
  }

  override func step <R> (reducer: (R, B) -> R) -> (R, A) -> R {
    return { accum, a in
      return reduce(self.f(a), accum, reducer)
    }
  }
}

class Filtering <A> : Transducer <A, A> {
  let p: A -> Bool
  init (_ p: A -> Bool) {
    self.p = p
  }

  override func step <R> (reducer: (R, A) -> R) -> (R, A) -> R {
    return { accum, a in
      return self.p(a) ? reducer(accum, a) : accum
    }
  }
}


let xs = Array(1...100)
reduce(xs, [], append
  |> FlatMapping(repeat(3))
  |> Filtering(isPrime)
  |> Mapping(square |> incr)
)


let compositeTransducer = FlatMapping(repeat(3)) |> Filtering(isPrime) |> Mapping(square |> incr)
reduce(xs, 0, (+) |> compositeTransducer)

😎

Hi Brandon, intellectually, I love your construction with transducers. But, if you want only to solve the last problem you give as an example, maybe you could keep it simple? Like this:

3 * reduce(xs, 0) { acc, x in
let elem = x * x + 1
return isPrime(elem) ? acc + elem : acc
}

I don't think we miss in readability ...

@ThierryDarrigrand: totally, my example was contrived.