Specifications of 'any', 'all', 'findIndices'
Mon, 22 Jan 2001 22:29:50 +0100
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"/
> 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.