Hi,
recently I found out that some recursive functions can be greatly optimized just by rewriting them using `let` so that they're not recursive themselves any more (only the inner let is). To give an example:
> fix :: (a -> a) -> a
> fix f = f (fix f)
isn't optimized, because it's a recursive function and so it isn't inlined or anything. However, defining it as
> fix f = let x = f x in x
makes it much more efficient, since `fix` is not recursive any more, so it gets inlined and then optimized for a given argument `f`.
Another example is the well-known generic catamorphism function:
> newtype Fix f = Fix { unfix :: f (Fix f) }
>
> catam :: (Functor f) => (f a -> a) -> (Fix f -> a)
> catam f = f . fmap (catam f) . unfix
is not optimized. When `catam` is used on a data structure such as [] or a tree, at each level `fmap` creates new constructors that are immediately consumed by `f`. But when written as
> catam f = let u = f . fmap u . unfix in u
this gets inlined and then optimized, and constructor creation/consumption is fused into very effective code.
As one comment asked, this seems like something GHC could do automatically. Would it be difficult? Is there a reason against it? I suppose in cases where it doesn't help, the additional `let` would get optimized away, so no harm would be done. And in cases like `fix` or `catam` the gain would be substantial.
Best regards,
Petr