Specifications of 'any', 'all', 'findIndices'
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
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