Applicative2

applicative2.scala

trait Applicative[F[_]] {
  def pure[A](a: A): F[A]
  def apply[A, B](f: F[A => B], a: F[A]): F[B]
}

trait Traversable[T[_]] {
  def traverse[A, B, F[_] ](a: T[A])(g: A => F[B])(implicit f: Applicative[F]): F[T[B]]
}

trait Monoid[A] {
  def unit: A
  def plus(a: A, b: A): A
}

case class Acc[O, A](acc: O)

object Main {
  implicit def ListMonoid[A] = new Monoid[List[A]] {
    def unit = Nil
    def plus(a: List[A], b: List[A]) = a ++ b
  }

  implicit def ApplicativeList = new Applicative[List] {
    def pure[A](a: A): List[A] = List(a)
    def apply[A, B](f: List[A => B], a: List[A]): List[B] = for (g <- f; i <- a) yield g(i)
  }

  implicit def PhantomApplicative[O](implicit m: Monoid[O]) = new Applicative[({type F[A] = Acc[O, A]})#F] {
    def pure[A](a: A)  = Acc(m.unit)
    def apply[A, B](o1: Acc[O, A => B], o2: Acc[O, A]): Acc[O, B] = Acc(m.plus(o1.acc, o2.acc))
  }

  implicit def TraversableList = new Traversable[List] {
    def cons[A]: A => List[A] => List[A] = h => t => h :: t
    def traverse[A, B, F[_]](a: List[A])(g: A => F[B])(implicit f: Applicative[F]): F[List[B]] = a match {
      case Nil     => f.pure(Nil)
      case x :: xs => f.apply(f.apply(f.pure(cons[B]), g(x)), traverse(xs)(g))
    }
  }

  def traverse[A, B, T[_], F[_]](a: T[A])(g: A => F[B])(implicit f: Applicative[F], t: Traversable[T]): F[T[B]] =
    t.traverse(a)(g)

  def compose[A, B, C](g: B => C, f: A => B): A => C = x => g(f(x))

  def accumulate[T[_], A, O](x: T[A])(f: A => O)(implicit t: Traversable[T], o: Monoid[O]): O = {
    def acc: O => Acc[O, O]= x => Acc(x)
    t.traverse[A, O, ({type F[B] = Acc[O, B]})#F](x)(compose(acc, f)).acc
  }

  def main(args: Array[String]): Unit = {
    println(accumulate(List(List(1), List(2), List(3)))(x => x))
  }
}