[Haskell-cafe] Re: Write Haskell as fast as C. [Was: Re: GHC predictability]

[Philippa Cowderoy]

On Fri, 16 May 2008, Don Stewart wrote:

> I don't understand what's ugly about:
> 
>         go s l x | x > m      = s / fromIntegral l
>                  | otherwise  = go (s+x) (l+1) (x+1)
> 

I suspect you've been looking at low-level code too long. How about the 
total lack of domain concepts?

Try:

mean n m = let (sum, length, _) = go (0,0,n)
             in sum / fromIntegral length
        where
            go :: (Double, Int, Double) -> (Double, Int, Double)
            go t@(s,l,x) | x > m      = t
                         | otherwise  = go (s+x) (l+1) (x+1)

as a starting point. I might consider generalising to a "while" HOF while 
I'm at it, because ultimately this is a while loop. Admittedly that would 
be relying on the implementation doing a little inlining, which you're not 
reliant on.

Given the audience it'd be good to see some of the working to pull it off 
via fusion in a comment too:

-- [1 .. d ] = unfoldr (let f n | n > d = Nothing 
--                          f n = Just (n,n+1) in f) 1
-- sum = foldr ...
-- length = foldr ...
-- sumAndLength = foldr ... (as calculated from the above)
-- mean [1 .. d] = s / l where
--   (sum, length) = sumAndLength [1 .. d]
--                 = sumAndLength . unfoldr ... 
--                 = foldr ... . unfoldr ...
--                 = ...

Some things it might be nice to have and/or know about:

* We really ought to be able to build the sumAndLength fold by building 
the appropriate tuple and tuple function from its components - with there 
being a standard idiom for naming them, and a library of such things to 
hand. Same thing for go, too - this means we retain the domain concepts in 
its implementation by default. The interesting thing about go is that we 
ourselves running the guts of an unfold at the same time, which means it 
supplies our termination criteria - I suspect I ought to post a 'most 
general' form of go on that basis soon?
* Does nesting unboxed tuples work appropriately?

I was about to suggest a standard way of doing the wiring for the tupling 
as well, but so long as nesting unboxed tuples works and the optimiser 
'gets it' then there's an arrow instance that ought to do nicely!

While not quite as low-level, the resulting code should hopefully be easy 
bait for GHC's optimiser (if not, someone please yell!), while both 
retaining much of the domain info of the original code and conveying much 
about how it's made to go fast.

> Nothing beats understanding what you're writing at all levels of abstraction.
> 

How about ensuring that a casual reader can do the same quickly?

-- 
flippa at flippac.org

Performance anxiety leads to premature optimisation