monoid

scalaz-monoid.scala

//
// Semigroup with a associative binary method `append`, subject
// to semigroup laws
//
// A Semigroup in type F must satisfy two laws:
// - closure: ∀ a, b in F, append(a, b) is also in F. This is
//   enforced by the type system
// - associativity: ∀ a, b, c in F, the following equation holds
//   => append(append(a, b), c) = append(a, append(b , c))
//
// Unlike a Monoid, Semigroup doesn't necessarily have a zero
// element
//
trait Semigroup[F] {
  // The associative binary method to combine `f1` and `f2`
  def append(f1: F, f2: => F): F

  trait SemigroupApply extends Apply[({type λ[α]=F})#λ] {
    def map[A, B](fa: F)(f: A => B) = fa
    def ap[A, B](fa: => F)(f: => F) = append(f, fa)
  }
}

//
// Monoid is a Semigroup with an identity element `zero` and 
// associative binary method `append` and that is subject to
// monoid laws
//
// Monoid instances must satisfy Semigroup laows and 2
// additional laws:
// - left identity:  ∀ a, append(zero, a) == a
// - right identity: ∀ a, append(a, zero) == a
//
// Monoid[Int]: `zero` and `append` are `0` and `+` respectively
// Monoid[List[A]]: `zero` and `append` are `Nil` and `++` respectively
//
//
trait Monoid[F] extends Semigroup[f] {
  // The identity element for `append`
  def zero: F

  ...
}

//
// Duality: Dual of any monoid by flipping the append
// operation
//
def dual[F](m: Monoid[F]): Monoid[F] = new Monoid[F] {
  val zero = m.zero
  def append(f1: F, f2: => F): A = m.append(f2, f1)
}

implicit def endoMonoid[F] = new Monoid[F => F] {
  def zero: F => F = identity
  def append(f1: F => F, f2: => F => F) = f1 andThen f2
}

// Generic sum for List[A], given Monoid[A]
def sum[A](xs: List[A])(implicit M: Monoid[A]): A = {
  xs.foldLeft(M.zero)(M.op)
}

// Generic sum for F[A], given Foldable[F] and Monoid[A]
def sum[F[_], A](fa: F[A])(implicit F: Foldable[F], M: Monoid[A]): A = {
  F.foldMap(fa)(identity)(M)
}