Je veux définir un type pour une fonction qui fait quelque chose, puis renvoie une autre fonction du même type [peut être lui-même]. L'idée évidente n'ai pas de travail ("Illégale cyclique référence de type" d'erreur):
type Behavior[S] = S => Behavior[S]
Il est évident que je suis en manque ici? Aussi je ne comprends pas comment exprimer une idée de "fonction renvoyant lui-même".
case class Behavior[S](step: S => Behavior[S])
Le Terminal F-Coalgebras sont assez cool.
Avertissement: beaucoup de fils de fer barbelés & co-bananes, ou quelque chose...
Ok, donc, supposons que vous ayez la notion de foncteur F qui capture ce que cela signifie que votre comportement "fait quelque chose". Dans la plupart des bibliothèques est quelque chose comme ceci:
trait Functor[F[_]]:
def map[A, B](fa: F[A])(f: A => B): F[B]
Un F-coalgebra A est essentiellement une fonction de A pour F[A]:
trait FCoalg[F[_]: Functor, A]:
def apply(a: A): F[A]
Maintenant, un terminal F-coalgebra T est un F-coalgebra qui, de plus, possède une propriété que de tous les autres F-coalgebra A il y a une médiation morphism A => T (tel que tout les déplacements, bla bla):
trait TerminalFCoalg[F[_]: Functor, T] extends FCoalg[F, T]:
def mediate[A](coalg: FCoalg[F, A]): A => T
Peut-on mettre en œuvre pour arbitraire F? Il s'avère que nous pouvons:
case class TerminalFCoalgCarrier[F[_]: Functor](
step: () => F[TerminalFCoalgCarrier[F]]
)
given tfcImpl[F[_]: Functor]: TerminalFCoalg[F, TerminalFCoalgCarrier[F]] with
def apply(a: TerminalFCoalgCarrier[F]): F[TerminalFCoalgCarrier[F]] = a.step()
def mediate[A](coalg: FCoalg[F, A]): A => TerminalFCoalgCarrier[F] = a =>
TerminalFCoalgCarrier(() => summon[Functor[F]].map(coalg(a))(mediate(coalg)))
Pour le bien d'un exemple concret, nous allons voir ce que l'engin n'est pour le plus simple imaginable foncteur Option:
given Functor[Option] with
def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
type ConaturalNumber = TerminalFCoalgCarrier[Option]
Il s'avère que le terminal F-coalgebra pour Option les soi-disant conatural numéros. Ce sont essentiellement les nombres naturels, plus dénombrable à l'infini. Ces choses sont bien adaptés pour représenter les longueurs de potentiellement infinie "cliquant" sur les processus.
Faites un essai sur une durée de comportement:
enum WelshCounting:
case Eeny
case Meeny
case Miny
case Moe
object WelshCountingOptionCoalg extends FCoalg[Option, WelshCounting]:
def apply(w: WelshCounting): Option[WelshCounting] =
import WelshCounting._
w match
case Eeny => None
case Meeny => Some(Eeny)
case Miny => Some(Meeny)
case Moe => Some(Miny)
val welshMediatingMorphism =
summon[TerminalFCoalg[Option, TerminalFCoalgCarrier[Option]]]
.mediate(WelshCountingOptionCoalg)
Maintenant, les machines ci-dessus automatiquement nous donne un moyen universel de traduire ces mots de comptage en conatural numéros. Nous allons ajouter une méthode d'assistance pour décrire conatural numéros (environ):
def describe(c: ConaturalNumber): String =
var counter = 0
var curr = c
while true do
curr.step() match
case None => return s"${counter}"
case Some(next) =>
if counter > 42 then
return "probably infinite"
else {
counter += 1
curr = next
}
throw new Error("We have counted to infinity, yay! :D")
Ce qu'il ne montre pour les Gallois, les mots de comptage?
@main def demo(): Unit =
for w <- WelshCounting.values do
val conat = welshMediatingMorphism(w)
println(s"${w} -> ${describe(conat)}")
// Eeny -> 0
// Meeny -> 1
// Miny -> 2
// Moe -> 3
Ok, c'est bien. Essayons une infiniment cliquant processus avec un seul état est le successeur de lui-même:
object LoopForever extends FCoalg[Option, Unit]:
def apply(u: Unit) = Some(())
val loopForeverMediatingMorphism =
summon[TerminalFCoalg[Option, TerminalFCoalgCarrier[Option]]]
.mediate(LoopForever)
Comment serait-il maintenant de décrire l'état célibataire ()?
println(s"${()} -> ${describe(loopForeverMediatingMorphism(()))}")
// () -> probably infinite
Semble fonctionner.
Code complet:
trait Functor[F[_]]:
def map[A, B](fa: F[A])(f: A => B): F[B]
trait FCoalg[F[_]: Functor, A]:
def apply(a: A): F[A]
trait TerminalFCoalg[F[_]: Functor, T] extends FCoalg[F, T]:
def mediate[A](coalg: FCoalg[F, A]): A => T
case class TerminalFCoalgCarrier[F[_]: Functor](
step: () => F[TerminalFCoalgCarrier[F]]
)
given tfcImpl[F[_]: Functor]: TerminalFCoalg[F, TerminalFCoalgCarrier[F]] with
def apply(a: TerminalFCoalgCarrier[F]): F[TerminalFCoalgCarrier[F]] = a.step()
def mediate[A](coalg: FCoalg[F, A]): A => TerminalFCoalgCarrier[F] = a =>
TerminalFCoalgCarrier(() => summon[Functor[F]].map(coalg(a))(mediate(coalg)))
given Functor[Option] with
def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
type ConaturalNumber = TerminalFCoalgCarrier[Option]
def describe(c: ConaturalNumber): String =
var counter = 0
var curr = c
while true do
curr.step() match
case None => return s"${counter}"
case Some(next) =>
if counter > 42 then
return "probably infinite"
else {
counter += 1
curr = next
}
throw new Error("We cannot count to infinity :(")
enum WelshCounting:
case Eeny
case Meeny
case Miny
case Moe
object WelshCountingOptionCoalg extends FCoalg[Option, WelshCounting]:
def apply(w: WelshCounting): Option[WelshCounting] =
import WelshCounting._
w match
case Eeny => None
case Meeny => Some(Eeny)
case Miny => Some(Meeny)
case Moe => Some(Miny)
val welshMediatingMorphism =
summon[TerminalFCoalg[Option, TerminalFCoalgCarrier[Option]]]
.mediate(WelshCountingOptionCoalg)
object LoopForever extends FCoalg[Option, Unit]:
def apply(u: Unit) = Some(())
val loopForeverMediatingMorphism =
summon[TerminalFCoalg[Option, TerminalFCoalgCarrier[Option]]]
.mediate(LoopForever)
@main def demo(): Unit =
for w <- WelshCounting.values do
val conat = welshMediatingMorphism(w)
println(s"${w} -> ${describe(conat)}")
println(s"${()} -> ${describe(loopForeverMediatingMorphism(()))}")