'any' and 'all' compared with the rest of the Report

[Jerzy Karczmarczuk]

Eric Shade:

> 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
   judge it.

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...)

Jerzy Karczmarczuk
Caen, France