Summation of higher kinded types.

GenericVersion.scala

abstract class Tree[+A]
case class Node[A](l: Tree[A], e: A, r: Tree[A]) extends Tree[A]
case object Tip extends Tree[Nothing]

abstract class MONOID[T] {
  val append: T => T => T
  val identity: T
}

object IntMonoid extends MONOID[Int] {
  val append = (a: Int) => (b: Int) => a + b
  val identity = 0
}

object StringMonoid extends MONOID[String] {
  val append = (a: String) => (b: String) => a + b
  val identity = ""
}

abstract class FOLDABLE[hk[_]] {
  def foldm[el](i: el)(f: el => el => el)(x: hk[el]): el
}

object FoldableList extends FOLDABLE[List] {
  def foldm[el](i: el)(f: el => el => el)(x: List[el]): el = x match {
    case Nil => i
    case h::t => foldm(f(i)(h))(f)(t)
  }
}

object Summation {
  def apply[M[_], A](F: FOLDABLE[M])(M: MONOID[A])(xs: M[A]): A = F.foldm(M.identity)(M.append)(xs)
}

object ModuleFun extends App {
  val SumLInt = Summation(FoldableList)(IntMonoid) _
  val SumLString = Summation(FoldableList)(StringMonoid) _
  
  println(SumLInt(List(1,2,3,4)))
  println(SumLString(List("a", "b", "c", "d")))
  //println(SumTInt.sum(Node(Node(Tip, 3, Tip), 4, Node(Tip, 5, Tip))))  
}

ModuleFun.scala

abstract class Tree[+A]
case class Node[A](l: Tree[A], e: A, r: Tree[A]) extends Tree[A]
case object Tip extends Tree[Nothing]

abstract class MONOID {
  type t
  val append: t => t => t
  val identity: t
}
  
object IntMonoid extends MONOID {
  type t = Int
  val append: Int => Int => Int = a => b => a + b
  val identity = 0
}

object StringMonoid extends MONOID {
  type t = String
  val append: String => String => String = a => b => a + b
  val identity = ""
}

abstract class FOLDABLE {
  type el
  type hk
  val foldm: el => (el => el => el) => hk => el
}
  
abstract class FoldableList extends FOLDABLE {
  type hk = List[el]
  override val foldm: el => (el => el => el) => hk => el = (i: el) => (f: el => el => el) => (x: hk) => x match {
    case Nil => i
    case h::t => foldm(f(i)(h))(f)(t)
  }
}

abstract class FoldableTree extends FOLDABLE {
  type hk = Tree[el]
  override val foldm: el => (el => el => el) => hk => el = (i: el) => (f: el => el => el) => (x: hk) => x match {
    case Tip => i
    case Node(l, e, r) => foldm(foldm(f(i)(e))(f)(l))(f)(r)
  }
}

abstract class Summation {
  val M: MONOID
  val FM: FOLDABLE{ type el = M.t}
  def sum(x: FM.hk): M.t = FM.foldm(M.identity)(M.append)(x)
}

object SumLInt extends Summation {
  val M = IntMonoid
  val FM = new FoldableList {
    type el = M.t
  }
}

object SumLString extends Summation {
  val M = StringMonoid
  val FM = new FoldableList {
    type el = M.t
  }
}

object SumTInt extends Summation {
  val M = IntMonoid
  val FM = new FoldableTree {
    type el = M.t
  }
}

object ModuleFun extends App {
  println(SumLInt.sum(List(1,2,3,4)))
  println(SumLString.sum(List("a", "b", "c", "d")))
  println(SumTInt.sum(Node(Node(Tip, 3, Tip), 4, Node(Tip, 5, Tip))))  
}

MonoidTest.scala

trait Monoid[T] {
  def append(a: T, b: T): T
  def zero: T
}

object Monoid {
  implicit object IntMonoid extends Monoid[Int] {
    override def append(a: Int, b: Int): Int = a + b
    override def zero = 0
  }
  
  implicit object StringMonoid extends Monoid[String] {
    override def append(a: String, b: String): String = a + b
    override def zero = ""
  }
}

trait FoldLeft[F[_]] {
  def foldLeft[A, B](xs: F[A], b: B, f: (B, A) => B): B
}

object FoldLeft {
  implicit object FoldLeftList extends FoldLeft[List] {
    override def foldLeft[A, B](xs: List[A], b: B, f: (B, A) => B): B = xs.foldLeft(b)(f)
  }
}

object MonoidTest extends App {
  def sum[M[_], A](xs: M[A])(implicit m: Monoid[A], f: FoldLeft[M]) = f.foldLeft(xs, m.zero, m.append)
  
  val a = List(1,2,3)
  val b = List("a","b","c")
  
  println(sum(a))
  println(sum(b))
}

NotCompile.scala

abstract class Tree[+A]
case class Node[A](l: Tree[A], e: A, r: Tree[A]) extends Tree[A]
case object Tip extends Tree[Nothing]

abstract class MONOID {
  type t
  val append: t => t => t
  val identity: t
}
  
object IntMonoid extends MONOID {
  type t = Int
  val append: Int => Int => Int = a => b => a + b
  val identity = 0
}

object StringMonoid extends MONOID {
  type t = String
  val append: String => String => String = a => b => a + b
  val identity = ""
}

abstract class FOLDABLE {
  type hk[_]
  def foldm[el, hk[el]](i: el)(f: el => el => el)(x: hk[el]): el
}
  
object FoldableList extends FOLDABLE {
  type hk[_] = List[_]
  override def foldm[el, hk[el]](i: el)(f: el => el => el)(x: List[el]): el = x match {
    case Nil => i
    case h::t => foldm(f(i)(h))(f)(t)
  }
}

object FoldableTree extends FOLDABLE {
  type hk = Tree[_]
  override def foldm[el, hk[el]](i: el)(f: el => el => el)(x: Tree[el]): el = x match {
    case Tip => i
    case Node(l, e, r) => foldm(foldm(f(i)(e))(f)(l))(f)(r)
  }
}

class Summation(val M: MONOID, FM: FOLDABLE) {
  def sum(x: FM.hk[M.t]): M.t = FM.foldm(M.identity)(M.append)(x)
}

object SumLInt extends Summation(IntMonoid, FoldableList)

object SumLString extends Summation(StringMonoid, FoldableList)

object SumTInt extends Summation(IntMonoid, FoldableTree)

object ModuleFun extends App {
  println(SumLInt.sum(List(1,2,3,4)))
  println(SumLString.sum(List("a", "b", "c", "d")))
  println(SumTInt.sum(Node(Node(Tip, 3, Tip), 4, Node(Tip, 5, Tip))))  
}