Specifications of 'any', 'all', 'findIndices'
I have some questions about the specifications of 'any', 'all', and 'findIndices' in the Haskell 98 reports. The specifications of 'any' and 'all' are any p = or . map p all p = and . map p While this is correct, it seems to me that it generates a lot of garbage because map will produce a list of Booleans until 'any' sees a True or 'all' sees a False. 'elem' and 'notElem' inherit the problem because they're defined in terms of 'any' and 'all'. I realize that this is only a specification, but Hugs at least uses this as its implementation. It seems clearer and more efficient to me to use the following definitions: any p [] = False any p (x:xs) = p x || any p xs all p [] = True all p (x:xs) = p x && all p xs leave 'elem' and 'notElem' as is, then define and = notElem False or = elem True There is a similar problem with findIndices, whose specification is findIndices p xs = [i | (x,i) <- zip xs [0..], p x] While this is admittedly cool, it also seems to generate a lot of garbage by producing pairs only to throw them away. I'm not yet up to speed on the implementation of lazy functional languages, so it may be that in all of these cases the compiler can easily optimize away the garbage. If so, it would be nice to see some documentation for non-wizards that explains what kinds of optimizations one can reasonably expect (like tail-recursion elimination in Scheme). Even if the apparent inefficiencies melt away, I think that my versions of 'any', 'all', 'and', and 'or' are clearer as specification than the current ones. -- Dr. Eric Shade, Associate Professor Computer Science Department (CSAB Accredited) Southwest Missouri State University
Hello! On Mon, Jan 22, 2001 at 11:19:42AM -0600, Eric Shade wrote:
I have some questions about the specifications of 'any', 'all', and 'findIndices' in the Haskell 98 reports. The specifications of 'any' and 'all' are
any p = or . map p all p = and . map p
While this is correct, it seems to me that it generates a lot of garbage because map will produce a list of Booleans until 'any' sees a True or 'all' sees a False. 'elem' and 'notElem' inherit the problem because they're defined in terms of 'any' and 'all'. I realize that this is only a specification, but Hugs at least uses this as its implementation. It seems clearer and more efficient to me to use the following definitions:
any p [] = False any p (x:xs) = p x || any p xs
all p [] = True all p (x:xs) = p x && all p xs
leave 'elem' and 'notElem' as is, then define
and = notElem False or = elem True
There is a similar problem with findIndices, whose specification is
findIndices p xs = [i | (x,i) <- zip xs [0..], p x]
While this is admittedly cool, it also seems to generate a lot of garbage by producing pairs only to throw them away.
I'm not yet up to speed on the implementation of lazy functional languages, so it may be that in all of these cases the compiler can easily optimize away the garbage. If so, it would be nice to see some documentation for non-wizards that explains what kinds of optimizations one can reasonably expect (like tail-recursion elimination in Scheme).
Depends on the implementation. GHC might remove some of the garbage, at least, see the GHC documentation ("good producers"/"good consumers"/ "cheap deforestation").
Even if the apparent inefficiencies melt away, I think that my versions of 'any', 'all', 'and', and 'or' are clearer as specification than the current ones.
I don't think so. The specifications are quite concise. Kind regards, Hannah.
Hannah Schroeter wrote:
Eric Shade wrote:
I have some questions about the specifications of 'any', 'all', and 'findIndices' ... any p = or . map p all p = and . map p
...It seems clearer and more efficient to me to use the following definitions:
any p [] = False any p (x:xs) = p x || any p xs
all p [] = True all p (x:xs) = p x && all p xs
...
Even if the apparent inefficiencies melt away, I think that my versions of 'any', 'all', 'and', and 'or' are clearer as specification than the current ones.
I don't think so. The specifications are quite concise. Hannah.
Just a moment, please. Do we speak about "concise" or "clear"? Johannes Waldman makes the same fusion, first saying that it is concise, and terminating with a statement on clear programming. Personally I am a convinced lazy programmer, I adore concise and obfuscated style, and I used with some internal pleasure the original definitions, until I started using Haskell for teaching. (I do not teach Haskell, we *use* it on compilation stuff, some- times on some graphics projects, and they have to learn it "off-line".) THREE TIMES I've been asked about that. Somebody quite clever remarked that any or all are *typical* cases for fold rather than for map. There is plenty of historical accidents in the standard prelude. [I won't complain any more about the Num stuff...] Johannes Waldmann last sentence:
Who said this, "premature optimization is the root of all evil".
Who said that what Eric Shade proposes is an evil optimization, while a curried "pearl": "any p = or . map p" is a nice shorthand, plenty of vitamines, especially for beginners. BTW., why not promote something like any = (or .) . map to make everybody happy? Jerzy Karczmarczuk Caen, France PS. Johannes Waldman raises some doubts:
so it's not at all clear that the above implementation is indeed more efficient.
Please, don't speculate. If you have something to say in this context, perform some tests. I did it with Hugs. Eric Shade implementation seems to be indeed more efficient, but very slightly (on my test, I won't claim anything general).
Hello! On Tue, Jan 23, 2001 at 09:50:37AM +0000, Jerzy Karczmarczuk wrote:
Hannah Schroeter wrote:
Eric Shade wrote: [...]
I don't think so. The specifications are quite concise. Hannah.
Just a moment, please. Do we speak about "concise" or "clear"?
I really probably spoke about "clear". However, I'm not a native English speaker so I wasn't aware of the difference between those two words until just now, when I looked them up. In this case, I find any p = or . map p rather clear, and almost as concise as it can get (any = (or .) . map even is shorter, thus perhaps more concise, but IMHO less clear for people not so apt in a combinatorial style).
[...]
"off-line".) THREE TIMES I've been asked about that. Somebody quite clever remarked that any or all are *typical* cases for fold rather than for map.
You / they probably mean something like this: any p = foldr (\ elem temp_res = p elem || temp_res) False
[...]
Please, don't speculate. If you have something to say in this context, perform some tests. I did it with Hugs. Eric Shade implementation seems to be indeed more efficient, but very slightly (on my test, I won't claim anything general).
Hugs is only a good test for --- hugs :-) However, just tested with GHC and results were these: hannah@c3po:/tmp $ cat x.hs my_any p = or . map p main = print (my_any (== 0) [1..10000000]) hannah@c3po:/tmp $ time ./x False real 0m6.003s user 0m5.917s sys 0m0.024s hannah@c3po:/tmp $ cat y.hs my_any p [] = False my_any p (x:xs) = p x || my_any p xs main = print (my_any (== 0) [1..10000000]) hannah@c3po:/tmp $ time ./y False real 0m4.403s user 0m4.330s sys 0m0.016s GHC was 4.08. Kind regards, Hannah.
I think a specification
any p = or . map p
is much more concise than the implementation
any p [] = False any p (x:xs) = p x || any p xs
another reason to prefer the higher-level variant is that the compiler can apply fusion laws, as in any p . map f = or . map p . map f = or . map (p . f) (one could also do this starting from the second definition, but then the compiler's first step would be to derive the higher-level version from it, I guess) so it's not at all clear that the above implementation is indeed more efficient. I'd rather write clear code, than worry about efficiency too early. Who said this, "premature optimization is the root of all evil". best regards -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --
Johannes Waldmann wrote:
... I'd rather write clear code, than worry about efficiency too early. Who said this, "premature optimization is the root of all evil".
I've always attributed this to Donald Knuth: Premature optimization is the root of all evil in programming. Though I can't confirm it. I do find this similar statement in his "Structured Programming with go to Statements" (Computing Surveys 6 4, Dec 1974): ... premature emphasis on efficiency is a big mistake which may well be the source of most programming complexity and grief. Note also one of Alan Perlis's epigrams: Optimization hinders evolution. (See http://www.cs.yale.edu/homes/perlis-alan/quotes.html) - Mark Tullsen
Eric Shade wondered: | I have some questions about the specifications of | 'any', 'all', and 'findIndices' in the Haskell 98 | reports. [...] it seems to me that it generates a lot | of garbage because map will produce a list of Booleans | [...] Several people have already commented on this. What I want to add is the following. The definitions in the Haskell report are a *specification*, not an implementation. It probably depends on the compiler which particular implementation runs faster. Therefore, the Haskell report provides a clear (yes, this is debatable) *possible* implementation, and the compiler writer is free to implement this in whatever way (s)he likes. As long as the implementation has the same functional behavior as the specification in the report. /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
Koen:
The definitions in the Haskell report are a *specification*, not an implementation. It probably depends on the compiler which particular implementation runs faster.
Therefore, the Haskell report provides a clear (yes, this is debatable) *possible* implementation, and the compiler writer is free to implement this in whatever way (s)he likes. As long as the implementation has the same functional behavior as the specification in the report.
Hear, hear. What I in turn would like to add is that specifications like any p = or . map p are on a higher level of abstraction than definitions like any p [] = False any p (x:xs) = p x || any p xs This makes it easier to find different implementations, which makes it easier to adapt the implementation to fit different architectures. The first specification is, for instance, directly data parallel which facilitates an implementation on a parallel machine or in hardware. Björn Lisper
Koen Claessen wrote: (about the definitions of any, all, etc.)
The definitions in the Haskell report are a *specification*, not an implementation. It probably depends on the compiler which particular implementation runs faster.
Therefore, the Haskell report provides a clear (yes, this is debatable) *possible* implementation, and the compiler writer is free to implement this in whatever way (s)he likes. As long as the implementation has the same functional behavior as the specification in the report.
I am sorry, but any p = or . map p is not an implementation-neutral specification, a *functional* specification. This is a very concrete way of doing things. As everybody knows, this is a folding process. Of course, 'or' uses (normally, again, according to the Report if I am not mistaken) 'foldr', and it is essentially trivial to get rid of 'map', putting (||) and 'p' together in the fold function, but: 1. Perhaps it is too optimistic to think that the compilers will to that optimisation by themselves. Hugs uses literally this "specification" 2. I maintain my opinion that from the pedagogical point of view this definition is imperfect. I think that the specification should say no more nor less what 'any', 'notElem' etc. functions provide, and put (possibly) in the Report that possible implementations are (...) But the generation of this "garbage", the intermediate list of booleans, whether real or virtual only, goes beyond the semantics of 'all', etc. As Koen said, several people already commented on that. And, I am afraid that this will continue. I can promise you that... Bjorn Lisper adds:
... What I in turn would like to add is that specifications like
any p = or . map p
are on a higher level of abstraction than definitions like
any p [] = False any p (x:xs) = p x || any p xs
This makes it easier to find different implementations, which makes it easier to adapt the implementation to fit different architectures. The first specification is, for instance, directly data parallel which facilitates an implementation on a parallel machine or in hardware.
Björn Lisper
Pardon? map is data parallel. foldr not so obviously... I am not sure about this higher level of abstraction. Unless, of course, we want to use generalized, monadic maps, but then, also folds. And we will produce, say, trees of boolean garbage instead of lists. Jerzy Karczmarczuk
Pardon? map is data parallel. foldr not so obviously...
Sorry, a slip on my behalf: foldr in general is not data parallel, but if the function being folded with is associative then foldr can be implemented by a parallel (balanced binary-tree) reduction in time O(log n), where n is the length of the list. A compiler needs the information that or is a fold over an associative operation in order to employ such a parallel implementation. Björn Lisper
participants (7)
-
Bjorn Lisper -
Eric Shade -
Hannah Schroeter -
Jerzy Karczmarczuk -
Johannes Waldmann -
Koen Claessen -
Mark Tullsen