Newbie: finding the key/index of the min/max element

[Alex Martelli]

John J. Lee wrote:

> On Thu, 2 May 2002, Alex Martelli wrote:
> [...]
>> Given that performance considerations cannot necessarily be _kept_
>> apart, the main worth of FP is still as a thinking tool (in most cases).
> [...]
> 
> I'm surprised enough by this statement that I think I must have
> misunderstood it.  Surely the fact that performance can't always be
> separated from the rest of programming doesn't imply that 'higher-level',
> slower languages than C++ (such as Python) are only of value as thinking
> tools in most cases??

Of course not.  In performance issues, one must always distinguish
between "big-O" ones, and ones that boil down to mere multiplicative
constants.  The latter ones, Moore's Law takes care of -- a law that's
been operating for so long, that most problems can by now be tackled
most cost-effectively in higher-level languages (often with the help of
lower-level languages for small but crucial bottlenecks).  A program in
C or Python may typically have the same big-O performance, and
only differ by such multiplicative constants.

This is not necessarily the same for a program that works on the basis
of modifiable data or rebindable names (as a C or Python one may) versus 
one that doesn't, cannot, modify nor rebind.  Although I don't recall the
details, I believe there's some underlying result in the theory -- about
the potential slowdown in transforming Turing machines being bounded
if they're both alterable-tape, but not from one with an alterable tape to
one with a single-assignment tape.

Those "most cases" may be an overbid in practical terms -- with a _little_ 
bit of deviation from FP here and there (or maybe even without anything 
such, depending on how you understand and consider Haskell monads), many 
problems of practical importance may indeed be solved by near-pure FP (even 
though in theory infinitely more programs might not be thus solvable 
without big-O performance penalties).  As I understand, Erlang is in 
widespread real-world use, and Haskell and ML variants can obtain excellent 
performance on many problems.


Alex