Quiero definir un tipo para una función que hace algo y, a continuación, devuelve otra función del mismo tipo [puede ser]. La idea obvia de no funcionar ("Ilegal cíclica tipo de error" referencia):
type Behavior[S] = S => Behavior[S]
Hay algo que es obvio que me estoy perdiendo aquí? También no entiendo cómo expresar una idea de la función "volver en sí".
case class Behavior[S](step: S => Behavior[S])
Terminal F-Coalgebras son bastante buenos.
Advertencia: muchos de alambre de púas & co-plátanos, o algo...
Aceptar, por lo tanto, supongamos que usted tiene el concepto de un functor F que capta lo que significa que su comportamiento "hace algo". En la mayoría de las bibliotecas es algo como esto:
trait Functor[F[_]]:
def map[A, B](fa: F[A])(f: A => B): F[B]
Un F-coalgebra A es, básicamente, una función de A a F[A]:
trait FCoalg[F[_]: Functor, A]:
def apply(a: A): F[A]
Ahora, un terminal F-coalgebra T es un F-coalgebra que, además, tiene una propiedad que de todos los demás F-coalgebra A hay una mediación de morfismos A => T (que todo desplazamientos, bla, bla):
trait TerminalFCoalg[F[_]: Functor, T] extends FCoalg[F, T]:
def mediate[A](coalg: FCoalg[F, A]): A => T
Podemos implementar para arbitrario F? Resulta que podemos:
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)))
Por el bien de un ejemplo concreto, vamos a ver lo que artilugio hace de la manera más simple imaginable functor Option:
given Functor[Option] with
def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
type ConaturalNumber = TerminalFCoalgCarrier[Option]
Resulta que el terminal F-coalgebra para Option son los llamados conatural números. Estos son, básicamente, los números naturales, además de infinito contable. Estas cosas son muy adecuados para representar las longitudes de potencialmente infinito "clic" de los procesos.
Vamos a intentarlo en un número finito de comportamiento:
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)
Ahora, por encima de la maquinaria automáticamente nos da una forma universal para traducir esos conteo de palabras en conatural números. Vamos a añadir un método auxiliar para describir conatural números (aproximadamente):
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")
¿Qué muestra para el Galés conteo de palabras?
@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, eso está claro. Vamos a intentar una infinitamente hacer clic en proceso con un solo estado que es el sucesor de la misma:
object LoopForever extends FCoalg[Option, Unit]:
def apply(u: Unit) = Some(())
val loopForeverMediatingMorphism =
summon[TerminalFCoalg[Option, TerminalFCoalgCarrier[Option]]]
.mediate(LoopForever)
¿Cómo podría ahora describir el único estado ()?
println(s"${()} -> ${describe(loopForeverMediatingMorphism(()))}")
// () -> probably infinite
Parece que funciona.
Código completo:
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(()))}")