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