Specifications of 'any', 'all', 'findIndices'

[Hannah Schroeter]

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.