Sven Panne wrote:
Jan-Willem Maessen - Sun Labs East wrote:
[...] The actual problem is function arguments. GHC can't do worker-wrapper unless a function is strict. Often we end up with something like this:
data Tree a = Branch !Int a (Tree a) (Tree a)
lookfor :: Int -> Tree a -> Maybe a lookfor Leaf key = Nothing lookfor (Branch k v l r) key | key==k = Just v | key < k = lookfor l key | otherwise = lookfor r key
Here we don't use "key" in the first clause, so GHC isn't allowed to unbox. Most of the uses of Int# that I've seen in library code have been workarounds to this problem. [...]
If that's the only concern, there is no real problem. One can do:
a) Help GHC a bit by hand with something like
lookfor Leaf key | key == key = Nothing
or
lookfor Leaf key = key `seq` Nothing
Not very nice, but a "traditional" way of improving strictness.
And, of course, we need to remember to do it uniformly everywhere in our program. Figuring out where to put these things isn't always easy. And frankly, I'd love to stamp out the use of equality for strictification once and for all.
b) Use GHC's -O2 flag, enabling specialization over constructors, which is exactly what you're looking for, see the "Game Plan" comment at the beginning of
I had a fascinating conversation with Simon P-J some years back on exactly this subject. It's a lovely optimization. But (as you point out) I need to do -ddump-simpl (and understand the results) to be sure the compiler's done it for me. Tomorrow, the compiler could (for some reason) decide not to do it anymore. It's all terribly fragile. Fundamentally, the idea here is to give a library implementor another tool to say what they mean. They can be assured of reasonable-looking code that's still tuned to run like the blazes---with the confidence of a types backing them up. They don't have to go crawling through their code or the simplifier output a line at a time. Unboxed types were designed with exactly that goal in mind. But they're not portable. I'm suggesting a lightweight, simple wrapper which would be portable. Perhaps that wrapper should even be named "Int#"!
Using "-O2 -ddump-simpl" with your (slightly corrected) example, one can see that the Ints are indeed unboxed during recursion.
Cheers, S.