Basic encoding of Transducers with a little fanciness

transducers2.scala

import spire.algebra._
import spire.implicits._

object Transducer {
  type RF[R, A] = (R, A) => R

  def apply[A, B](f: A => B) =
    new Transducer[B, A] {
      def apply[R](rf: RF[R, B]): RF[R, A] = (r, a) => rf(r, f(a))
    }

  object Skip extends Exception with scala.util.control.NoStackTrace
  object Halt extends Exception with scala.util.control.NoStackTrace

  trait TransducedOps[A, B] {
    def fold[R](init: R)(rf: RF[R, B]): R

    import scala.collection.generic.CanBuildFrom

    def to[CC[_]](implicit cbf: CanBuildFrom[CC[B], B, CC[B]]): CC[B] =
      fold(cbf())(_ += _).result
    def reduce(implicit B: Monoid[B]): B =
      fold(B.id)(_ |+| _)
    def sum(implicit B: AdditiveMonoid[B]): B =
      fold(B.zero)(_ + _)
    def product(implicit B: MultiplicativeMonoid[B]): B =
      fold(B.one)(_ * _)
  }

  class Transduced[A, B](as: TraversableOnce[A], t: Transducer[B, A]) extends TransducedOps[A, B] {
    def fold[R](init: R)(rf: RF[R, B]): R =
      as.foldLeft(init)(t(rf))
  }

  class TransducedC[A, B](as: TraversableOnce[A], t: Transducer[B, A]) extends TransducedOps[A, B] {
    def fold[R](init: R)(rf: RF[R, B]): R = {
      val it = as.toIterator
      val f: RF[R, A] = t(rf)
      var res: R = init
      while (it.hasNext) {
        try {
          res = f(res, it.next)
        } catch {
          case _: Skip.type => ()
          case _: Halt.type => return res
        }
      }
      res
    }
  }

  implicit class TransducerOps[A](val as: TraversableOnce[A]) extends AnyVal {
    def transduce[B](t: Transducer[B, A]) = new Transduced(as, t)
    def transduceC[B](t: Transducer[B, A]) = new TransducedC(as, t)
  }
}

import Transducer.{RF, Halt, Skip, TransducerOps}

trait Transducer[A, B] { self =>

  def apply[R](f: RF[R, A]): RF[R, B]

  def andThen[C](that: Transducer[B, C]): Transducer[A, C] =
    that compose this

  def ∘[Z](that: Transducer[Z, A]): Transducer[Z, B] =
    this compose that

  def compose[Z](that: Transducer[Z, A]): Transducer[Z, B] =
    new Transducer[Z, B] {
      def apply[R](rf: RF[R, Z]): RF[R, B] = self(that(rf))
    }

  def map1[Z](f: A => Z): Transducer[Z, B] =
    new Transducer[Z, B] {
      def apply[R](rf: RF[R, Z]): RF[R, B] =
        self((r, a) => rf(r, f(a)))
    }

  def contramap2[C](f: C => B): Transducer[A, C] =
    new Transducer[A, C] {
      def apply[R](rf: RF[R, A]): RF[R, C] = {
        val g = self(rf)
        (r, c) => g(r, f(c))
      }
    }
}

object Test {
  val parseI = Transducer((s: String) => s.toInt)
  val reversed = Transducer((s: String) => s.reverse)
  val root2 = Transducer((n: Int) => math.pow(2.0, 1.0 / n))

  def lessThan(x: Int) = Transducer { (n: Int) => 
    if (n < x) n else throw Skip
  }

  def until(x: Int) = Transducer { (n: Int) => 
    if (n != x) n else throw Halt
  }

  def repeat[A] =
    new Transducer[A, A] {
      def apply[R](rf: (R, A) => R): (R, A) => R =
        (r, a) => rf(rf(r, a), a)
    }

  def main(args: Array[String]) {
    val lst = List("1","2","3")
    println(lst.transduce(parseI).sum)
    println(lst.transduce(parseI ∘ repeat ∘ root2).sum)
    println(lst.transduce(repeat ∘ repeat).reduce)
    println(lst.transduce(reversed).to[List])
    println(lst.transduce(reversed).to[Vector])

    val nil = List.empty[Int]
    println((1 to 10).transduceC(lessThan(5)).to[List])
    println((1 to 10).transduceC(lessThan(5)).sum)

    val ns = List(1,3,5,3,1,3,5,3,1)
    println(ns.transduceC(until(5)).to[List])
    println(ns.transduceC(lessThan(5)).to[List])
  }
}