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

Question

我想为一个做某事的函数定义一个类型，然后 returns 另一个相同类型的函数[可以是它本身]。明显的想法行不通（“非法循环类型引用”错误）：

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]

现在，终端 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-余代数就是所谓的同自然数。这些基本上是自然数，加上可数无穷大。这些东西非常适合表示潜在无限“点击”过程的长度。

让我们在有限行为上试试：

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

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

Recursive higher order function type in Scala 3

scala

higher-order-functions

higher-order-types

scala-3

简答

长答案（简短版）

长答案