scala - Scala 3 中的递归高阶函数类型

Question

我想为一个函数定义一个类型，它做某事然后返回另一个相同类型的函数[可以是它本身]。显而易见的想法行不通(“非法循环类型引用”错误):

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

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

Answer 1

简答

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]

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

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

现在，一个 terminal F-coalgebra T 是一个 F-coalgebra，它还有一个属性从所有其他 F-coalgebra A 有一个中介态射 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]

事实证明，Option 的终结符 F-coalgebra 是所谓的自然数。这些基本上是自然数，加上可数无穷大。这些东西非常适合表示潜在无限“点击”过程的长度。

让我们在有限行为上尝试一下:

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