Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Reworked and explanded UMP presentation and Scala Cats examples of free monoids
import cats._
import cats.implicits._
import org.scalacheck.Prop.forAll
// Reworked and explanded UMP presentation and examples http://eed3si9n.com/herding-cats/Free-monoids.html that is inconsistent
object FoldMapExp extends App {
// Prep work: define a monoid of integers modulo 2
case class IntMod2 private(unwrap: Int) extends AnyVal {
override def toString = s"IntMod2($unwrap)"
}
object IntMod2 {
@inline def apply(b: Int): IntMod2 = new IntMod2(b % 2)
implicit val intMod2Monoid: Monoid[IntMod2] = new Monoid[IntMod2] {
def combine(a1: IntMod2, a2: IntMod2): IntMod2 =
IntMod2(a1.unwrap + a2.unwrap)
def empty: IntMod2 = IntMod2(0)
}
implicit val intMod2Eq: Eq[IntMod2] = (a1: IntMod2, a2: IntMod2) => a1.unwrap == a2.unwrap
}
// Morphism in category Set between the set Char and the set String is a total function Char => String
val i: Char => String = (c: Char) => c.toString
// Morphism in category Set between the set Char and the set IntMod2 is a total function Char => IntMod2
val f: Char => IntMod2 = (c: Char) => IntMod2(1)
// Morphism in category Mon between Monoid[String] and Monoid[IntMod2] is a total function String => IntMod2
// but also a homomorphism between Monoid[String] and Monoid[IntMod2] (to be checked after this).
// Note that the following hand-crafted definition of g is absolutely unique given i and f if we want the UMP for Monoid[String] to hold (see propUMP below).
val g: String => IntMod2 = (s: String) => IntMod2(s.length)
import IntMod2._
// Check that g is a Monoid homomorphism
val propMonoidHom = forAll { (a: String, b: String) =>
Monoid[IntMod2].combine(g(a), g(b)) == g(Monoid[String].combine(a, b))
}
propMonoidHom.check()
// Universal Mapping Property (Monoid[String] is a free monoid).
// We cannot prove that g is unique but check how our hand-crafted implementation will fare.
// For any x (element of (the set of) Char), we check that Monoid[String] is free in the sense that
// for any f, there exists (we can design) a unique g that 'expands' i to f.
val propUMP = forAll { x: Char =>
// Note that g originally operates in category Mon but after applying a forgetful functor U to it, it operates in category Set
g(i(x)) == f(x)
}
propUMP.check()
// Now we can use foldMap to interpret a Foldable List into the 'target' monoid Monoid[IntMod2]
val res: IntMod2 = List("ab", "bc", "cde") foldMap g // extra argument (Monoid[IntMod2]) is inferred
println(s"res=$res")
assert(res == IntMod2(1))
val propFoldMap = forAll { ls: List[String] =>
(ls foldMap g) == IntMod2(ls map(_.length) foldMap identity)
}
propFoldMap.check()
// Morphism in category Set between the set Boolean and the set of all strings like ["0","1"]* is a total function Boolean => ["0","1"]*
val i2: Boolean => String = (b: Boolean) => if (b) "1" else "0"
// Morphism in category Set between the set Boolean and the set IntMod2 is a total function Boolean => IntMod2
val f2: Boolean => IntMod2 = (b: Boolean) => IntMod2(if (b) 1 else 0)
// Morphism in category Mon between Monoid[["0","1"]*] and Monoid[IntMod2] is a total function ["0","1"]* => IntMod2
// but also a homomorphism between Monoid[["0","1"]*] and Monoid[IntMod2] (to be checked after this).
// Note that the following hand-crafted definition of g2 is absolutely unique given i2 and f2 if we want the UMP for Monoid[["0","1"]*] to hold (see propUMP2 below).
val g2: String => IntMod2 = (s: String) => IntMod2(s.count(_ == '1'))
// Check that g2 is a Monoid homomorphism (TODO needs to enforce a and b to be like ["0","1"]* but works for String as well)
val propMonoidHom2 = forAll { (a: String, b: String) =>
Monoid[IntMod2].combine(g2(a), g2(b)) == g2(Monoid[String].combine(a, b))
}
propMonoidHom2.check()
// Universal Mapping Property (Monoid[["0","1"]*] is a free monoid).
// We cannot prove that g2 is unique but check how our hand-crafted implementation will fare.
// For any x (element of (the set of) Boolean), we check that Monoid[["0","1"]*] is free in the sense that
// for any f2, there exists (we can design) a unique g2 that 'expands' i2 to f2.
val propUMP2 = forAll { (x: Boolean) =>
// Note that g2 originally operates in category Mon but after applying a forgetful functor U to it, it operates in category Set
g2(i2(x)) == f2(x)
}
propUMP2.check()
// Now we can use foldMap to interpret a Foldable List into the 'target' monoid Monoid[IntMod2]
// Even number of 1's in all strings combined
val res21: IntMod2 = List("01", "01", "101") foldMap g2 // extra argument (Monoid[IntMod2]) is inferred
println(s"res21=$res21")
assert(res21 == IntMod2(0))
// Odd number of 1's in all strings combined
val res22: IntMod2 = List("01", "011", "101") foldMap g2 // extra argument (Monoid[IntMod2]) is inferred
println(s"res22=$res22")
assert(res22 == IntMod2(1))
val propFoldMap2 = forAll { ls: List[String] =>
(ls foldMap g2) == IntMod2(ls map(_.count(_ == '1')) foldMap identity)
}
propFoldMap2.check()
// Morphism in category Set between the set Char and the set String is a total function Char => String
val i_hc: Char => String = (c: Char) => c.toString
// Morphism in category Set between the set Char and the set Long is a total function Boolean => Long
val f_hc: Char => Long = (c: Char) => c.toLong
// Morphism in category Mon between Monoid[String] and Monoid[Long] is a total function String => Long
// but also a homomorphism between Monoid[String] and Monoid[Long] (to be checked after this).
// Note that the following hand-crafted definition of g_hc is absolutely unique given i_hc and f_hc if we want the UMP for Monoid[String] to hold (see propUMP_hc below).
val g_hc: String => Long = (s: String) => s.map((x: Char) => x.toLong).sum
// Check that g_hc is a Monoid homomorphism
val propMonoidHom_hc = forAll { (a: String, b: String) =>
Monoid[Long].combine(g_hc(a), g_hc(b)) == g_hc(Monoid[String].combine(a, b))
}
propMonoidHom_hc.check()
// Universal Mapping Property (Monoid[String] is a free monoid).
// We cannot prove that g_hc is unique but check how our hand-crafted implementation will fare.
// For any x (element of (the set of) Char), we check that Monoid[String] is free in the sense that
// for any f_hc, there exists (we can design) a unique g_hc that 'expands' i_hc to f_hc.
val propUMP_hc = forAll { x: Char =>
// Note that g_hc originally operates in category Mon but after applying a forgetful functor U to it, it operates in category Set
g_hc(i_hc(x)) == f_hc(x)
}
propUMP_hc.check()
// Now we can use foldMap to interpret a Foldable List into the 'target' monoid Monoid[Long]
val res_hc: Long = List("ab", "bc", "cde") foldMap g_hc // extra argument (Monoid[Long]) is inferred
println(s"res_hc=$res_hc")
assert(res_hc == 692)
val propFoldMap_hc = forAll { ls: List[String] =>
(ls foldMap g_hc) == (ls.map(_.map((x: Char) => x.toLong).sum)).sum
}
propFoldMap_hc.check()
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment