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]

А почему два разных класса Applicable и Lifted? (У МакБрайда понятно почему отдельно * и $)

[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]

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

[sassa-nf.livejournal.com]

и второе: что-то с ленивостью не понятно как быть. Например, traverse бесконечный Stream.

[ivan-gandhi.livejournal.com]

Хороший вопрос, посмотрю.

[sassa-nf.livejournal.com]

а ещё

  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)
  }

кажется, означает рекурсию глубины as.size.

а давайте сделаем вот так:

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

а из-за ленивости Stream, видимо, нужно переписать <*> и т.п. с ленивым аргументом def <*>(at: =>T[A]):T[B]

  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) )

[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]

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