Combinatory Recursion

[TomasMikula]

Currently, a recursive function is represented as (A -⚬ B) => (A -⚬ B). More precisely:

case class RecF[A, B](f: (A -⚬ B) => (A -⚬ B)) extends (A -⚬ B) { self =>
  val recursed: A -⚬ B = f(self)
}

That is, there is a Scala function (=>) involved, which defeats the benefits of "programs as values" (e.g., it cannot be serialized).

There are several alternatives to address that.

Of course, there is a point-full way: label the recursive function and then invoke it by label:

case class RecF[A, B](label: Label[A, B], f: A -⚬ B) extends (A -⚬ B) // where f can contain RecCall(label)
case class RecCall[A, B](label: Label[A, B]) extends (A -⚬ B)

However, that is a misfit with an otherwise point-free representation. It would mean that one has to be careful about capture avoidance during serialization (e.g. by ensuring unique label names or by alpha renaming).

Here are two (dual) combinators to implement recursive functions:

def repeatUntilRight[A, B](f: A -⚬ (A |+| B)): A -⚬ B

def repeatUntilChooseLeft[A, B](f: (A |&| B) -⚬ B): A -⚬ B

These should definitely be exposed to the user.

If the above two combinators are not versatile enough, we could provide something like

def rec[A, B](f: (RecCall[A, B] |*| A) -⚬ B): A -⚬ B // RecCall here has nothing to do with RecCall above

// invoke recursive call
def recCall[A, B]: (RecCall[A, B] |*| A) -⚬ B

// comonoid operations on RecCall, to allow any number of recursive calls
def noRecCall[A, B]: RecCall[A, B] -⚬ One
def dupRecCall[A, B]: RecCall[A, B] -⚬ (RecCall[A, B] |*| RecCall[A, B])

For closed DSLs, RecCall[A, B] can be just Unlimited[A =⚬ B].