List.or, List.any and List.elem
Andreas Abel
abela at chalmers.se
Thu Jun 12 14:45:02 UTC 2014
Curious on whether I should prefer
List.any f
over
List.or . List.map f
I consulted the source code at
http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-List.html
I found that according to the Report, they are identical, but there are
fusion rules for List.any which look like I should prefer it to the said
composition.
What puzzled me is that later,
List.elem x
is
List.any (x ==)
according to the Report, but GHC defines it recursively, *without*
fusion rules. I wonder
Q1: Should I prefer List.any (x==) then, since it gives opportunity to
fusion?
Q2: Why is then List.elem defined recursively?
Q3: Where is the comment that justifies the taken design decisions??
Cheers,
Andreas
#ifdef USE_REPORT_PRELUDE
any p = or . map p
all p = and . map p
#else
any _ [] = False
any p (x:xs) = p x || any p xs
all _ [] = True
all p (x:xs) = p x && all p xs
{-# NOINLINE [1] any #-}
{-# NOINLINE [1] all #-}
{-# RULES
"any/build" forall p (g::forall b.(a->b->b)->b->b) .
any p (build g) = g ((||) . p) False
"all/build" forall p (g::forall b.(a->b->b)->b->b) .
all p (build g) = g ((&&) . p) True
#-}
#endif
-- | 'elem' is the list membership predicate, usually written in infix form,
-- e.g., @x \`elem\` xs at . For the result to be
-- 'False', the list must be finite; 'True', however, results from an
element equal to @x@ found at a finite index of a finite or infinite list.
elem :: (Eq a) => a -> [a] -> Bool
-- | 'notElem' is the negation of 'elem'.
notElem :: (Eq a) => a -> [a] -> Bool
#ifdef USE_REPORT_PRELUDE
elem x = any (== x)
notElem x = all (/= x)
#else
elem _ [] = False
elem x (y:ys) = x==y || elem x ys
notElem _ [] = True
notElem x (y:ys)= x /= y && notElem x ys
#endif
--
Andreas Abel <>< Du bist der geliebte Mensch.
Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden
andreas.abel at gu.se
http://www2.tcs.ifi.lmu.de/~abel/
More information about the Libraries
mailing list