Optimization: Pull polymorphism out of recursions

We can optimize some recursive functions like this:

```
map :: forall a b . (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

map' :: forall a b . (a -> b) -> [a] -> [b]
map' = mapInner
-- This function is monomorphic!
mapInner :: (a -> b) -> [a] -> [b]
mapInner f [] = []
mapInner f (x:xs) = f x : mapInner f xs
```

The latter version has two advantages:

The recursion will be compiled better, it won’t get a pointless extra unit argument, see

The function itself is more efficient, it doesn’t need type instantiations in the body of the recursive function.

We can’t do this in all cases, in particular we can’t do it if the recursive function is instantiated to different type arguments in the body, but this is unusual.

I think this is very similar to the “static argument transform” performed by GHC, except it focusses on type arguments rather than value arguments. Perhaps we want to do the general version? I think it’s probably safer in our case because we’re eager…

See also https://github.com/input-output-hk/plutus/blob/master/plutus-core/plutus-ir/src/PlutusIR/Transform/ThunkRecursions.hs#L16

Discussion:
```
Michael Peyton Jones
August 11, 2022 at 4:14 PM

This got in my brain so here are some thoughts:

I think the thing to do would be to do two passes, first a “call pattern analysis” pass that globally collects for each variable the set of call patterns for it that appear. Where a call pattern is probably just the list of arguments (type and term) it gets called with.

Then we can process these to determine the static arguments for each variable

I think GHC might also do something like “call pattern analysis” we could compare.

The call pattern analysis is nice and separate and can be tested independently, and also avoids re-traversing the program too much, since it should be doable a single pass.

Then we go through and decide what to do for each function declaration. Probably for starters we should just do non-recursive and singly-recursive functions.

We need a heuristic for when we do the transformation.

I think we should always lift out static type arguments, that seems like a clear win.

The thesis argues that you get the most benefit from performing the transformation on value arguments when there are at least two. We should verify this in our case. We could even make this configurable.

Michael Peyton Jones
August 10, 2022 at 5:56 PM

The thesis linked from the GHC wiki page is a good reference. Sounds like mutually recursive functions are tricky, which is a shame.

Roman Kireev
August 10, 2022 at 5:43 PM

I think it would be good to handle the most general case with term-level arguments.

Michael Peyton Jones
August 10, 2022 at 5:17 PM

https://gitlab.haskell.org/ghc/ghc/-/wikis/static-argument-transformation
```