[clean-list] More transformations

[Erik Zuurbier]

Ronny wrote:

>As you mentioned yourself the functions are not the same. They
>have different termination behaviour, but because length returns
>a 32 bit signed Int they can also differ for long lists. So the
>Clean compiler can't do this transformation.

This triggers the question: can you do transformations only if the
result will be (in some sense) equal to the original function, or can you
also do transformation if the result is (in some sense) better than the
original, e.g. better termination behaviour, fewer overflow errors etc.

>The heart of the matter is that Ints are always fully evaluated.
>If length were to return a result of type
>
>   :: Nat = Zero | Succ Nat
>
>then it wouldn't have to traverse the whole list. Deforestation
>could get rid of the intermediate Nat value to obtain the check
>function you want. This representation of natural numbers is of
>course inefficient for most purposes.

This triggers the possibility that the Clean-compiler would start its
compilation proces with the above Nat type everywhere the programmer
specified Int, then do the transformations, and then replace remaining
Nats by Int for performance reasons.

Erik Zuurbier