scalahigher-order-functionsscala-3higher-order-types

Recursive higher order function type in Scala 3


I want to define a type for a function that does something and then returns another function of the same type [can be itself]. The obvious idea didn't work ("Illegal cyclic type reference" error):

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

Is there something obvious that I am missing here? Also I do not understand how to express an idea of "function returning itself".


Solution

  • Short answer

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

    Long answer (short version)

    Terminal F-Coalgebras are pretty cool.

    Long answer

    Warning: lots of barbed wire & co-bananas, or something...

    Ok, so, suppose that you have the concept of a functor F that captures what it means that your behavior "does something". In most libraries it's something like this:

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

    An F-coalgebra A is essentially just a function from A to F[A]:

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

    Now, a terminal F-coalgebra T is an F-coalgebra which additionally has a property that from every other F-coalgebra A there is a mediating morphism A => T (such that everything commutes, blah blah):

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

    Can we implement it for arbitrary F? It turns out we can:

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

    For the sake of a concrete example, let's see what that contraption does for the simplest imaginable 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]
    

    It turns out that the terminal F-coalgebra for Option are the so-called conatural numbers. These are basically the natural numbers, plus countable infinity. These things are nicely suitable for representing lengths of potentially infinite "clicking" processes.

    Let's try it on a finite behavior:

    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)
    

    Now, the above machinery automatically gives us a universal way to translate those counting words into conatural numbers. Let's add a helper method for describing conatural numbers (approximately):

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

    What does it show for the Welsh counting words?

    
    @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
    
    

    Ok, that's neat. Let's try an infinitely clicking process with just one state that is successor of itself:

    object LoopForever extends FCoalg[Option, Unit]:
      def apply(u: Unit) = Some(())
    
    val loopForeverMediatingMorphism =
      summon[TerminalFCoalg[Option, TerminalFCoalgCarrier[Option]]]
        .mediate(LoopForever)
    
    

    How would it now describe the single state ()?

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

    Seems to work.


    Full code:

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