[Haskell-cafe] Why doesn't GHC optimize recursive functions by converting them into `let`?

Petr P petr.mvd at gmail.com
Thu Nov 8 16:00:30 CET 2012


  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`.
(See
http://stackoverflow.com/questions/12999385/why-does-ghc-make-fix-so-confounding
)

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.
(See http://stackoverflow.com/q/13099203/1333025)

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121108/38826bf9/attachment.htm>


More information about the Haskell-Cafe mailing list