Free Applicative in Scala

Question

Looking through the haskell free package (http://hackage.haskell.org/package/free-3.4.2) there's a few types that seem simple and useful, that I see almost no literature on outside of haskell, the type I'm interested in now is the Free Applicative. Now I think that the free applicative builds up chains of function applications as data and maps them (out-of / over) G, (I think...)

where I'm at ...

trait Functor[F[_]]  { 
  def map[A, B](f: A => B): F[A] => F[B]
}

trait Applicative[F[_]] extends Functor[F] {
  def ap[A, B](f: F[A => B]): F[A] => F[B]
  def apF[A, B](f: F[A])(x: F[A => B]): F[B]
}

trait FreeAp[F[_], A] {
  def map[B](f: A => B): FreeAp[F, B] = {
   this match {
    case Pure(x) => Pure(f(x))
    case Ap(x, y) => Ap(x, { y.map(f.compose _) })
  }
}
  def runAp[G[_]](phi: F ~> G, fa: FreeAp[F, A])(implicit G: Applicative[G]): G[A] = {
    fa match {
      case Pure(x) => G.pure(x)
      case Ap(f, x) => G.apF(phi(f)) { G.map(id[A])(runAp(phi, x)) } 
    }
  }

   def runApM[B, M](phi: F ~> ({ type l[x] = M })#l, x: FreeAp[F, B])(implicit M: Monoid[M]): M = {
      ???
    }
  }

case class Pure[F[_], A](x: A) extends FreeAp[F, A]
case class Ap[F[_], A, B](x: F[A], y: FreeAp[F, A => B]) extends FreeAp[F, B]

what I'm asking for: the runAp looks so simple in haskell but I've been having some trouble translating... I need a shove in the right direction

runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a
runAp _ (Pure x) = pure x
runAp u (Ap f x) = flip id <$> u f <*> runAp u x

Ideally I'd like a gentle walk through the free applicative and some help with at least the runAp implementation (but really get into it and spare no detail)

update: so I've been working with this myself and I tried implementing map and I get a variance error, the second case expression gives an error unless FreeAp is contravariant in A, but the first case expression gives an error unless FreeAp isn't contravariant in A... Any Ideas ?

update: I added the variance annotations from @Cirdec's answer and it didn't suddenly work but I played around and added a annotation [Any, B] to the Ap construction in map and now that definition type checks. so far though no luck with runAp...

update: this is the type error I'm getting on the Ap branch of the runAp pattern match ...

type mismatch; found : core01.FreeAp[F,Any => A] required: core01.FreeAp[F,A]

////

trait Forall[P[_]] {
  def apply[A]: P[A]
}

trait ~>[F[_], G[_]] { 
  def apply[A](x: F[A]): G[A] 
}

UPDATE reading: http://ro-che.info/articles/2013-03-31-flavours-of-free-applicative-functors.html, Free Applicative Functors by Paolo Capriotti

//// including the Functor & Applicative definitions above
trait FreeAp[F[_], A] { self =>
  def map[B](f: A => B): FreeAp[F, B] = {
    this match {
      case Pure(x) => Pure(f(x))
      case ap: Ap[F, α, _] => Ap(ap.x.map(f.compose(_: α => A)), ap.y)
    }
  }
}


case class Pure[F[_], A](x: A) extends FreeAp[F, A]
case class Ap[F[_], A, B](x: FreeAp[F, A => B], y: F[A]) extends FreeAp[F, B]

def liftAp[F[_], A](x: F[A]): FreeAp[F, A] = Ap[F, A, A](Pure(id), x)

def runAp[F[_], G[_], A](implicit G: Applicative[G]): (F ~> G) => FreeAp[F, A] => G[A] = {
  (u: F ~> G) =>
    (fa: FreeAp[F, A]) => fa match {
      case Pure(x) => G.pure(x)
      case ap: Ap[F, α, _] => {
      val gf: G[(α => A) => A] = G.map(curry(flip(id[α => A])))(u(ap.y))
      val gx: G[α => A] = runAp(G)(u)(ap.x)
      G.ap(gf)(gx)
    }
  }
}

trait FreeApFunctor[F[_]] extends Functor[({ type l[x] = FreeAp[F, x] })#l] {
  final override def map[A, B](f: A => B): FreeAp[F, A] => FreeAp[F, B] = _ map f
}

  trait FreeApSemiapplicative[F[_]] extends Apply[({ type l[x] = FreeAp[F, x] })#l] with FreeApFunctor[F] {
final def ap[A, B](f: => FreeAp[F, A => B]): FreeAp[F, A] => FreeAp[F, B] = {
  (fa: FreeAp[F, A]) => f match {
    case Pure(x) => map(x)(fa)
    case a: Ap[F, α, _] => Ap(ap{ map(flip[α, A, B])(a.x) }(fa), a.y)
    }//                                              ^^^
     // type mismatch; found : core01.FreeAp[F,α => _] required: core01.FreeAp[F,(α, A) => B]
  }
}

Answer 1

Traits

First, you'll need to get what Applicative and Functor are correct. Let's start with Functor. I'm going to use the Haskell names and argument orders for everything, where I can:

class Functor f where
        fmap    :: (a -> b) -> f a  -> f b

trait Functor[F[+_]] {
    def fmap[A,B]: (A => B) => F[A] => F[B]
}

Now Applicative. Your Applicative is missing that an Applicative first must be a Functor and that an Applicative has a way to make one from a value. The type for apF also seems to be incorrect; it should allow you to apply a function that is stuck inside the functor to a value that is also stuck inside the functor.

class Functor f => Applicative f where
        pure  :: a-> f a
        (<*>)  :: f (a -> b)-> f a  -> f b

trait Applicative[F[+_]] extends Functor[F] {
    def pure[A]: A => F[A]
    def apF[A,B]: F[A => B] => F[A] => F[B]
}

I'd suggest you make something else that's applicative before jumping all the way to free applicative, perhaps the Identity functor and its applicative instance. Hopefully this will help you understand what you need to be making for the free applicative instance.

Data Types and Variance

Now we need the data types.

data Ap f a where
  Pure :: a -> Ap f a
  Ap   :: f a -> Ap f (a -> b) -> Ap f b

In Scala, these are represented by case classes:

sealed abstract class FreeAp[F[+_],+A]
case class Pure[F[+_], +A](a: A) extends FreeAp[F, A]
case class Ap[F[+_], A, +B](x: F[A], fg: FreeAp[F,A=>B]) extends FreeAp[F, B]

In order for Scala's variant types to work, we annotated these with variance, and marked the variance correctly on our traits as well. This is normal in languages with variant type systems, a similar interface in c# would require in and out annotation to be generally useful and match the expectations of programmers using libraries. If you really hate variance, you can remove all the variance annotations from my answer, and it still works - you just won't have variant interfaces.

Instances

We can start porting the instances for Functor and Applicative:

instance Functor (Ap f) where
  fmap f (Pure a)   = Pure (f a)
  fmap f (Ap x y)   = Ap x ((f .) <$> y)

instance Applicative (Ap f) where
  pure = Pure
  Pure f <*> y = fmap f y
  Ap x y <*> z = Ap x (flip <$> y <*> z)

Functor and Applicative Instances

A functor instance in Scala is difficult to write, due to the fact that there aren't really universally quantified types. With universally quantified types, flip and compose could both be used below without explicit types. We can get around this by binding a type variable, a, in pattern matching, which is done by the pattern ap: Ap[F,a,_]. The type variable is used to provide the explicit types .compose(_ : a => A) and flip[a,A,B].

class FreeApInstances[F[+_]] {
    implicit object FreeApApplicativeInstance extends Applicative[({type f[+x] = FreeAp[F, x]})#f] {
        // Functor
        final def fmap[A,B]:   (A=>B) =>      FreeAp[F,A]  => FreeAp[F,B] =
                            (f: A=>B) => (fa: FreeAp[F,A]) => fa match {
            case Pure(a)         => Pure(f(a))
            case ap: Ap[F, a, _] => Ap(ap.x, fmap(f.compose(_ : a => A))(ap.fg))
        }
        // Applicative
        final def pure[A]:    A  => FreeAp[F,A] =
                          (a: A) => Pure(a)
        final def apF[A, B]:     FreeAp[F,A=>B]  =>      FreeAp[F,A]  => FreeAp[F,B] =
                            (ff: FreeAp[F,A=>B]) => (fa: FreeAp[F,A]) => ff match {
            case Pure(f)         => fmap(f)(fa)
            case ap: Ap[F, a, _] => Ap(ap.x, apF(fmap(flip[a,A,B])(ap.fg))(fa))
        }
    }
}

flip, which is needed for Applicative, just flips the order of two arguments:

def flip[A,B,C]:    (A => B => C)  =>     B  =>     A  => C =
                (f: (A => B => C)) => (b: B) => (a: A) => f(a)(b)

runAp

Finally, we can port runAp:

-- | Given a natural transformation from @f@ to @g@, this gives a canonical monoidal natural transformation from @'Ap' f@ to @g@.
runAp :: Applicative g => (forall x. f x -> g x) -> Ap f a -> g a
runAp _ (Pure x) = pure x
runAp u (Ap f x) = flip id <$> u f <*> runAp u x

This requires a universal quantification for forall x. f x -> g x. We can satisfy this one with the usual trick for languages with generics - add a generic member to something; the member can then provide something for all types, though we will need to be able to explicitly provide the type. You have clearly already found a Scala type for natural transformations:

trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] }

Again, we'll bind a type variable a from the pattern ap: Ap[F, a _] to get the type that Scala can't infer, id: (a=>A) => a => A.

def runAp[F[_],G[_],A](implicit g: Applicative[G]):
       (F ~> G) =>      FreeAp[F,A]  => G[A] =
    (u: F ~> G) => (fa: FreeAp[F,A]) => fa match {
        case Pure(x)         => g.pure(x)
        case ap: Ap[F, a, _] => {
            val gf: G[(a=>A)=>A] = g.fmap(flip(id[a=>A]))(u.apply(ap.x))
            val gx: G[a=>A]      = runAp(g)(u)(ap.fg)
            g.apF(gf)(gx)
        } 
    }

id is just the identity function:

def id[A]:   A  => A =
          (x:A) => x