Eu quero definir um tipo para uma função que faz alguma coisa e, em seguida, retorna outra função do mesmo tipo [pode ser em si]. O óbvio, a ideia não funcionou ("Ilegal cíclica tipo de erro" referência):
type Behavior[S] = S => Behavior[S]
Há algo de óbvio que eu estou faltando aqui? Também não compreendo como a de expressar uma idéia de "função retornar em si".
case class Behavior[S](step: S => Behavior[S])
Terminal F-Coalgebras são muito legais.
Aviso: os lotes de arame farpado e co-bananas, ou algo assim...
Ok, então, suponha que você tenha o conceito de um functor F que capta o que significa que o seu comportamento "faz algo". Na maioria das bibliotecas é algo como isto:
trait Functor[F[_]]:
def map[A, B](fa: F[A])(f: A => B): F[B]
Um F-coalgebra A é essencialmente uma função da A para F[A]:
trait FCoalg[F[_]: Functor, A]:
def apply(a: A): F[A]
Agora, um terminal F-coalgebra T é um F-coalgebra que além disso tem uma propriedade que de todos os outros F-coalgebra A há uma mediação morphism A => T (de tal forma que tudo o que comutam, blá, blá):
trait TerminalFCoalg[F[_]: Functor, T] extends FCoalg[F, T]:
def mediate[A](coalg: FCoalg[F, A]): A => T
Podemos implementá-lo para arbitrário F? Acontece que, nós 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 causa de um exemplo concreto, vamos ver o que essa geringonça faz para o mais simples que se possa imaginar 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]
Acontece que o terminal F-coalgebra para Option são os chamados conatural números. Estes são basicamente os números naturais, além de infinito contável. Essas coisas são bem adequados para representar comprimentos de potencialmente infinita "clicando em" processos.
Vamos tentar em um finito comportamento:
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)
Agora, acima de máquinas automaticamente nos dá uma forma universal para traduzir essas contagem de palavras em conatural números. Vamos adicionar um método auxiliar para descrever 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")
O que faz é mostrar para o país de gales contagem de palavras?
@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, que bom. Vamos tentar infinitamente clicando o processo com apenas um estado que é o sucessor de si mesmo:
object LoopForever extends FCoalg[Option, Unit]:
def apply(u: Unit) = Some(())
val loopForeverMediatingMorphism =
summon[TerminalFCoalg[Option, TerminalFCoalgCarrier[Option]]]
.mediate(LoopForever)
Como poderia descrever agora o único estado ()?
println(s"${()} -> ${describe(loopForeverMediatingMorphism(()))}")
// () -> probably infinite
Parece funcionar.
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(()))}")