'any' and 'all' compared with the rest of the Report

Ch. A. Herrmann herrmann@infosun.fmi.uni-passau.de
Tue, 23 Jan 2001 20:22:07 +0100 (MET)


    Eric> use meta-linguistic rewrite rules.  So without knowing the
    Eric> specific optimizations that a compiler provides, I think it's
    Eric> safe to assume that the Prelude 'any' and 'all' *will* require
    Eric> linear space.)

I don't hope so. If (||) and (&&) are implemented short circuiting,
and        = foldr (&&) True
or         = foldr (||) False

"foldr", if applied lazily, will stop producing the list as soon
as the outcome is available. (This will not be possible with
"foldl" which is to be preferred for reductions with a strict
operation.) Short circuiting means that (&&) or (||) will not
force evaluation of their second argument if not necessary and
it even should mean that they drop the space for their first argument
as soon as they force evaluation of their second.

(&&) x y = if x then y else False 
(||) x y = if x then True else y

should forget everything about x as soon as the case
is determined.

Laziness of "map" in

any, all  :: (a -> Bool) -> [a] -> Bool
any p      = or  . map p
all p      = and . map p

will produce the list also only as far as it is required by 
"or" resp. "and".

Thus, there should be no significant efficiency differences between
the explicitly recursive definition and the "foldr" definition.

However, there is a methodical difference. Consider a data type with
10 or 20 constructors (instead of 2). Do you like always to give a 
definition for each case seperately?

 Christoph Herrmann
 E-mail:  herrmann@fmi.uni-passau.de
 WWW:     http://brahms.fmi.uni-passau.de/cl/staff/herrmann.html