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

Eric Shade EricShade@smsu.edu
Mon, 22 Jan 2001 11:19:42 -0600

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