Unexpected lack of optimisation

[Simon Peyton-Jones]

| The situation in Neil's code is almost identical, except that the
| top-level case expression is on a value passed by environment, not by
| function argument.

Interesting thought.  I think you're describing a possible extension to the SpecConstr transformation described in "Call pattern specialisation for Haskell" (http://research.microsoft.com/%7Esimonpj/papers/spec-constr)

   f x = let g y = ...case x of { z:zs -> e1; [] -> e2 } ...
          in
          ...case x of
                z:zs -> if ... then g 3 else g 4
                []   -> ...

Here 'x' is free in 'g', but x's value is known at g's call sites.  It's not enough just to know "x is a cons" inside g; we must also have access to z,zs.  So perhaps the thing to do is to imagine lambda-lifting 'g' to become 'gl' thus:

  gl x y = ...case x of { z:zs -> e1; [] -> e2 } ...

  f x = ...case x of
                z:zs -> if ... then gl x 3 else gl x 4
                []   -> ...

Now the SpecConstr transformation will apply nicely.  And it's arguably a bad shortcoming that currently the mere act of lambda lifting can affect how effective SpecConstr is.

Of course, we only want to lambda-lift wrt the parameters that'll be specialised, so this transformation probably wants to be done at the same time as the rest of SpecConstr. I don't have much idea of how hard that'd be, but it's a nice idea.

Simon