4.13. Recursion

4.13.1. Recursive functions

A function may refer to itself, and the compiler generates the corresponding recursion in the target language. Factorial, with guards:

fact :: Int -> Int
fact n
  ? n == 0 = 1
  : n * fact (n - 1)
$ ./recur fact 10
3628800

Functions may also be mutually recursive. This pair decides, inefficiently, whether a number is even:

isEven :: Int -> Bool
isEven n
  ? n == 0 = True
  : isOdd (n - 1)

isOdd :: Int -> Bool
isOdd n
  ? n == 0 = False
  : isEven (n - 1)
$ ./recur isEven 10
true
Caution

Recursion is not equally well supported across target languages. Some impose a recursion depth limit or lack tail-call optimization, so deep recursion can overflow the stack or crash the pool.

4.13.2. Recursive types

A type is recursive when its definition refers to itself. To terminate, that recursion has to be guarded: every cycle through the definition must pass under an ?T (optional, with Null as the base case) or a [T] (list, with [] as the base case).

A bare self-reference is rejected at compile time:

recx.loc:5:1: Type alias 'X' has a vacuous body: it reduces to a self-reference with no payload
    |
  5 | type X = X
    | ^

The examples below need one stdlib import for working with optional values:

import maybe-py (require, isNull)

isNull tests whether an optional is absent; require asserts it is present and strips the ?.

Linked lists

The canonical case: a payload paired with an optional tail of the same type. When the tail slot reaches Null, the chain ends.

type LL a = (a, ?(LL a))

llExample :: LL Int
llExample = (42, (7, (99, Null)))
$ ./recur llExample
[42,[7,[99,null]]]

A builder producing a descending range:

llRange :: Int -> LL Int
llRange n ? n > 0 = (n, llRange (n - 1))
          : (0, Null)
$ ./recur llRange 3
[3,[2,[1,[0,null]]]]

The recursive call returns LL Int, but the second slot wants ?(LL Int). The typechecker’s element-wise coercion from a to ?a bridges that with no annotation. The base case writes Null straight into the optional slot.

Consumers use the tuple selectors .0 and .1:

llLen :: LL Int -> Int
llLen x ? isNull (.1 x) = 1
        : 1 + llLen (require (.1 x))

llSum :: LL Int -> Int
llSum x ? isNull (.1 x) = .0 x
        : (.0 x) + llSum (require (.1 x))
$ ./recur llLen '[1,[2,[3,null]]]'
3
$ ./recur llSum '[1,[2,[3,null]]]'
6
Branching: binary trees

A node can carry more than one optional child, giving a branching structure. A binary tree node has a payload and two independently optional subtrees, so it may have zero, one, or two children:

type BTree a = (a, ?(BTree a), ?(BTree a))

btreeExample :: BTree Int
btreeExample = (10, (5, Null, Null), (15, Null, Null))
$ ./recur btreeExample
[10,[5,null,null],[15,null,null]]

A balanced builder, sharing its subtree through let:

btreeBuild :: Int -> BTree Int
btreeBuild d ? d <= 0 = (1, Null, Null)
             : let sub = btreeBuild (d - 1)
               in (0, sub, sub)
$ ./recur btreeBuild 2
[0,[0,[1,null,null],[1,null,null]],[0,[1,null,null],[1,null,null]]]

Summing every payload reads best when the optional handling is factored into a helper, leaving the main function as the structural recursion it is:

btreeSum :: BTree Int -> Int
btreeSum x = .0 x + maybeSum (.1 x) + maybeSum (.2 x)

maybeSum :: ?(BTree Int) -> Int
maybeSum m ? isNull m = 0
           : btreeSum (require m)
$ ./recur btreeSum '[10,[5,null,null],[15,null,null]]'
30
List-guarded recursion: rose trees

The other permitted guard is [T]. An empty list is the natural base case, and arbitrary branching falls out as a list of children rather than a fixed number of optional slots:

type Rose a = (a, [Rose a])

roseExample :: Rose Int
roseExample = (1, [(2, []), (3, [])])
$ ./recur roseExample
[1,[[2,[]],[3,[]]]]

A builder for a complete binary rose tree, and a sum that folds the children:

roseBuild :: Int -> Rose Int
roseBuild d ? d <= 0 = (1, [])
            : let sub = roseBuild (d - 1)
              in (0, [sub, sub])

roseSum :: Rose Int -> Int
roseSum x = .0 x + fold (\acc child -> acc + roseSum child) 0 (.1 x)
$ ./recur roseBuild 2
[0,[[0,[[1,[]],[1,[]]]],[0,[[1,[]],[1,[]]]]]]
$ ./recur roseSum '[1,[[2,[]],[3,[]]]]'
6
Record form

The same rules apply to record declarations. The only surface difference is that fields are addressed by name instead of position; the wire format and the typecheck rules are identical to the tuple-alias form. This is an alternative encoding of the same linked list, so it lives in its own program below — two declarations of LL cannot share a module.

record LL where
  head :: Int
  tail :: ?LL

llRecordExample :: LL
llRecordExample = {head = 42, tail = {head = 7, tail = Null}}

llLen :: LL -> Int
llLen x ? isNull (.tail x) = 1
        : 1 + llLen (require (.tail x))
$ ./recrec llRecordExample
{"head":42,"tail":{"head":7,"tail":null}}
$ ./recrec llLen '{"head":1,"tail":{"head":2,"tail":null}}'
2
Parameterised recursion

Recursive types can carry type parameters, which thread through every recursive position:

record Container a where
  val :: a
  sub :: ?(Container a)

containerExample :: Container Int
containerExample = {val = 1, sub = {val = 2, sub = Null}}

containerLength :: Container a -> Int
containerLength x ? isNull (.sub x) = 1
                  : 1 + containerLength (require (.sub x))
$ ./recrec containerExample
{"val":1,"sub":{"val":2,"sub":null}}

containerLength stays polymorphic in the payload, which is what you want inside a program. It cannot be given a command line interface, though, so exporting it draws a warning and the program builds without that one command:

$ morloc make recrec.loc
Warning: skipping generic export 'containerLength'
Caution

Mutually recursive type aliases — two or more type definitions that reference each other in a cycle — are not supported. The frontend detects them and names the cycle:

recy.loc:5:1: error:
Mutual recursion between type definitions is not supported. Cycle: A, B
  |
5 | type A = (Int, B)
  | ^

The rule holds across general and language-specific scopes, and whether the cycle lives in one module or spans several.