Magma.scala

trait Magma[A] {
  def append(x: A, y: A): A
}

object Magma {
  implicit def Monoid[A](implicit m: Monoid[A]) = new Magma[A] {
    def append(x: A, y: A) = m.append(x, y)
  }
}

sealed trait Tree[A] {
  def foldMap[B: Magma](f: A => B): B
}
case class Leaf[A](value: A) extends Tree[A] {
  def foldMap[B: Magma](f: A => B) = f(value)
}
case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A] {
  def foldMap[B](f: A => B)(implicit m: Magma[B]) =
    m.append(left.foldMap(f), right.foldMap(f))
}

trait Monoid[A] {
  def zero: A
  def append(x: A, y: A): A
}

case class Sum[N](value: N)

object Sum {
  implicit def Monoid[N](implicit n: Numeric[N]) = new Monoid[Sum[N]] {
    def zero = Sum(n.zero)
    def append(x: Sum[N], y: Sum[N]) = Sum(n.plus(x.value, y.value))
  }
}

object MagmaTest extends App {
  assert(Node(Leaf(0), Node(Leaf(1), Leaf(2))).foldMap(Sum[Int]) == Sum(3))
}

解説とか

Magmaは二項演算を持つ。

MonoidはMagmaに結合律と単位元を加えたもの。

MonoidがMagmaを継承していないのは、Haskellに合わせる為です。

MonoidはMagmaですので、implicit conversionが定義されます。

Magmaのコンパニオンオブジェクトに定義することで、implicit parameterの探索範囲に加えられます。

Sumは数値をWrapすることで、Monoidとして扱うことが可能です。

SumもMagmaと同様に、コンパニオンオブジェクトにインスタンスを定義します。

Tree(BinaryTree)は自由マグマとして、foldMap(マグマ準同型)を持ちます。

この例だと構造を保っていることがわかりにくいですが、勉強会で例にあったKakkoなどを定義してみるとわかりやすいと思います。