[Haskell-cafe] how to optmize this code?

[Daniel Fischer]

On Thursday 31 March 2011 11:45:00, Christian Maeder wrote:
> Since we don't have a function sum' in the Prelude (should we have it?) 

I think we should.

> I wonder what happens if you just use "sum". Will the "sum" (based on 
> sum' so without -DUSE_REPORT_PRELUDE) be strict enough?

I don't know about other compiler's behaviour, but for GHC, it will be 
strict enough *if compiled with optimisations*, but not without (the 
strictness analyser runs only with optimisations turned on).
- Of course, given a type signature that allows strictness to be inferred.

However, the same holds for 'foldl (+) 0'. In fact, in the presence of a 
suitable type signature, with optimisations turned on, both produce nearly 
identical code (the order of parameters in the recursive loop is changed, 
sometimes parameter order can make a surprisingly large difference, but 
whether it's better to have the list or the accumulator first depends).

The difference is that the explicit recursion produces the better code even 
with optimisations turned off, except that the overload of (+) to use is 
not inlined, so the accumulator still builds a thunk, while with 
optimisations you get the specialised strict additions (+# resp. 
plusInteger, ...) so you have the strictness you need.

> 
> #ifdef USE_REPORT_PRELUDE
> sum                     =  foldl (+) 0
> product                 =  foldl (*) 1
> #else
> sum     l       = sum' l 0
>    where
>      sum' []     a = a
>      sum' (x:xs) a = sum' xs (a+x)
> product l       = prod l 1
>    where
>      prod []     a = a
>      prod (x:xs) a = prod xs (a*x)
> #endif
> 
> Cheers C.
> 
> P.S.
> 
> isMultiple a = any ((== 0) . mod a)

For Int (and most other types),

isMultiples a = any ((== 0) . rem a)

will be faster (mod is implemented using rem).
However, for checks other than comparisons with 0, one needs to be aware of 
the differences of rem and mod, the latter does what one would expect, rem 
can badly surprise the unaware.