免费适用于Scala

Question

通过haskell免费软件包(http://hackage.haskell.org/package/free-3.4.2),有一些类似于简单和有用的类型,我几乎看不到有关haskell外部的文献,类型I'我现在感兴趣的是Free Applicative.现在我认为免费的应用程序将功能应用程序链构建为数据并映射它们(不在/外)G,(我认为......)

我在哪里......

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]

我要求的是:runAp在haskell看起来如此简单,但我在翻译时遇到了一些麻烦...我需要向正确的方向推进

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

理想情况下,我想轻松地通过免费的应用程序和至少runAp实现的一些帮助(但真的进入它并且没有任何细节)

更新:所以我自己一直在使用这个并且我尝试实现map并且我得到了一个方差错误,第二个case表达式给出了一个错误,除非FreeAp在A中是逆变的,但是第一个case表达式给出了一个错误,除非FreeAp不是A中的逆变...任何想法？

更新:我添加了来自@ Cirdec的答案的方差注释,它并没有突然发挥作用,但我玩了一下并在地图中的Ap构造中添加了注释[Any,B],现在定义类型检查.到目前为止虽然runAp没有运气...

更新:这是我在runAp模式匹配的Ap分支上得到的类型错误...

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

更新阅读:http: //ro-che.info/articles/2013-03-31-flavours-of-free-applicative-functors.html,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

性状

首先,你需要得到什么Applicative和Functor正确的.让我们开始吧Functor.我将使用Haskell名称和参数命令,我可以:

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

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

现在Applicative.你Applicative错过了Applicative第一个必须是a Functor,并且Applicative有一种方法可以从一个值中创建一个.类型apF也似乎不正确; 它应该允许你将一个卡在仿函数中的函数应用到一个也卡在仿函数中的值.

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

我建议你在跳到免费应用程序之前做一些其他适用的东西,也许是Identity仿函数及其应用实例.希望这可以帮助您了解您需要为免费应用实例制作什么.

数据类型和方差

现在我们需要数据类型.

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

在Scala中,这些由case类表示:

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]

为了使Scala的变体类型起作用,我们使用方差对它们进行注释,并在我们的特征上正确标记方差.这在具有变体类型系统的语言中是正常的,c#中的类似接口将需要in和out注释通常是有用的并且与使用库的程序员的期望相匹配.如果你真的讨厌方差,你可以从我的答案中删除所有方差注释,它仍然可以工作 - 你只是没有变量接口.

实例

我们可以开始移植实例Functor和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和Applicative Instances

Scala中的仿函数实例难以编写,因为实际上没有普遍量化的类型.使用通用量化类型,flip并且compose可以在没有显式类型的情况下使用.我们可以通过a在模式匹配中绑定类型变量来解决这个问题,这是由模式完成的ap: Ap[F,a,_].type变量用于提供显式类型.compose(_ : a => A)和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,这是必要的Applicative,只是翻转两个参数的顺序:

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

runAp

最后,我们可以移植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

这需要通用量化forall x. f x -> g x.我们可以通过泛型语言的常用技巧来满足这一点 - 为某些东西添加通用成员; 然后,成员可以为所有类型提供一些东西,但我们需要能够明确地提供类型.您已经清楚地找到了自然变换的Scala类型:

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

同样,我们将从模式绑定一个类型变量a,ap: Ap[F, a _]以获得Scala无法推断的类型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 只是身份功能:

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