'any' and 'all' compared with the rest of the Report
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
Hi, Eric> use meta-linguistic rewrite rules. So without knowing the Eric> specific optimizations that a compiler provides, I think it's Eric> safe to assume that the Prelude 'any' and 'all' *will* require Eric> linear space.) I don't hope so. If (||) and (&&) are implemented short circuiting, and = foldr (&&) True or = foldr (||) False "foldr", if applied lazily, will stop producing the list as soon as the outcome is available. (This will not be possible with "foldl" which is to be preferred for reductions with a strict operation.) Short circuiting means that (&&) or (||) will not force evaluation of their second argument if not necessary and it even should mean that they drop the space for their first argument as soon as they force evaluation of their second. (&&) x y = if x then y else False (||) x y = if x then True else y should forget everything about x as soon as the case is determined. Laziness of "map" in any, all :: (a -> Bool) -> [a] -> Bool any p = or . map p all p = and . map p will produce the list also only as far as it is required by "or" resp. "and". Thus, there should be no significant efficiency differences between the explicitly recursive definition and the "foldr" definition. However, there is a methodical difference. Consider a data type with 10 or 20 constructors (instead of 2). Do you like always to give a definition for each case seperately? Christoph -- Christoph Herrmann E-mail: herrmann@fmi.uni-passau.de WWW: http://brahms.fmi.uni-passau.de/cl/staff/herrmann.html
Eric Shade wrote: | Then I get to 'any' and 'all', whose specification | requires linear time and *linear* space when it should | run in constant space. I do not understand this remark. What do you mean by this? It is very difficult to say anything about space usage in a lazy functional language, but let us assume that a list "xs" is lazily produced in a one-by-one element fashion, and that noone else than the following expression is looking at that list. Then: any p xs Runs in constant space (with respect to the size of the list), for any of the discussed implementations of "any". Or did you mean something else? /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen phone:+46-31-772 5424 mailto:koen@cs.chalmers.se ----------------------------------------------------- Chalmers University of Technology, Gothenburg, Sweden
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
Hmmm, I'm slowly using track of this whole discusssion. But as a simple matter of fact: Using or not using optimizations (aka -O) changes the space behaviour of your Haskell programm. Sad as it may sound, it seems to be the price you have to pay for lazy evaluation. Of course it depends on the exact reading of "space behaviour" (temporary allocation vs. max heap usage), but it basically remains the same. On a positive side, this shifts debugging to a much higher level (searching for space leaks) than commonly done in imperative/OO/... languages (searching for semantic bugs in the first place, space leaks only come after that). Just my 2 cents, Sven
participants (5)
-
Ch. A. Herrmann -
Eric Shade -
Jerzy Karczmarczuk -
Koen Claessen -
Sven Panne