Skip to content

Instantly share code, notes, and snippets.

@mayonesa
Created July 14, 2019 01:31
Show Gist options
  • Save mayonesa/ef5706683bcc225c3bac2113962505e0 to your computer and use it in GitHub Desktop.
Save mayonesa/ef5706683bcc225c3bac2113962505e0 to your computer and use it in GitHub Desktop.
Monoids, Functional Programming in Scala
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}
val intAddition = new Monoid[Int] {
def op(int1: Int, int2: Int) = int1 + int2
def zero = 0
}
val intMultiplication = new Monoid[Int] {
def op(int1: Int, int2: Int) = int1 * int2
def zero = 1
}
val booleanOr = new Monoid[Boolean] {
def op(b1: Boolean, b2: Boolean) = b1 || b2
def zero = false
}
val booleanAnd = new Monoid[Boolean] {
def op(b1: Boolean, b2: Boolean) = b1 && b2
def zero = true
}
def endoMonoid[A]: Monoid[A => A] =
new Monoid[A => A] {
def op(x: A => A, y: A => A) = x andThen y
val zero: A => A = identity
}
def dual[A](m: Monoid[A]) = new Monoid[A] {
def op(a1: A, a2: A) = m.op(a2, a1)
def zero = m.zero
}
def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B =
as.foldLeft(m.zero)((b, a) => m.op(b, f(a)))
def foldLeft[A, B](as: List[A])(z: B)(f: (B, A) => B): B = {
val mb = new Monoid[B] {
def op(b1: B, b2: B): B = b1 b2
val zero: B = z
}
foldMap(as, mb)(f)
}
def foldMapV[A, B](v: Seq[A], m: Monoid[B])(f: A => B): B = {
def loop(u: Seq[A]): B =
if (u.isEmpty)
m.zero
else if (u.size == 1)
f(u(0))
else {
val (l, r) = u.splitAt(u.size / 2)
m.op(loop(l), loop(r))
}
loop(v)
}
def ordered(v: Seq[Int]): Boolean =
foldMapV(v, new Monoid[(Int, Boolean)] {
def op(ib0: (Int, Boolean), ib1: (Int, Boolean)) = {
val (i0, b0) = ib0
val (i1, b1) = ib1
println(s"$b0 && $i0 <= $i1, $b1")
(i1, b1 && i0 <= i1)
}
val zero = (Int.MinValue, true)
})((_, true))._2
sealed trait WC
case class Stub(chars: String) extends WC
case class Part(lStub: String, nWords: Int, rStub: String) extends WC
val wcMonoid = new Monoid[WC] {
def op(a: WC, b: WC) =
(a, b) match {
case (Stub(a0), Stub(b0)) => Stub(a0 + b0)
case (Stub(a0), Part(l, wc, r)) => Part(a0 + l, wc, r)
case (Part(l, wc, r), Stub(b0)) => Part(l, wc, r + b0)
case (Part(la, wca, ra), Part(lb, wcb, rb)) => Part(la, wca + (if ((ra + lb).isEmpty) 0 else 1) + wcb, rb)
}
val zero = Stub("")
}
def count(s: String): Int =
foldMapV(s.toIndexedSeq, wcMonoid) { c: Char =>
if (c.isWhitespace) Part("", 0, "")
else Stub(c.toString)
} match {
case Stub(a) => stubVal(a)
case Part(a, wc, b) => stubVal(a) + wc + stubVal(b)
}
def stubVal(s: String) = s.size min 1
trait Foldable[F[_]] {
def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B = foldMap(as)(f.curried)(endoMonoid[B])(z)
def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B = foldMap(as)(a => (b: B) => f(b, a)))(dual(endoMonoid[B]))(z)
def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B
def concatenate[A](as: F[A])(ma: Monoid[A]): A = foldLeft(as)(ma.zero)(ma.op)
}
val foldableList = new Foldable[List] {
def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B =
def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B
def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B
}
def functionMonoid[A, B](bMonoid: Monoid[B]): Monoid[A => B] =
new Monoid[A => B] {
def op(f: A => B, g: A => B): A => B = a => bMonoid.op(f(a), g(a))
def zero: A => B = _ => bMonoid.zero
}
def bag[A](as: IndexedSeq[A]): Map[A, Int] = foldMapV(as, mapMergeMonoid(intAddition))(Map(_ -> 1))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment