Character traits
First, you need to get the correct Applicative and Functor values. Let's start with Functor . I am going to use Haskell names and arguments for everything where I can:
class Functor f where fmap :: (a -> b) -> fa -> fb trait Functor[F[+_]] { def fmap[A,B]: (A => B) => F[A] => F[B] }
Now Applicative . Your Applicative absent, and Applicative must be a Functor and that Applicative has a way to make it one of the values. The type for apF also seems wrong; it should allow you to apply a function stuck inside a functor to a value that is also stuck inside a functor.
class Functor f => Applicative f where pure :: a-> fa (<*>) :: f (a -> b)-> fa -> fb trait Applicative[F[+_]] extends Functor[F] { def pure[A]: A => F[A] def apF[A,B]: F[A => B] => F[A] => F[B] }
I would advise you to do something else that is applicative before jumping to a full application, perhaps the Identity functor and its applicative instance. Hope this helps you understand what you need to do for the free applicative instance.
Data Types and Deviations
Now we need data types.
data Ap fa where Pure :: a -> Ap fa Ap :: fa -> Ap f (a -> b) -> Ap fb
In Scala, they 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 the working Scala types to work, we annotated them with dispersion and correctly estimated the variance on our traits. This is normal in languages with type variants; a similar interface in C # requires that the in and out annotations are generally useful and meet the expectations of programmers using libraries. If you really hate rejection, you can remove all change annotations from my answer, and it still works - you just won't have any interface options.
Instances
We can start porting instances for Functor and Applicative :
instance Functor (Ap f) where fmap f (Pure a) = Pure (fa) fmap f (Ap xy) = Ap x ((f .) <$> y) instance Applicative (Ap f) where pure = Pure Pure f <*> y = fmap fy Ap xy <*> z = Ap x (flip <$> y <*> z)
Functor and applicative instances
A functor instance in Scala is difficult to write because there are actually no universally quantified types. When using universally quantified flip and compose types, both can be used below without explicit types. We can get around this by binding a variable of type a , according to the pattern that is executed by the pattern ap: Ap[F,a,_] . A typical variable is used to provide explicit types .compose(_ : a => A) and flip[a,A,B] .
class FreeApInstances[F[+_]] { implicit object FreeApApplicativeInstance extends Applicative[({type f[+x] = FreeAp[F, x]})
flip , which is required for Applicative , simply reverses 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 runAp port:
-- | 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. fx -> gx) -> Ap fa -> ga runAp _ (Pure x) = pure x runAp u (Ap fx) = flip id <$> uf <*> runAp ux
This requires universal quantification for forall x. fx -> gx forall x. fx -> gx . We can satisfy this with the usual trick for languages with generics - add a common element to something; the member can then provide something for all types, although we will need to explicitly specify the type. You have already explicitly found a Scala for natural transformations :
trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] }
Again, we bind a variable of type a from the ap: Ap[F, a _] template to get a type that Scala cannot 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 only an identical function:
def id[A]: A => A = (x:A) => x