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

Eric Shade EricShade@smsu.edu
Tue, 23 Jan 2001 12:35:19 -0600

I didn't mean to get into a discussion about 'specification
vs. implementation' or 'clarity vs. conciseness', although those are
important distinctions.  In my original post I didn't do a good job of
putting my objections in the proper context, so let me take one more
whack at it and then I'll leave it alone.

As a newcomer to Haskell, I read the entire Report, including all of
the purely functional code in the Prelude and Libraries (I glossed
over the monadic stuff initially).  The code is not only clear as a
*specification*, but also seems perfectly suitable as a default
*implementation*.  All the code seemed to have the time and space
requirements that one would expect.

Then I get to 'any' and 'all', whose specification requires linear
time and *linear* space when it should run in constant space.  (By the
way, I checked and GHC does *not* use the Prelude definitions but
rather the obvious recursive ones, and most of its optimizations based
on "good consumers/producers" use meta-linguistic rewrite rules.  So
without knowing the specific optimizations that a compiler provides, I
think it's safe to assume that the Prelude 'any' and 'all' *will*
require linear space.)

This is jarring; all the other code is clear *and* efficient, but
'any' and 'all' are not.  I start to question whether I really
understand the language after all.  (Do 'or' and 'map' work
differently than I thought?  Did I misunderstand laziness? ...)  After
all, why would the authors (who presumably know more about the
language than anyone on the planet) intentionally provide inefficient
code in *this* case when they provided efficient code for all the
*other* functions?  This is why I don't think that the specifications
are good; they're OK in isolation but not in the context of the rest
of the Report.  For me (and apparently for others), these
specifications didn't enhance my understanding; they led me to
question it.

I know that the Report clearly says that these are just
specifications, but that's one short paragraph.  When I read 20 pages
of code that appears to be reasonably efficient as well, I assume that
that's by design and not accident.  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"

Since the specifications of 'any' and 'all' are part of the Report,
they are part of the documentation for the language.  They should be
judged by how well they help people understand the language.  The
direct recursive versions, though slightly less concise, are equally
clear and will not cause any confusion.  That's why I prefer them.

Dr. Eric Shade, Associate Professor
Computer Science Department (CSAB Accredited)
Southwest Missouri State University