2014-05-17 13 views
6

Così comonad.com ha un'interessante serie di articoli su come lavorare con gli applicativi e ho cercato di portare quello che posso a scala (per divertimento e per imparare). Così, Haskell definisce FixF -Definizione di Haskell FixF in scala

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

è scritto," FixF è di tipo ((* -> *) -> * -> *) -> * -> *) Prende il punto fisso di una. "Secondo ordine Functor"(un funtore che invia una Functor ad un altro Functor, vale a dire un endofunctor sulla categoria funck dell'hash), per recuperare un "primo ordine Functor" standard. "

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

Ora ho visto questo

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

e questo

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

Quindi non è il primo Fix (tipo sbagliato) E 'il secondo? Io non la penso che i generi sono proprio

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

è vero -

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

è?

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

se così mi piacerebbe vedere la definizione corretta e funtore

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

} 

ora domanda bonus, qualcuno può definire l'applicativo?

+0

Questo dovrebbe essere taggato [python]? Non vedo perché? –

+0

@jb, non c'è alcuna ragione per taggare questa domanda python. in quanto ovviamente non ha nulla da pitone. – DEAD

risposta

8

Questa è una domanda interessante - avrei letto anche quei post, e mi ero chiesto come sarebbe stata terrificante l'implementazione di Scala, ma non l'ho mai provata. Quindi risponderò in dettaglio, ma tieni presente che quanto segue è estremamente pratico (è sabato mattina, dopotutto) e non rappresenta necessariamente il modo più pulito per farlo in Scala.

E 'probabilmente meglio iniziare definendo alcuni dei tipi dalla 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[_], 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] 

E un paio di più dal 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]) 

Se avete lavorato con quanto sopra, dovresti avere un'idea di cosa dovrebbe essere FixF:

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

Si scopre che questo è un po 'troppo severo, però, così useremo la seguente invece:

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)" 
} 

Ora supponiamo che vogliamo implementare liste come "secondo ordine punto fisso di funtori polinomiali", come nel post del blog. Possiamo cominciare definendo alcuni alias utili:

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] 

E ora possiamo definire la versione Scala degli esempi da posta:

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

Questo appare come quello che ci si aspetterebbe data la realizzazione Haskell :

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

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

Ora abbiamo bisogno delle nostre istanze di classe tipo. La maggior parte di questi sono abbastanza semplice:

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

Compreso l'istanza applicativa per FixF sé:

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

Faremo anche definire la trasformazione del terminale:

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

Ma ora siamo nei guai. Abbiamo davvero bisogno di un po 'di pigrizia in più qui, quindi dovremo imbrogliare un po':

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

Forse c'è un modo per arrivare a questo lavoro con la codifica di applicativi Scalaz 7 di senza il trucco, ma se c'è io don' Voglio passare il sabato pomeriggio a capirlo.

Quindi che fa schifo, ma almeno adesso possiamo controllare il nostro lavoro:

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

che è esattamente quello che volevamo.

+1

Fantastico. molto apprezzato. – DEAD

0

Solo guardando il tipo di dati Haskell, mi piacerebbe provare la seguente classe:

import scala.language.higherKinds 

class FixF[F[_,_],A](val ffix: F[FixF[F,_],A]) extends AnyVal; 

Cercherò di ampliare la risposta più tardi, quando ho imparato di più su FixF.