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