Non-structural recursion

You can write recursive functions that do not follow the structure of a datatype. Some of them are problematic and to be avoided, while others are legitimate. We will review several patterns here.

Non-termination

Non-terminating functions are an important class of recursive functions that are non-structural. Here is a first, small example:

loop :: Integer -> Integer
loop x = loop x

Here is an example derivation:

  loop 5
= loop 5
= loop 5
= …

Clearly, this derivation never terminates; it just repeats itself endlessly. If you have inadvertently invoked such a non-terminating function call in GHCi, you can abort it with the Ctrl + C key combination.

While the loop function is blatantly non-terminating, the source of non-termination may often not be so apparent when it dresses up in a lot more code (such as mutually recursive functions).

A slightly different pattern of non-termination is the following:

diverge :: [Integer...