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.