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

[sassa-nf.livejournal.com]

duh!..

def traverse[A, B](f: A => T[B])(as: List[A]): T[List[B]] = foldR(pure Nil)( (p,n) => lift(cons[B] _) <@> f(p) <*> n )

аналогично

def traverse[A, B](f: A => T[B])(as: Stream[A]): T[Stream[B]] = if as.isEmpty pure(Stream.empty) else lift(Stream.cons[B] _) <@> f(as.head) <*> traverse(f)(as.tail)

[ivan-gandhi.livejournal.com]

о, конечно. спасибо!!!