[Haskell-cafe] how to optmize this code?
Daniel Fischer
daniel.is.fischer at googlemail.com
Thu Mar 31 12:18:46 CEST 2011
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.
More information about the Haskell-Cafe
mailing list