Last active
December 10, 2015 02:18
-
-
Save tonymorris/4366536 to your computer and use it in GitHub Desktop.
foldMap is equivalent to scala.List
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
trait Semigroup[A] { | |
def op(a1: A, a2: A): A | |
} | |
trait Monoid[A] extends Semigroup[A] { | |
def id: A | |
} | |
object Monoid { | |
implicit def ListMonoid[A]: Monoid[List[A]] = | |
new Monoid[List[A]] { | |
def op(a1: List[A], a2: List[A]) = | |
a1 ::: a2 | |
def id = | |
Nil | |
} | |
} | |
// foldMap is isomorphic to scala.List | |
trait FMList[A] { | |
def foldMap[B](f: A => B)(implicit M: Monoid[B]): B | |
def ::(a: A): FMList[A] = | |
new FMList[A] { | |
def foldMap[B](f: A => B)(implicit M: Monoid[B]) = | |
M.op(f(a), FMList.this.foldMap(f)) | |
} | |
def +:(a: A): FMList[A] = | |
new FMList[A] { | |
def foldMap[B](f: A => B)(implicit M: Monoid[B]) = | |
M.op(FMList.this.foldMap(f), f(a)) | |
} | |
def :::(a: FMList[A]): FMList[A] = | |
new FMList[A] { | |
def foldMap[B](f: A => B)(implicit M: Monoid[B]) = | |
M.op(a.foldMap(f), FMList.this.foldMap(f)) | |
} | |
def filter(p: A => Boolean): FMList[A] = | |
new FMList[A] { | |
def foldMap[B](f: A => B)(implicit M: Monoid[B]) = | |
FMList.this.foldMap(x => if(p(x)) f(x) else M.id) | |
} | |
def map[X](q: A => X): FMList[X] = | |
new FMList[X] { | |
def foldMap[B](f: X => B)(implicit M: Monoid[B]) = | |
FMList.this.foldMap(f compose q) | |
} | |
def flatMap[X](q: A => FMList[X]): FMList[X] = | |
new FMList[X] { | |
def foldMap[B](f: X => B)(implicit M: Monoid[B]) = | |
FMList.this.foldMap(q(_) foldMap f) | |
} | |
def toScalaList: List[A] = | |
foldMap(List(_)) | |
override def toString: String = | |
"FM" + toScalaList.toString | |
} | |
object FMList { | |
def nil[A]: FMList[A] = | |
new FMList[A] { | |
def foldMap[B](f: A => B)(implicit M: Monoid[B]) = | |
M.id | |
} | |
def single[A](a: A): FMList[A] = | |
new FMList[A] { | |
def foldMap[B](f: A => B)(implicit M: Monoid[B]) = | |
f(a) | |
} | |
def fromScalaList[A](a: List[A]): FMList[A] = | |
a.foldRight[FMList[A]](nil)(_ :: _) | |
} | |
case class ~>[R, A](run: (A => R) => R) { | |
def map[B](f: A => B): R ~> B = | |
~>(g => run(g compose f)) | |
def flatMap[B](f: A => (R ~> B)): R ~> B = | |
~>(g => run(f(_) run g)) | |
} | |
object ~> { | |
def pure[R, A](a: A): R ~> A = | |
~>(_(a)) | |
def constant[R, A](r: => R): R ~> A = | |
~>(_ => r) | |
} | |
// fold is isomorphic to scala.List | |
trait FList[A] { | |
def fold[R](implicit M: Monoid[R]): R ~> A | |
def ::(a: A): FList[A] = | |
new FList[A] { | |
def fold[R](implicit M: Monoid[R]) = | |
~>(f => M.op(f(a), FList.this.fold run f)) | |
} | |
def +:(a: A): FList[A] = | |
new FList[A] { | |
def fold[R](implicit M: Monoid[R]) = | |
~>(f => M.op(FList.this.fold run f, f(a))) | |
} | |
def :::(a: FList[A]): FList[A] = | |
new FList[A] { | |
def fold[R](implicit M: Monoid[R]) = | |
~>(f => M.op(a.fold run f, FList.this.fold run f)) | |
} | |
def filter(p: A => Boolean): FList[A] = | |
new FList[A] { | |
def fold[R](implicit M: Monoid[R]) = | |
~>(f => FList.this.fold run (x => if(p(x)) f(x) else M.id)) | |
} | |
def map[X](q: A => X): FList[X] = | |
new FList[X] { | |
def fold[R](implicit M: Monoid[R]) = | |
~>(f => FList.this.fold run (f compose q)) | |
} | |
def flatMap[X](q: A => FList[X]): FList[X] = | |
new FList[X] { | |
def fold[R](implicit M: Monoid[R]) = | |
~>(f => FList.this.fold run (q(_).fold run f)) | |
} | |
def toScalaList: List[A] = | |
fold[List[A]].run(List(_)) | |
override def toString: String = | |
"F" + toScalaList.toString | |
} | |
object FList { | |
def nil[A]: FList[A] = | |
new FList[A] { | |
def fold[R](implicit M: Monoid[R]) = | |
~>.constant(M.id) | |
} | |
def single[A](a: A): FList[A] = | |
new FList[A] { | |
def fold[R](implicit M: Monoid[R]) = | |
~>(_(a)) | |
} | |
def fromScalaList[A](a: List[A]): FList[A] = | |
a.foldRight[FList[A]](nil)(_ :: _) | |
} | |
object Main { | |
def step[A](a: A): A = { | |
println(a) | |
a | |
} | |
def main(args: Array[String]) { | |
val flist0: FList[Int] = FList.nil | |
val flist1 = 3 :: flist0 | |
val flist2 = 1 :: 2 :: flist1 | |
val flist3 = flist2 map (_ * 2) | |
val flist4 = flist3 ::: (40 :: 50 :: 60 :: FList.nil) | |
val flist5 = flist4 filter (x => x / 10 % 2 == 0) | |
val flist6 = flist5.flatMap(x => x :: x + 200 :: FList.nil) | |
val fmlist0: FMList[Int] = FMList.nil | |
val fmlist1 = 3 :: fmlist0 | |
val fmlist2 = 1 :: 2 :: fmlist1 | |
val fmlist3 = fmlist2 map (_ * 2) | |
val fmlist4 = fmlist3 ::: (40 :: 50 :: 60 :: FMList.nil) | |
val fmlist5 = fmlist4 filter (x => x / 10 % 2 == 0) | |
val fmlist6 = fmlist5.flatMap(x => x :: x + 200 :: FMList.nil) | |
List( | |
flist0 | |
, flist1 | |
, flist2 | |
, flist3 | |
, flist4 | |
, flist5 | |
, flist6 | |
, flist6.toScalaList | |
, fmlist0 | |
, fmlist1 | |
, fmlist2 | |
, fmlist3 | |
, fmlist4 | |
, fmlist5 | |
, fmlist6 | |
, fmlist6.toScalaList | |
) foreach println | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment