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

问题描述 投票:0回答:1

我想为一个函数定义一个类型,该函数执行某些操作,然后返回另一个相同类型的函数[可以是它本身]。明显的想法不起作用(“非法循环类型引用”错误):

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

我在这里遗漏了一些明显的东西吗?我也不明白如何表达“函数返回自身”的想法。

scala higher-order-functions scala-3 higher-order-types
1个回答
9
投票

简短回答

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

长答案(简短版)

终端 F-余代数 非常酷。

长答案

警告:大量铁丝网和香蕉,或者其他东西......

好吧,假设您有函子

F
的概念,它捕获了您的行为“做某事”的含义。大多数图书馆都是这样的:

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

F
-代数
A
本质上只是从
A
F[A]
的函数:

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

现在,一个 terminal

F
-余代数
T
是一个
F
-余代数,它另外还有一个属性,即与所有其他
F
-余代数
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]

事实证明,

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

© www.soinside.com 2019 - 2024. All rights reserved.