Foldable

trait Foldable[F[_]] {

  def foldr[A, B](f: (A, B) => B)(z: B)(fa: F[A]): B

  def foldMap[A, M: Monoid](f: A => M)(fa: F[A]): M = {
    val m: Monoid[M] = implicitly[Monoid[M]]
    foldr[A, M]((a, b) => m.mappend(f(a), b))(m.mempty)(fa)
  }
}

object Foldable {

  def foldr[A, B, F[_]: Foldable](f: (A, B) => B)(z: B)(fa: F[A]): B =
    implicitly[Foldable[F]].foldr(f)(z)(fa)

  def foldMap[A, F[_]: Foldable, M: Monoid](f: A => M)(fa: F[A]): M =
    implicitly[Foldable[F]].foldMap(f)(fa)
}