संक्षिप्त जवाब

case class Behavior[S](step: S => Behavior[S])

लंबे जवाब (लघु संस्करण)

टर्मिनल एफ-Coalgebras बहुत अच्छा कर रहे हैं.

लंबे जवाब

चेतावनी: के बहुत सारे कंटीले तार और सह-केले, या कुछ और...

ठीक है, तो मान लीजिए कि आप की अवधारणा को एक functor F को दर्शाता है कि क्या इसका मतलब है कि अपने व्यवहार करता है "कुछ". ज्यादातर पुस्तकालयों कुछ इस तरह है:

trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]

एक F-coalgebra A अनिवार्य रूप से सिर्फ एक समारोह से A करने के लिए F[A]:

trait FCoalg[F[_]: Functor, A]:
  def apply(a: A): F[A]

अब, एक टर्मिनल F-coalgebra T एक F-coalgebra जो इसके अलावा, एक संपत्ति है कि से हर दूसरे F-coalgebra A वहाँ है एक मध्यस्थता आकारिता A => T (इस तरह है कि सब कुछ commutes, ब्ला ब्ला):

trait TerminalFCoalg[F[_]: Functor, T] extends FCoalg[F, T]:
  def mediate[A](coalg: FCoalg[F, A]): A => T

हम कर सकते हैं इसे लागू करने के लिए मनमाने ढंग से F? यह पता चला है हम कर सकते हैं:

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

की खातिर के लिए एक ठोस उदाहरण के लिए, चलो देखते हैं क्या है कि कोंटरापशन करता है के लिए सबसे सरल कल्पना 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]

यह पता चला है कि टर्मिनल F-coalgebra के लिए Option तथाकथित conatural संख्या. ये मूल रूप से कर रहे हैं प्राकृतिक संख्या, प्लस गणनीय अनंत । ये बातें कर रहे हैं अच्छी तरह से उपयुक्त का प्रतिनिधित्व करने के लिए लंबाई के संभावित अनंत "क्लिक" प्रक्रियाओं.

चलो यह कोशिश करते हैं पर एक परिमित व्यवहार:

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)

अब, उपरोक्त मशीनरी स्वचालित रूप से हमें देता है एक सार्वभौमिक तरह से अनुवाद करने के लिए उन लोगों की गिनती शब्दों में conatural संख्या है. चलो एक सहायक विधि का वर्णन करने के लिए conatural संख्या (लगभग):

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

क्या करता है यह दिखाने के लिए वेल्श गिनती के शब्द?

@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

ठीक है, यह साफ है । चलो कोशिश एक असीम क्लिक के साथ प्रक्रिया सिर्फ एक है कि राज्य के उत्तराधिकारी ही है:

object LoopForever extends FCoalg[Option, Unit]:
  def apply(u: Unit) = Some(())

val loopForeverMediatingMorphism =
  summon[TerminalFCoalg[Option, TerminalFCoalgCarrier[Option]]]
    .mediate(LoopForever)

कैसे होगा यह अब का वर्णन भी राज्य ()?

println(s"${()} -> ${describe(loopForeverMediatingMorphism(()))}")
// () -> probably infinite

काम करने लगता है.

पूरा कोड:

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