'any' and 'all' compared with the rest of the Report
Wed, 24 Jan 2001 11:08:54 +0000
> It would be one thing if the
> Report were littered with functions whose specifications were
> obviously not intended as implementations. But 'any', 'all', and
> 'findIndices' were the only inefficient ones I noticed out of the
> entire Report.
> And it's obvious that clarity is not the only goal in the
> specifications. For example, why bother to write a messy O(log n)
> version of x^n when the following is more clear *and* more concise?
> x ^ n | n >= 0 = product (replicate n x)
> _ ^ _ = error "Prelude.^: negative exponent"
1. elem, notElem, etc. follow the same pattern.
2. The rational number package is not too optimal, as far as I can
3. Now, now, you fight against the inefficiency of linear algorithms
which use map, and here you propose EXACTLY the same for the product?
(Unless, as Bjorn hopes, one day the compilers will do all the
parallelisation/logarithmoptimisation for us.)
BY THE WAY.
The power algorithm which uses the binary splitting of the exponent
is very popular in the pedagogical context, and sometimes abused, for
example to compute huge powers of "infinite precision" integers.
If we assume that the multiplication algorithm for two long numbers
of lengths M and N is proportional to M*N, see for yourself what is
the asymptotic complexity of the power which uses the logarithmic
method vs. the linear one. You might be surprised. //Sorry for
deviating from Haskell...//
On the other hand, having an even more generic logarithmic iterator
for associative operations seems to me a decent idea. You might even
need it one day (I had this pleasure) for the multiplication of an
object by an integer, where the object was so non-standard, that the
only way of implementing N*X was: X+X+...+X.
So, Eric, don't call this algorithm "messy". (I suspect that you
are joking, but ALL comp. sci students should know it, and perhaps
some of them read this list and may believe you...)