在scala中定义Haskell FixF

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

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

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] = ???

 }

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

最好从定义first post in the series中的一些类型开始：

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[_],A](l: F[A]): Sum[F,G,A] = InL(l)
  def inR[F[_],A](r: G[A]): Sum[F,A] = InR(r)
}

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

还有一些来自blog post itself：

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,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,x]

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

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

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

val baz: MyList[String] = new FixF[EmbedXUnitConstOr,String](
    Embed("baz"),String](Const())
  )
)

val bar: MyList[String] = new FixF[EmbedXUnitConstOr,String](
    Embed("bar"),Sum.inR[UnitConst,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[_[_],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,B,x] })#L] =
  new Applicative[({ type L[x] = ProductF[F,x] })#L] {
    def point[A](a: => A): ProductF[F,A] =
      ProductF(fba.point(a),gba.point(a))
    def ap[A,C](fa: => ProductF[F,A])(
      f: => ProductF[F,A => C]
    ): ProductF[F,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,x] })#L] =
  new Applicative[({ type L[x] = Sum[F,x] })#L] {
    def point[A](a: => A): Sum[F,A] = InR(ga.point(a))
    def ap[A,B](x: => Sum[F,A])(f: => Sum[F,A => B]): Sum[F,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,MyList](
      applicativeEmbed[MyList],applicativeSum[UnitConst,MyList](
        applicativeConst[Unit],myListApplicative,terminal[MyList,Unit]
      )
    )
  )

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

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

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

这正是我们想要的.