McBride and Paterson's applicatives, in Scala

[juan_gandhi]

trait Applicative[T[_]] extends Functor[T] {
  def pure[A](a:A):T[A]
  def ap[A,B](tf:T[A=>B]): T[A] => T[B]
  def map[A,B](f:A=>B) = ap(pure(f))
}

abstract class Applicable[A, B, T[_]](fs: T[A=>B]) {
  def <*>(at: T[A]):T[B]
}
abstract class Lifted[A, B, T[_]](f: A=>B) {
  def <@>(ta:T[A]): T[B] // in Haskell it is <$>; can't use $ in Scala, and can't have lt;&s> either.
}

trait RichApplicative[T[_]] extends Applicative[T] {
  implicit def applicable[A,B](tf:T[A=>B]): Applicable[A, B, T]
  implicit def lift[A,B](f: A=>B) = new Lifted[A, B, T](f) { def <@>(at: T[A]) = ap(pure(f))(at)}
}

trait Traversable[T[_]] extends RichApplicative[T] {
  def traverse[A, B](f: A => T[B])(as: List[A]): T[List[B]] = as match {
    case Nil => pure(Nil)
    case head::tail => lift(cons[B] _) <@> f(head) <*> traverse(f)(tail)
  }

  def dist[A] = traverse(identity[T[A]] _) _
}

Work in progress. I'm on page 5. (dumb, eh)

Comments? Ideas?

Comments

[ivan-gandhi.livejournal.com]

Да это трейты. Вот и разделил.

[sassa-nf.livejournal.com]

так а в чём трейтовость? Вроде * от $ отличаются только первым аргументом, а в скальной реализации - только способом конструировать Applicable / Lifted. После конструирования разница есть? Вроде нет.

[ivan-gandhi.livejournal.com]

Да я не вижу пока особого смысла в наличии <$>; посмотрю ещё.

[sassa-nf.livejournal.com]

типа def lift(f) = applicative(pure f), а потому applicative(f)=new Applicative(f){ def <*>(at)=ap(f)(at) }

[ivan-gandhi.livejournal.com]

Да, действительно; попробую. Я думал этот <@> будет где-то систематически нужен...