Home > database >  Recursive higher order function type in Scala 3
Recursive higher order function type in Scala 3

Time:11-24

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

CodePudding user response:

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

CodePudding user response:

Expanding that alias will lead to a function of undefined order i.e. S => S => S => ....

A high order function will return another function. The type of a function needs to be well defined hence you need to know the precise order of the returned function.

If you plan to make a function that returns another high order function (possibly itself) you could use currying:

def makeFOrder1(arg: Int): Int => Int =
  arg2 => arg2   arg

def makeFOrder2(arg: Int): Int => Int => Int =
  arg2 => arg3 => arg   arg2   arg3

def makeFOrder3(arg: Int): Int => Int => Int => Int =
  arg2 => arg3 => arg4 => arg   arg2   arg3   arg4


//They behave like curried functions
makeFOrder1(1)(2)
makeFOrder2(1)(2)(3)
makeFOrder3(1)(2)(3)(4)

//Use currying directly
def makeF(arg: Int)(arg2: Int)(arg3: Int)(arg4: Int): Int =
  arg   arg2   arg3   arg4

makeF(1)(2)(3)(4)

val partiallyApplied1 = makeF(1)
val partiallyApplied2 = partiallyApplied1(2)(3)
val partiallyApplied3 = partiallyApplied1(4)
  • Related