在scala中定义Haskell FixF

Question

所以comonad.com有一系列有趣的关于使用应用程序的文章,我一直在努力把我能用到scala(为了好玩和学习).所以,haskell定义了FixF -

newtype FixF f a = FixF (f (FixF f) a)

它是写的," FixF是善良的((* -> *) -> * -> *) -> * -> *).它需要一个"二阶Functor"(一个Functor将Functor发送给另一个Functor,即hask的functor类别的endofunctor)的修复点,以恢复标准的"第一顺序" Functor"退出."

kinds classify types
*                   type  A
* -> *              type F[_]
* -> * -> *         type F[_,_]
((* -> *) -> *)     type F[F'[_]]
((* -> *) ->* -> *) type F[F'[_], A] 

现在我已经看到了这一点

case class Fix[F[_]](out: F[Fix[F]])
// ((* -> *) -> * )

还有这个

case class BFixF[F[_,_], A](out: F[A, BFixF[F,A]])

所以它不是第一个Fix(错误种类)它是第二个吗？我不认为种类是对的

BFixF :: ((* -> * -> * ) -> * -> *) ?

是吗 -

    // edit as of this morning it is really not this
    class FixF[F[_[_], _], A] :: ((* -> *) -> * -> *) -> *)

是吗 ？

    case class FixF'[F[_], A](run: F[Fix[F, A]]) 

如果是这样,我很乐意看到正确的定义和函子

 case class FixF[F[_], A] (out: F[Fix[F, A]])

 trait FixFFunctor[F[_]: Functor] extends Functor[({type l[x] = FixF[F, x]})#l] {

   def map[A, B](f: A => B): FixF[F, A] => FixF[F, B] = ???

 }

现在红利问题,有人能定义应用吗？

Answer 1

这是一个非常酷的问题 - 我也会阅读这些帖子,并且想知道Scala实现看起来有多可怕,但我从未尝试过.所以我会稍微回复一下,但请注意以下内容非常不合适(毕竟是星期六早上),并不一定代表Scala最干净的方式.

最好从系列的第一篇文章中定义一些类型开始:

import scala.language.higherKinds
import scalaz._, Scalaz._

case class Const[M, A](mo: M)

sealed trait Sum[F[_], G[_], A]

object Sum {
  def inL[F[_], G[_], A](l: F[A]): Sum[F, G, A] = InL(l)
  def inR[F[_], G[_], A](r: G[A]): Sum[F, G, A] = InR(r)
}

case class InL[F[_], G[_], A](l: F[A]) extends Sum[F, G, A]
case class InR[F[_], G[_], A](r: G[A]) extends Sum[F, G, A]

还有一些来自博客文章的帖子:

case class Embed[F[_], A](out: A)

case class ProductF[F[_[_], _], G[_[_], _], B[_], A](f: F[B, A], g: G[B, A])

如果您已完成上述工作,您应该对FixF应该是什么样子有所了解:

case class FixF[F[f[_], _], A](out: F[({ type L[x] = FixF[F, x] })#L, A])

事实证明,这有点过于严格,所以我们将使用以下内容:

class FixF[F[f[_], _], A](v: => F[({ type L[x] = FixF[F, x] })#L, A]) {
  lazy val out = v
  override def toString = s"FixF($out)"
}

现在假设我们想要将列表实现为"多项式函子的二阶修正点",如博客文章中所述.我们可以从定义一些有用的别名开始:

type UnitConst[x] = Const[Unit, x]
type UnitConstOr[F[_], x] = Sum[UnitConst, F, x]
type EmbedXUnitConstOr[F[_], x] = ProductF[Embed, UnitConstOr, F, x]

type MyList[x] = FixF[EmbedXUnitConstOr, x]

现在我们可以从帖子中定义示例的Scala版本:

val foo: MyList[String] = new FixF[EmbedXUnitConstOr, String](
  ProductF[Embed, UnitConstOr, MyList, String](
    Embed("foo"),
    Sum.inL[UnitConst, MyList, String](Const())
  )
)

val baz: MyList[String] = new FixF[EmbedXUnitConstOr, String](
  ProductF[Embed, UnitConstOr, MyList, String](
    Embed("baz"),
    Sum.inL[UnitConst, MyList, String](Const())
  )
)

val bar: MyList[String] = new FixF[EmbedXUnitConstOr, String](
  ProductF[Embed, UnitConstOr, MyList, String](
    Embed("bar"),
    Sum.inR[UnitConst, MyList, String](baz)
  )
)

这看起来像我们在Haskell实现时所期望的:

scala> println(foo)
FixF(ProductF(Embed(foo),InL(Const(()))))

scala> println(bar)
FixF(ProductF(Embed(bar),InR(FixF(ProductF(Embed(baz),InL(Const(())))))))

现在我们需要我们的类型类实例.其中大部分非常简单:

implicit def applicativeConst[M: Monoid]: Applicative[
  ({ type L[x] = Const[M, x] })#L
] = new Applicative[({ type L[x] = Const[M, x] })#L] {
  def point[A](a: => A): Const[M, A] = Const(mzero[M])
  def ap[A, B](fa: => Const[M, A])(f: => Const[M, A => B]): Const[M, B] =
    Const(f.mo |+| fa.mo) 
}

implicit def applicativeEmbed[F[_]]: Applicative[
  ({ type L[x] = Embed[F, x] })#L
] = new Applicative[({ type L[x] = Embed[F, x] })#L] {
  def point[A](a: => A): Embed[F, A] = Embed(a)
  def ap[A, B](fa: => Embed[F, A])(f: => Embed[F, A => B]): Embed[F, B] =
    Embed(f.out(fa.out))
}

implicit def applicativeProductF[F[_[_], _], G[_[_], _], B[_]](implicit
  fba: Applicative[({ type L[x] = F[B, x] })#L],
  gba: Applicative[({ type L[x] = G[B, x] })#L]
): Applicative[({ type L[x] = ProductF[F, G, B, x] })#L] =
  new Applicative[({ type L[x] = ProductF[F, G, B, x] })#L] {
    def point[A](a: => A): ProductF[F, G, B, A] =
      ProductF(fba.point(a), gba.point(a))
    def ap[A, C](fa: => ProductF[F, G, B, A])(
      f: => ProductF[F, G, B, A => C]
    ): ProductF[F, G, B, C] = ProductF(fba.ap(fa.f)(f.f), gba.ap(fa.g)(f.g))
  }

包括FixF自己的应用实例:

implicit def applicativeFixF[F[_[_], _]](implicit
  ffa: Applicative[({ type L[x] = F[({ type M[y] = FixF[F, y] })#M, x] })#L]
): Applicative[({ type L[x] = FixF[F, x] })#L] =
  new Applicative[({ type L[x] = FixF[F, x] })#L] {
    def point[A](a: => A): FixF[F, A] = new FixF(ffa.pure(a))
    def ap[A, B](fa: => FixF[F, A])(f: => FixF[F, A => B]): FixF[F, B] =
      new FixF(ffa.ap(fa.out)(f.out))
  }

我们还将定义终端转换:

implicit def terminal[F[_], M: Monoid]: F ~> ({ type L[x] = Const[M, x] })#L =
  new (F ~> ({ type L[x] = Const[M, x] })#L) {
    def apply[A](fa: F[A]): Const[M, A] = Const(mzero[M])
  }

但现在我们遇到了麻烦.我们真的需要一些额外的懒惰,所以我们会作弊:

def applicativeSum[F[_], G[_]](
  fa: Applicative[F],
  ga: => Applicative[G],
  nt: G ~> F
): Applicative[({ type L[x] = Sum[F, G, x] })#L] =
  new Applicative[({ type L[x] = Sum[F, G, x] })#L] {
    def point[A](a: => A): Sum[F, G, A] = InR(ga.point(a))
    def ap[A, B](x: => Sum[F, G, A])(f: => Sum[F, G, A => B]): Sum[F, G, B] =
      (x, f) match {
        case (InL(v), InL(f)) => InL(fa.ap(v)(f))
        case (InR(v), InR(f)) => InR(ga.ap(v)(f))
        case (InR(v), InL(f)) => InL(fa.ap(nt(v))(f))
        case (InL(v), InR(f)) => InL(fa.ap(v)(nt(f)))
      }
  }

implicit def myListApplicative: Applicative[MyList] =
  applicativeFixF[EmbedXUnitConstOr](
    applicativeProductF[Embed, UnitConstOr, MyList](
      applicativeEmbed[MyList],
      applicativeSum[UnitConst, MyList](
        applicativeConst[Unit],
        myListApplicative,
        terminal[MyList, Unit]
      )
    )
  )

也许有一种方法可以让Scalaz 7的应用程序编码在没有黑客的情况下使用,但是如果有的话我不想花费我的星期六下午搞清楚.

这很糟糕,但至少现在我们可以检查我们的工作:

scala> println((foo |@| bar)(_ ++ _))
FixF(ProductF(Embed(foobar),InL(Const(()))))

这正是我们想要的.