Reworked and explanded UMP presentation and Scala Cats examples of free monoids

FoldMapUMP.scala

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()

}