Applicative.scala

applicative.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[_], F[_]] {
  def traverse[A, B](f: A => F[B], a: T[A]): 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[F[_]](implicit f: Applicative[F]) = new Traversable[List, F] {
    def cons[A]: A => List[A] => List[A] = h => t => h :: t
    def traverse[A, B](g: A => F[B], a: List[A]): F[List[B]] = a match {
      case Nil     => f.pure(Nil)
      case x :: xs => f.apply(f.apply(f.pure(cons[B]), g(x)), traverse(g, xs))
    }
  }

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

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

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

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