2

我想为一个函数定义一个类型，该函数执行某些操作，然后返回另一个相同类型的函数[可以是它自己]。显而易见的想法不起作用（“非法循环类型引用”错误）：

type Behavior[S] = S => Behavior[S]

我在这里有什么明显的遗漏吗？我也不明白如何表达“函数返回自身”的想法。

4

1 回答 1

8

简短的回答

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

长答案（短版）

Terminal F-Coalgebras非常酷。

长答案

警告：很多铁丝网和香蕉，或其他东西......

好的，所以，假设你有一个仿函数的概念，F它捕捉到你的行为“做某事”的含义。在大多数库中是这样的：

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

-coalgebraF本质A上只是一个从A到的函数F[A]：

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

现在，一个终端 F-coalgebraT是一个F-coalgebra 它还具有一个属性，即从所有其他F-coalgebraA那里有一个中介态射A => T（这样一切都可以交换，等等）：

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

为了举一个具体的例子，让我们看看这个装置对最简单的可想象函子做了什么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代数Option是所谓的余数。这些基本上是自然数，加上可数无穷大。这些东西非常适合表示可能无限“点击”过程的长度。

让我们尝试一个有限的行为：

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)

现在，上述机器自动为我们提供了一种通用方法，可以将这些计数词转换为自然数。让我们添加一个辅助方法来描述自然数（大约）：

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(()))}")
于 2021-11-23T20:28:25.287 回答