Created
October 1, 2019 05:37
-
-
Save raymondtay/e09f23e8301ba5622d214079aff054f8 to your computer and use it in GitHub Desktop.
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
// The type of the transducer function happens to resemble the folding function | |
// you would normally pass to `foldLeft` or `foldRight`. Here's an example | |
// using the following: | |
// {{{ | |
// val xs = List("1", "2", "3") | |
// scala> xs.foldLeft | |
// override def foldLeft[B](z: B)(op: (B, String) => B): B | |
// }}} | |
// | |
// The type of `op` is exactly that of the type `RF` - what a coincidence ! | |
// When you look at the example usage of the transducers, you will notice that | |
// the value of `z` is 0 which means `op` is really (Int, String) => Int and | |
// this coincides with | |
// {{{ | |
// scala> parseInt ∘ repeat ∘ twice | |
// res10: Transducer[Int,String] = Transducer$$anon$2@54baa9be | |
// because its really just (R, Int) => R ∘ (R, String) => R | |
// }}} | |
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]) = (r, a) => rf(r, f(a)) // this is similar to the `map` function | |
} | |
} | |
import Transducer.RF | |
// Conceptually, the `apply` is a transformation function which takes a | |
// reduction function and transforms its value of type `A` to `B` i.e. | |
// (R, A) => R <+> (R, B) => R where <+> is my notation for transformation. | |
// | |
// | |
//`that` is of type (R, Z) => R <+> (R, A) => R | |
// `rf` is of type (R, Z) => R which means (that(rf)) : (R, A) => R | |
// and self(that(rf)) : (R, B) => R because "self" refers to the smart | |
// constructor of type (R, A) => R | |
trait Transducer[A,B] { self => | |
// the map function is not defined yet but you know its going to be there | |
// because there needs to be a function that transforms A => B. | |
def apply[R](rf : RF[R, A]) : RF[R, B] | |
// compose-function | |
def ∘ [Z](that: Transducer[Z, A]) = | |
new Transducer[Z, B] { | |
def apply[R](rf: RF[R, Z]) = self(that(rf)) | |
} | |
} | |
object Test extends App { | |
val parseInt = Transducer((s: String) => s.toInt) | |
val twice = Transducer((i: Int) => i * 2) | |
/** | |
* scala> Test.main(Array()) | |
* Incoming => 1, 0, 2 | |
* Incoming => 2, 4, 8 | |
* Incoming => 3, 12, 18 | |
* */ | |
def repeat[A] = | |
new Transducer[A,A] { | |
def apply[R](rf: RF[R,A]) = (r, a) => { | |
println(s"Incoming => $a, $r, ${rf(r, a)}") | |
rf(rf(r, a), a) | |
} | |
} | |
val xs = List("1", "2", "3") | |
// val result = | |
// xs.foldLeft(0)(parseInt(_ + _)) | |
// println(result) | |
val result2 = | |
xs.foldLeft(0)((parseInt ∘ repeat ∘ twice)(_ + _)) | |
println(result2) | |
} | |
/** | |
* Here's how we can achieve the equivalent using Functors | |
* in Cats | |
* scala> val parseInt = Functor[Id].lift((s: String) => s.toInt) | |
* parseInt: cats.Id[String] => cats.Id[Int] = $$Lambda$2281/1768175008@4c68b72d | |
* | |
* scala> val twice = Functor[Id].lift((x:Int) => x * 2) | |
* twice: cats.Id[Int] => cats.Id[Int] = $$Lambda$2291/478942543@5f670485 | |
* | |
* scala> xs.foldLeft(0)((acc,e) => acc + twice.compose(parseInt)(e)) | |
* res10: Int = 12 | |
* | |
* scala> xs.foldLeft(0)((acc,e) => acc + twice.compose(twice.compose(parseInt))(e)) | |
* res11: Int = 24 | |
* | |
*/ | |
// Comparing to both approaches, the transducers abstraction does have its | |
// beauty w.r.t 2 things: | |
// (a) the reducing function in transducers is more readable, by how much? | |
// depends on the reader. | |
// (b) transducers is generic | |
// (c) the machinery of the reduction can be tested |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment