List.lhs 24.5 KB
 simonmar committed Jun 28, 2001 1 \begin{code}  dterei committed Jun 18, 2011 2 {-# LANGUAGE Trustworthy #-}  3 {-# LANGUAGE CPP, NoImplicitPrelude, MagicHash #-}  Ross Paterson committed Jan 20, 2008 4 {-# OPTIONS_HADDOCK hide #-}  5   simonmar committed Apr 26, 2002 6 7 8 9 10 11 12 13 14 15 16 17 18 ----------------------------------------------------------------------------- -- | -- Module : GHC.List -- Copyright : (c) The University of Glasgow 1994-2002 -- License : see libraries/base/LICENSE -- -- Maintainer : cvs-ghc@haskell.org -- Stability : internal -- Portability : non-portable (GHC Extensions) -- -- The List data type and its operations -- -----------------------------------------------------------------------------  simonmar committed Jun 28, 2001 19   ross committed Feb 03, 2005 20 -- #hide  simonmar committed Jun 28, 2001 21 module GHC.List (  Don Stewart committed Mar 05, 2008 22  -- [] (..), -- Not Haskell 98; built in syntax  simonmar committed Jun 28, 2001 23 24  map, (++), filter, concat,  Don Stewart committed Mar 05, 2008 25  head, last, tail, init, null, length, (!!),  simonmar committed Sep 28, 2004 26  foldl, scanl, scanl1, foldr, foldr1, scanr, scanr1,  simonmar committed Jun 28, 2001 27 28 29 30  iterate, repeat, replicate, cycle, take, drop, splitAt, takeWhile, dropWhile, span, break, reverse, and, or, any, all, elem, notElem, lookup,  simonmar committed Sep 28, 2004 31  concatMap,  simonmar committed Jun 28, 2001 32  zip, zip3, zipWith, zipWith3, unzip, unzip3,  simonmar committed Sep 28, 2004 33  errorEmptyList,  simonmar committed Jun 28, 2001 34   simonmar committed Sep 28, 2004 35 #ifndef USE_REPORT_PRELUDE  simonmar committed Jun 28, 2001 36 37 38 39 40 41 42  -- non-standard, but hidden when creating the Prelude -- export list. takeUInt_append #endif ) where  simonmar committed Jul 03, 2001 43 import Data.Maybe  simonmar committed Jun 28, 2001 44 45 46 47 48 49 50 import GHC.Base infixl 9 !! infix 4 elem, notElem \end{code} %*********************************************************  Don Stewart committed Mar 05, 2008 51 %* *  simonmar committed Jun 28, 2001 52 \subsection{List-manipulation functions}  Don Stewart committed Mar 05, 2008 53 %* *  simonmar committed Jun 28, 2001 54 55 56 %********************************************************* \begin{code}  ross committed Sep 01, 2003 57 -- | Extract the first element of a list, which must be non-empty.  simonmar committed Jun 28, 2001 58 59 60 head :: [a] -> a head (x:_) = x head [] = badHead  pcapriotti committed Jul 25, 2012 61 {-# NOINLINE [1] head #-}  simonmar committed Jun 28, 2001 62   Ian Lynagh committed Aug 05, 2008 63 badHead :: a  simonmar committed Jun 28, 2001 64 65 66 badHead = errorEmptyList "head" -- This rule is useful in cases like  Don Stewart committed Mar 05, 2008 67 -- head [y | (x,y) <- ps, x==t]  simonmar committed Jun 28, 2001 68 {-# RULES  Don Stewart committed Mar 05, 2008 69 70 71 72 "head/build" forall (g::forall b.(a->b->b)->b->b) . head (build g) = g (\x _ -> x) badHead "head/augment" forall xs (g::forall b. (a->b->b) -> b -> b) . head (augment g xs) = g (\x _ -> x) (head xs)  simonmar committed Jun 28, 2001 73 74  #-}  ross committed Sep 01, 2003 75 -- | Extract the elements after the head of a list, which must be non-empty.  simonmar committed Jun 28, 2001 76 77 78 79 tail :: [a] -> [a] tail (_:xs) = xs tail [] = errorEmptyList "tail"  ross committed Sep 01, 2003 80 -- | Extract the last element of a list, which must be finite and non-empty.  simonmar committed Jun 28, 2001 81 82 83 84 85 86 87 last :: [a] -> a #ifdef USE_REPORT_PRELUDE last [x] = x last (_:xs) = last xs last [] = errorEmptyList "last" #else -- eliminate repeated cases  Don Stewart committed Mar 05, 2008 88 89 last [] = errorEmptyList "last" last (x:xs) = last' x xs  simonmar committed Jun 28, 2001 90  where last' y [] = y  Don Stewart committed Mar 05, 2008 91  last' _ (y:ys) = last' y ys  simonmar committed Jun 28, 2001 92 93 #endif  ross committed Sep 01, 2003 94 -- | Return all the elements of a list except the last one.  Ian Lynagh committed Sep 11, 2009 95 -- The list must be non-empty.  simonmar committed Jun 28, 2001 96 97 98 99 100 101 102 103 104 105 init :: [a] -> [a] #ifdef USE_REPORT_PRELUDE init [x] = [] init (x:xs) = x : init xs init [] = errorEmptyList "init" #else -- eliminate repeated cases init [] = errorEmptyList "init" init (x:xs) = init' x xs where init' _ [] = []  Don Stewart committed Mar 05, 2008 106  init' y (z:zs) = y : init' z zs  simonmar committed Jun 28, 2001 107 108 #endif  ross committed Sep 01, 2003 109 -- | Test whether a list is empty.  simonmar committed Jun 28, 2001 110 111 112 113 null :: [a] -> Bool null [] = True null (_:_) = False  Ian Lynagh committed Feb 21, 2010 114 -- | /O(n)/. 'length' returns the length of a finite list as an 'Int'.  ross committed Sep 01, 2003 115 116 -- It is an instance of the more general 'Data.List.genericLength', -- the result type of which may be any kind of number.  simonpj@microsoft committed May 08, 2006 117 118 119 120 121 122 length :: [a] -> Int length l = len l 0# where len :: [a] -> Int# -> Int len [] a# = I# a# len (_:xs) a# = len xs (a# +# 1#)  simonmar committed Jun 28, 2001 123   ross committed Sep 01, 2003 124 125 126 127 128 -- | 'filter', applied to a predicate and a list, returns the list of -- those elements that satisfy the predicate; i.e., -- -- > filter p xs = [ x | x <- xs, p x]  pcapriotti committed Jul 25, 2012 129 {-# NOINLINE [1] filter #-}  simonmar committed Jun 28, 2001 130 filter :: (a -> Bool) -> [a] -> [a]  simonmar committed Feb 05, 2002 131 132 133 filter _pred [] = [] filter pred (x:xs) | pred x = x : filter pred xs  Don Stewart committed Mar 05, 2008 134  | otherwise = filter pred xs  simonmar committed Jun 28, 2001 135   simonmar committed Feb 05, 2002 136 {-# NOINLINE [0] filterFB #-}  Ian Lynagh committed Aug 05, 2008 137 filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b  simonmar committed Jun 28, 2001 138 filterFB c p x r | p x = x c r  Don Stewart committed Mar 05, 2008 139  | otherwise = r  simonmar committed Jun 28, 2001 140 141  {-# RULES  simonmar committed Feb 05, 2002 142 "filter" [~1] forall p xs. filter p xs = build (\c n -> foldr (filterFB c p) n xs)  Don Stewart committed Mar 05, 2008 143 144 "filterList" [1] forall p. foldr (filterFB (:) p) [] = filter p "filterFB" forall c p q. filterFB (filterFB c p) q = filterFB c (\x -> q x && p x)  simonmar committed Jun 28, 2001 145 146 147 148 149 150 151 152 153 154 155 156  #-} -- Note the filterFB rule, which has p and q the "wrong way round" in the RHS. -- filterFB (filterFB c p) q a b -- = if q a then filterFB c p a b else b -- = if q a then (if p a then c a b else b) else b -- = if q a && p a then c a b else b -- = filterFB c (\x -> q x && p x) a b -- I originally wrote (\x -> p x && q x), which is wrong, and actually -- gave rise to a live bug report. SLPJ.  ross committed Sep 01, 2003 157 158 159 160 161 162 163 -- | 'foldl', applied to a binary operator, a starting value (typically -- the left-identity of the operator), and a list, reduces the list -- using the binary operator, from left to right: -- -- > foldl f z [x1, x2, ..., xn] == (...((z f x1) f x2) f...) f xn -- -- The list must be finite.  simonmar committed Jun 28, 2001 164 165 166 167 168  -- We write foldl as a non-recursive thing, so that it -- can be inlined, and then (often) strictness-analysed, -- and hence the classic space leak on foldl (+) 0 xs  169 foldl :: (b -> a -> b) -> b -> [a] -> b  Ian Lynagh committed Aug 05, 2008 170 foldl f z0 xs0 = lgo z0 xs0  Don Stewart committed Mar 05, 2008 171 172 173  where lgo z [] = z lgo z (x:xs) = lgo (f z x) xs  simonmar committed Jun 28, 2001 174   ross committed Sep 01, 2003 175 176 177 178 179 180 181 182 183 -- | 'scanl' is similar to 'foldl', but returns a list of successive -- reduced values from the left: -- -- > scanl f z [x1, x2, ...] == [z, z f x1, (z f x1) f x2, ...] -- -- Note that -- -- > last (scanl f z xs) == foldl f z xs.  184 scanl :: (b -> a -> b) -> b -> [a] -> [b]  simonmar committed Jun 28, 2001 185 186 187 188 scanl f q ls = q : (case ls of [] -> [] x:xs -> scanl f (f q x) xs)  ross committed Sep 01, 2003 189 190 191 192 -- | 'scanl1' is a variant of 'scanl' that has no starting value argument: -- -- > scanl1 f [x1, x2, ...] == [x1, x1 f x2, ...]  Don Stewart committed Mar 05, 2008 193 194 195 scanl1 :: (a -> a -> a) -> [a] -> [a] scanl1 f (x:xs) = scanl f x xs scanl1 _ [] = []  simonmar committed Jun 28, 2001 196 197 198 199  -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the -- above functions.  ross committed Sep 01, 2003 200 201 202 -- | 'foldr1' is a variant of 'foldr' that has no starting value argument, -- and thus must be applied to non-empty lists.  simonmar committed Jun 28, 2001 203 204 205 206 207 foldr1 :: (a -> a -> a) -> [a] -> a foldr1 _ [x] = x foldr1 f (x:xs) = f x (foldr1 f xs) foldr1 _ [] = errorEmptyList "foldr1"  ross committed Sep 01, 2003 208 209 210 211 212 -- | 'scanr' is the right-to-left dual of 'scanl'. -- Note that -- -- > head (scanr f z xs) == foldr f z xs.  simonmar committed Jun 28, 2001 213 214 215 216 217 scanr :: (a -> b -> b) -> b -> [a] -> [b] scanr _ q0 [] = [q0] scanr f q0 (x:xs) = f x q : qs where qs@(q:_) = scanr f q0 xs  ross committed Sep 01, 2003 218 219 -- | 'scanr1' is a variant of 'scanr' that has no starting value argument.  simonmar committed Jun 28, 2001 220 scanr1 :: (a -> a -> a) -> [a] -> [a]  Ian Lynagh committed Aug 05, 2008 221 222 scanr1 _ [] = [] scanr1 _ [x] = [x]  Don Stewart committed Mar 05, 2008 223 scanr1 f (x:xs) = f x q : qs  simonmar committed Jun 28, 2001 224 225  where qs@(q:_) = scanr1 f xs  ross committed Sep 01, 2003 226 227 228 229 230 -- | 'iterate' @f x@ returns an infinite list of repeated applications -- of @f@ to @x@: -- -- > iterate f x == [x, f x, f (f x), ...]  pcapriotti committed Jul 25, 2012 231 {-# NOINLINE [1] iterate #-}  simonmar committed Jun 28, 2001 232 iterate :: (a -> a) -> a -> [a]  simonmar committed Feb 05, 2002 233 iterate f x = x : iterate f (f x)  simonmar committed Jun 28, 2001 234   pcapriotti committed Jul 25, 2012 235 {-# NOINLINE [0] iterateFB #-}  Ian Lynagh committed Aug 05, 2008 236 iterateFB :: (a -> b -> b) -> (a -> a) -> a -> b  simonmar committed Jun 28, 2001 237 238 239 iterateFB c f x = x c iterateFB c f (f x) {-# RULES  Don Stewart committed Mar 05, 2008 240 241 "iterate" [~1] forall f x. iterate f x = build (\c _n -> iterateFB c f x) "iterateFB" [1] iterateFB (:) = iterate  simonmar committed Jun 28, 2001 242 243 244  #-}  ross committed Sep 01, 2003 245 -- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.  simonmar committed Jun 28, 2001 246 repeat :: a -> [a]  simonmar committed Feb 05, 2002 247 248 249 {-# INLINE [0] repeat #-} -- The pragma just gives the rules more chance to fire repeat x = xs where xs = x : xs  simonmar committed Jun 28, 2001 250   Don Stewart committed Mar 05, 2008 251 {-# INLINE [0] repeatFB #-} -- ditto  Ian Lynagh committed Aug 05, 2008 252 repeatFB :: (a -> b -> b) -> a -> b  simonmar committed Jun 28, 2001 253 repeatFB c x = xs where xs = x c xs  simonmar committed Dec 21, 2001 254   simonmar committed Jun 28, 2001 255 256  {-# RULES  simonmar committed Feb 05, 2002 257 "repeat" [~1] forall x. repeat x = build (\c _n -> repeatFB c x)  Don Stewart committed Mar 05, 2008 258 "repeatFB" [1] repeatFB (:) = repeat  simonmar committed Jun 28, 2001 259 260  #-}  ross committed Sep 01, 2003 261 262 263 264 -- | 'replicate' @n x@ is a list of length @n@ with @x@ the value of -- every element. -- It is an instance of the more general 'Data.List.genericReplicate', -- in which @n@ may be of any integral type.  Simon Marlow committed Jan 26, 2006 265 {-# INLINE replicate #-}  simonmar committed Jun 28, 2001 266 267 268 replicate :: Int -> a -> [a] replicate n x = take n (repeat x)  ross committed Sep 01, 2003 269 -- | 'cycle' ties a finite list into a circular one, or equivalently,  simonmar committed Jun 28, 2001 270 271 272 273 -- the infinite repetition of the original list. It is the identity -- on infinite lists. cycle :: [a] -> [a]  Don Stewart committed Mar 05, 2008 274 275 cycle [] = error "Prelude.cycle: empty list" cycle xs = xs' where xs' = xs ++ xs'  simonmar committed Jun 28, 2001 276   ross committed Sep 01, 2003 277 -- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the  278 279 280 281 282 283 -- longest prefix (possibly empty) of @xs@ of elements that satisfy @p@: -- -- > takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2] -- > takeWhile (< 9) [1,2,3] == [1,2,3] -- > takeWhile (< 0) [1,2,3] == [] --  simonmar committed Jun 28, 2001 284 285 286 287 288 289 290  takeWhile :: (a -> Bool) -> [a] -> [a] takeWhile _ [] = [] takeWhile p (x:xs) | p x = x : takeWhile p xs | otherwise = []  291 292 293 294 295 296 -- | 'dropWhile' @p xs@ returns the suffix remaining after 'takeWhile' @p xs@: -- -- > dropWhile (< 3) [1,2,3,4,5,1,2,3] == [3,4,5,1,2,3] -- > dropWhile (< 9) [1,2,3] == [] -- > dropWhile (< 0) [1,2,3] == [1,2,3] --  ross committed Sep 01, 2003 297   simonmar committed Jun 28, 2001 298 299 300 301 302 303 dropWhile :: (a -> Bool) -> [a] -> [a] dropWhile _ [] = [] dropWhile p xs@(x:xs') | p x = dropWhile p xs' | otherwise = xs  ross committed Sep 01, 2003 304 -- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@  305 306 307 308 309 310 311 312 313 -- of length @n@, or @xs@ itself if @n > 'length' xs@: -- -- > take 5 "Hello World!" == "Hello" -- > take 3 [1,2,3,4,5] == [1,2,3] -- > take 3 [1,2] == [1,2] -- > take 3 [] == [] -- > take (-1) [1,2] == [] -- > take 0 [1,2] == [] --  ross committed Sep 01, 2003 314 315 -- It is an instance of the more general 'Data.List.genericTake', -- in which @n@ may be of any integral type.  simonmar committed Jun 28, 2001 316 take :: Int -> [a] -> [a]  ross committed Sep 01, 2003 317 318  -- | 'drop' @n xs@ returns the suffix of @xs@  319 320 321 322 323 324 325 326 327 -- after the first @n@ elements, or @[]@ if @n > 'length' xs@: -- -- > drop 6 "Hello World!" == "World!" -- > drop 3 [1,2,3,4,5] == [4,5] -- > drop 3 [1,2] == [] -- > drop 3 [] == [] -- > drop (-1) [1,2] == [1,2] -- > drop 0 [1,2] == [1,2] --  ross committed Sep 01, 2003 328 329 330 331 -- It is an instance of the more general 'Data.List.genericDrop', -- in which @n@ may be of any integral type. drop :: Int -> [a] -> [a]  332 333 334 335 336 337 338 339 340 341 342 -- | 'splitAt' @n xs@ returns a tuple where first element is @xs@ prefix of -- length @n@ and second element is the remainder of the list: -- -- > splitAt 6 "Hello World!" == ("Hello ","World!") -- > splitAt 3 [1,2,3,4,5] == ([1,2,3],[4,5]) -- > splitAt 1 [1,2,3] == ([1],[2,3]) -- > splitAt 3 [1,2,3] == ([1,2,3],[]) -- > splitAt 4 [1,2,3] == ([1,2,3],[]) -- > splitAt 0 [1,2,3] == ([],[1,2,3]) -- > splitAt (-1) [1,2,3] == ([],[1,2,3]) --  Michal Terepeta committed Jun 26, 2011 343 344 -- It is equivalent to @('take' n xs, 'drop' n xs)@ when @n@ is not @_|_@ -- (@splitAt _|_ xs = _|_@).  345 -- 'splitAt' is an instance of the more general 'Data.List.genericSplitAt',  ross committed Sep 01, 2003 346 347 348 349 -- in which @n@ may be of any integral type. splitAt :: Int -> [a] -> ([a],[a]) #ifdef USE_REPORT_PRELUDE  simonmar committed Jul 31, 2001 350 take n _ | n <= 0 = []  simonmar committed Jun 28, 2001 351 take _ [] = []  simonmar committed Jul 31, 2001 352 take n (x:xs) = x : take (n-1) xs  simonmar committed Jun 28, 2001 353   simonmar committed Jul 31, 2001 354 drop n xs | n <= 0 = xs  simonmar committed Jun 28, 2001 355 drop _ [] = []  simonmar committed Jul 31, 2001 356 drop n (_:xs) = drop (n-1) xs  simonmar committed Jun 28, 2001 357   ross committed Sep 01, 2003 358 splitAt n xs = (take n xs, drop n xs)  simonmar committed Jun 28, 2001 359 360  #else /* hack away */  Simon Marlow committed Jan 26, 2006 361 {-# RULES  Don Stewart committed Mar 05, 2008 362 "take" [~1] forall n xs . take n xs = takeFoldr n xs  Simon Marlow committed Jan 26, 2006 363 364 365 "takeList" [1] forall n xs . foldr (takeFB (:) []) (takeConst []) xs n = takeUInt n xs #-}  Simon Marlow committed Mar 27, 2007 366 367 368 369 370 371 {-# INLINE takeFoldr #-} takeFoldr :: Int -> [a] -> [a] takeFoldr (I# n#) xs = build (\c nil -> if n# <=# 0# then nil else foldr (takeFB c nil) (takeConst nil) xs n#)  Simon Marlow committed Jan 26, 2006 372 373 374 375 376 377 378 {-# NOINLINE [0] takeConst #-} -- just a version of const that doesn't get inlined too early, so we -- can spot it in rules. Also we need a type sig due to the unboxed Int#. takeConst :: a -> Int# -> a takeConst x _ = x {-# NOINLINE [0] takeFB #-}  Simon Marlow committed Mar 27, 2007 379 380 takeFB :: (a -> b -> b) -> b -> a -> (Int# -> b) -> Int# -> b takeFB c n x xs m | m <=# 1# = x c n  Don Stewart committed Mar 05, 2008 381  | otherwise = x c xs (m -# 1#)  Simon Marlow committed Jan 26, 2006 382 383  {-# INLINE [0] take #-}  simonmar committed Jun 28, 2001 384 385 386 387 388 389 390 391 392 take (I# n#) xs = takeUInt n# xs -- The general code for take, below, checks n <= maxInt -- No need to check for maxInt overflow when specialised -- at type Int or Int# since the Int must be <= maxInt takeUInt :: Int# -> [b] -> [b] takeUInt n xs | n >=# 0# = take_unsafe_UInt n xs  simonmar committed Jul 31, 2001 393  | otherwise = []  simonmar committed Jun 28, 2001 394 395 396 397 398 399 400 401 402 403 404  take_unsafe_UInt :: Int# -> [b] -> [b] take_unsafe_UInt 0# _ = [] take_unsafe_UInt m ls = case ls of [] -> [] (x:xs) -> x : take_unsafe_UInt (m -# 1#) xs takeUInt_append :: Int# -> [b] -> [b] -> [b] takeUInt_append n xs rs | n >=# 0# = take_unsafe_UInt_append n xs rs  simonmar committed Jul 31, 2001 405  | otherwise = []  simonmar committed Jun 28, 2001 406   Don Stewart committed Mar 05, 2008 407 408 409 take_unsafe_UInt_append :: Int# -> [b] -> [b] -> [b] take_unsafe_UInt_append 0# _ rs = rs take_unsafe_UInt_append m ls rs =  simonmar committed Jun 28, 2001 410 411 412 413 414  case ls of [] -> rs (x:xs) -> x : take_unsafe_UInt_append (m -# 1#) xs rs drop (I# n#) ls  Don Stewart committed Mar 05, 2008 415 416  | n# <# 0# = ls | otherwise = drop# n# ls  simonmar committed Jun 28, 2001 417  where  Don Stewart committed Mar 05, 2008 418 419 420 421  drop# :: Int# -> [a] -> [a] drop# 0# xs = xs drop# _ xs@[] = xs drop# m# (_:xs) = drop# (m# -# 1#) xs  simonmar committed Jun 28, 2001 422 423  splitAt (I# n#) ls  Don Stewart committed Mar 05, 2008 424 425  | n# <# 0# = ([], ls) | otherwise = splitAt# n# ls  simonmar committed Jun 28, 2001 426  where  Don Stewart committed Mar 05, 2008 427 428 429 430 431 432  splitAt# :: Int# -> [a] -> ([a], [a]) splitAt# 0# xs = ([], xs) splitAt# _ xs@[] = (xs, xs) splitAt# m# (x:xs) = (x:xs', xs'') where (xs', xs'') = splitAt# (m# -# 1#) xs  simonmar committed Jun 28, 2001 433 434 435  #endif /* USE_REPORT_PRELUDE */  436 437 438 439 440 441 442 443 444 -- | 'span', applied to a predicate @p@ and a list @xs@, returns a tuple where -- first element is longest prefix (possibly empty) of @xs@ of elements that -- satisfy @p@ and second element is the remainder of the list: -- -- > span (< 3) [1,2,3,4,1,2,3,4] == ([1,2],[3,4,1,2,3,4]) -- > span (< 9) [1,2,3] == ([1,2,3],[]) -- > span (< 0) [1,2,3] == ([],[1,2,3]) -- -- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@  ross committed Sep 01, 2003 445 446  span :: (a -> Bool) -> [a] -> ([a],[a])  simonmar committed Jun 28, 2001 447 448 449 450 451 span _ xs@[] = (xs, xs) span p xs@(x:xs') | p x = let (ys,zs) = span p xs' in (x:ys,zs) | otherwise = ([],xs)  452 453 454 455 456 457 458 459 460 -- | 'break', applied to a predicate @p@ and a list @xs@, returns a tuple where -- first element is longest prefix (possibly empty) of @xs@ of elements that -- /do not satisfy/ @p@ and second element is the remainder of the list: -- -- > break (> 3) [1,2,3,4,1,2,3,4] == ([1,2,3],[4,1,2,3,4]) -- > break (< 9) [1,2,3] == ([],[1,2,3]) -- > break (> 9) [1,2,3] == ([1,2,3],[]) -- -- 'break' @p@ is equivalent to @'span' ('not' . p)@.  ross committed Sep 01, 2003 461 462  break :: (a -> Bool) -> [a] -> ([a],[a])  simonmar committed Jun 28, 2001 463 464 465 466 #ifdef USE_REPORT_PRELUDE break p = span (not . p) #else -- HBC version (stolen)  Don Stewart committed Mar 05, 2008 467 break _ xs@[] = (xs, xs)  simonmar committed Jun 28, 2001 468 break p xs@(x:xs')  Don Stewart committed Mar 05, 2008 469 470  | p x = ([],xs) | otherwise = let (ys,zs) = break p xs' in (x:ys,zs)  simonmar committed Jun 28, 2001 471 472 #endif  ross committed Sep 01, 2003 473 474 -- | 'reverse' @xs@ returns the elements of @xs@ in reverse order. -- @xs@ must be finite.  simonmar committed Jun 28, 2001 475 476 477 478 479 480 481 482 483 484 reverse :: [a] -> [a] #ifdef USE_REPORT_PRELUDE reverse = foldl (flip (:)) [] #else reverse l = rev l [] where rev [] a = a rev (x:xs) a = rev xs (x:a) #endif  ross committed Sep 01, 2003 485 486 487 488 489 490 491 492 493 -- | 'and' returns the conjunction of a Boolean list. For the result to be -- 'True', the list must be finite; 'False', however, results from a 'False' -- value at a finite index of a finite or infinite list. and :: [Bool] -> Bool -- | 'or' returns the disjunction of a Boolean list. For the result to be -- 'False', the list must be finite; 'True', however, results from a 'True' -- value at a finite index of a finite or infinite list. or :: [Bool] -> Bool  simonmar committed Jun 28, 2001 494 495 496 497 #ifdef USE_REPORT_PRELUDE and = foldr (&&) True or = foldr (||) False #else  Don Stewart committed Mar 05, 2008 498 499 500 501 and [] = True and (x:xs) = x && and xs or [] = False or (x:xs) = x || or xs  simonmar committed Jun 28, 2001 502   pcapriotti committed Jul 25, 2012 503 504 505 {-# NOINLINE [1] and #-} {-# NOINLINE [1] or #-}  simonmar committed Jun 28, 2001 506 {-# RULES  Don Stewart committed Mar 05, 2008 507 508 509 510 "and/build" forall (g::forall b.(Bool->b->b)->b->b) . and (build g) = g (&&) True "or/build" forall (g::forall b.(Bool->b->b)->b->b) . or (build g) = g (||) False  simonmar committed Jun 28, 2001 511 512 513  #-} #endif  ross committed Sep 01, 2003 514 -- | Applied to a predicate and a list, 'any' determines if any element  Simon Marlow committed Jul 14, 2010 515 516 517 -- of the list satisfies the predicate. For the result to be -- 'False', the list must be finite; 'True', however, results from a 'True' -- value for the predicate applied to an element at a finite index of a finite or infinite list.  ross committed Sep 01, 2003 518 519 520 any :: (a -> Bool) -> [a] -> Bool -- | Applied to a predicate and a list, 'all' determines if all elements  Simon Marlow committed Jul 14, 2010 521 522 523 -- of the list satisfy the predicate. For the result to be -- 'True', the list must be finite; 'False', however, results from a 'False' -- value for the predicate applied to an element at a finite index of a finite or infinite list.  ross committed Sep 01, 2003 524 all :: (a -> Bool) -> [a] -> Bool  simonmar committed Jun 28, 2001 525 526 527 528 #ifdef USE_REPORT_PRELUDE any p = or . map p all p = and . map p #else  Don Stewart committed Mar 05, 2008 529 530 any _ [] = False any p (x:xs) = p x || any p xs  simonmar committed Jun 28, 2001 531   Don Stewart committed Mar 05, 2008 532 533 all _ [] = True all p (x:xs) = p x && all p xs  pcapriotti committed Jul 25, 2012 534 535 536 537  {-# NOINLINE [1] any #-} {-# NOINLINE [1] all #-}  simonmar committed Jun 28, 2001 538 {-# RULES  Don Stewart committed Mar 05, 2008 539 540 541 542 "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  simonmar committed Jun 28, 2001 543 544 545  #-} #endif  ross committed Sep 01, 2003 546 -- | 'elem' is the list membership predicate, usually written in infix form,  Simon Marlow committed Jul 14, 2010 547 548 -- e.g., @x \elem\ xs@. 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.  ross committed Sep 01, 2003 549 550 551 552 elem :: (Eq a) => a -> [a] -> Bool -- | 'notElem' is the negation of 'elem'. notElem :: (Eq a) => a -> [a] -> Bool  simonmar committed Jun 28, 2001 553 554 555 556 #ifdef USE_REPORT_PRELUDE elem x = any (== x) notElem x = all (/= x) #else  Don Stewart committed Mar 05, 2008 557 558 elem _ [] = False elem x (y:ys) = x==y || elem x ys  simonmar committed Jun 28, 2001 559   Don Stewart committed Mar 05, 2008 560 notElem _ [] = True  simonmar committed Jun 28, 2001 561 562 563 notElem x (y:ys)= x /= y && notElem x ys #endif  ross committed Sep 01, 2003 564 -- | 'lookup' @key assocs@ looks up a key in an association list.  simonmar committed Jun 28, 2001 565 566 567 568 569 570 lookup :: (Eq a) => a -> [(a,b)] -> Maybe b lookup _key [] = Nothing lookup key ((x,y):xys) | key == x = Just y | otherwise = lookup key xys  ross committed Sep 01, 2003 571 -- | Map a function over a list and concatenate the results.  simonmar committed Jun 28, 2001 572 573 574 concatMap :: (a -> [b]) -> [a] -> [b] concatMap f = foldr ((++) . f) []  ross committed Sep 01, 2003 575 -- | Concatenate a list of lists.  simonmar committed Jun 28, 2001 576 577 578 concat :: [[a]] -> [a] concat = foldr (++) []  pcapriotti committed Jul 25, 2012 579 580 {-# NOINLINE [1] concat #-}  simonmar committed Jun 28, 2001 581 582 {-# RULES "concat" forall xs. concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)  simonmar committed Feb 05, 2002 583 -- We don't bother to turn non-fusible applications of concat back into concat  simonmar committed Jun 28, 2001 584  #-}  simonmar committed Feb 05, 2002 585   simonmar committed Jun 28, 2001 586 587 588 589 \end{code} \begin{code}  ross committed Sep 01, 2003 590 591 592 -- | List index (subscript) operator, starting from 0. -- It is an instance of the more general 'Data.List.genericIndex', -- which takes an index of any integral type.  simonmar committed Jun 28, 2001 593 594 (!!) :: [a] -> Int -> a #ifdef USE_REPORT_PRELUDE  simonmar committed Dec 21, 2001 595 596 597 598 xs !! n | n < 0 = error "Prelude.!!: negative index" [] !! _ = error "Prelude.!!: index too large" (x:_) !! 0 = x (_:xs) !! n = xs !! (n-1)  simonmar committed Jun 28, 2001 599 600 601 602 603 #else -- HBC version (stolen), then unboxified -- The semantics is not quite the same for error conditions -- in the more efficient version. --  Ian Lynagh committed Aug 05, 2008 604 605 xs !! (I# n0) | n0 <# 0# = error "Prelude.(!!): negative index\n" | otherwise = sub xs n0  simonmar committed Jun 28, 2001 606  where  Don Stewart committed Mar 05, 2008 607  sub :: [a] -> Int# -> a  simonmar committed Jun 28, 2001 608 609  sub [] _ = error "Prelude.(!!): index too large\n" sub (y:ys) n = if n ==# 0#  Don Stewart committed Mar 05, 2008 610 611  then y else sub ys (n -# 1#)  simonmar committed Jun 28, 2001 612 613 614 615 616 #endif \end{code} %*********************************************************  Don Stewart committed Mar 05, 2008 617 %* *  simonmar committed Jun 28, 2001 618 \subsection{The zip family}  Don Stewart committed Mar 05, 2008 619 %* *  simonmar committed Jun 28, 2001 620 621 622 %********************************************************* \begin{code}  Ian Lynagh committed Aug 05, 2008 623 foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c  Don Stewart committed Mar 05, 2008 624 625 foldr2 _k z [] _ys = z foldr2 _k z _xs [] = z  simonmar committed Jun 28, 2001 626 627 foldr2 k z (x:xs) (y:ys) = k x y (foldr2 k z xs ys)  pcapriotti committed Jul 25, 2012 628 629 {-# NOINLINE [1] foldr2 #-}  Ian Lynagh committed Aug 05, 2008 630 foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d  simonmar committed Jun 28, 2001 631 632 633 foldr2_left _k z _x _r [] = z foldr2_left k _z x r (y:ys) = k x y (r ys)  Ian Lynagh committed Aug 05, 2008 634 foldr2_right :: (a -> b -> c -> d) -> d -> b -> ([a] -> c) -> [a] -> d  simonmar committed Jun 28, 2001 635 636 637 638 639 640 foldr2_right _k z _y _r [] = z foldr2_right k _z y r (x:xs) = k x y (r xs) -- foldr2 k z xs ys = foldr (foldr2_left k z) (\_ -> z) xs ys -- foldr2 k z xs ys = foldr (foldr2_right k z) (\_ -> z) ys xs {-# RULES  Don Stewart committed Mar 05, 2008 641 642 "foldr2/left" forall k z ys (g::forall b.(a->b->b)->b->b) . foldr2 k z (build g) ys = g (foldr2_left k z) (\_ -> z) ys  simonmar committed Jun 28, 2001 643   Don Stewart committed Mar 05, 2008 644 645 "foldr2/right" forall k z xs (g::forall b.(a->b->b)->b->b) . foldr2 k z xs (build g) = g (foldr2_right k z) (\_ -> z) xs  simonmar committed Jun 28, 2001 646 647 648 649 650 651 652 653 654 655 656 657 658  #-} \end{code} The foldr2/right rule isn't exactly right, because it changes the strictness of foldr2 (and thereby zip) E.g. main = print (null (zip nonobviousNil (build undefined))) where nonobviousNil = f 3 f n = if n == 0 then [] else f (n-1) I'm going to leave it though.  ross committed Sep 01, 2003 659 Zips for larger tuples are in the List module.  simonmar committed Jun 28, 2001 660 661 662  \begin{code} ----------------------------------------------  ross committed Sep 01, 2003 663 664 665 -- | 'zip' takes two lists and returns a list of corresponding pairs. -- If one input list is short, excess elements of the longer list are -- discarded.  pcapriotti committed Jul 25, 2012 666 {-# NOINLINE [1] zip #-}  simonmar committed Jun 28, 2001 667 zip :: [a] -> [b] -> [(a,b)]  simonmar committed Feb 05, 2002 668 669 zip (a:as) (b:bs) = (a,b) : zip as bs zip _ _ = []  simonmar committed Jun 28, 2001 670   simonmar committed Dec 21, 2001 671 {-# INLINE [0] zipFB #-}  Ian Lynagh committed Aug 05, 2008 672 zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d  rl@cse.unsw.edu.au committed Nov 26, 2009 673 zipFB c = \x y r -> (x,y) c r  simonmar committed Jun 28, 2001 674 675  {-# RULES  Don Stewart committed Mar 05, 2008 676 677 "zip" [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys) "zipList" [1] foldr2 (zipFB (:)) [] = zip  simonmar committed Jun 28, 2001 678 679 680 681 682  #-} \end{code} \begin{code} ----------------------------------------------  ross committed Sep 01, 2003 683 684 -- | 'zip3' takes three lists and returns a list of triples, analogous to -- 'zip'.  simonmar committed Jun 28, 2001 685 686 687 688 689 690 691 692 693 694 695 696 697 zip3 :: [a] -> [b] -> [c] -> [(a,b,c)] -- Specification -- zip3 = zipWith3 (,,) zip3 (a:as) (b:bs) (c:cs) = (a,b,c) : zip3 as bs cs zip3 _ _ _ = [] \end{code} -- The zipWith family generalises the zip family by zipping with the -- function given as the first argument, instead of a tupling function. \begin{code} ----------------------------------------------  ross committed Sep 01, 2003 698 699 700 701 -- | 'zipWith' generalises 'zip' by zipping with the function given -- as the first argument, instead of a tupling function. -- For example, @'zipWith' (+)@ is applied to two lists to produce the -- list of corresponding sums.  pcapriotti committed Jul 25, 2012 702 {-# NOINLINE [1] zipWith #-}  simonmar committed Jun 28, 2001 703 zipWith :: (a->b->c) -> [a]->[b]->[c]  simonmar committed Feb 05, 2002 704 705 zipWith f (a:as) (b:bs) = f a b : zipWith f as bs zipWith _ _ _ = []  simonmar committed Jun 28, 2001 706   rl@cse.unsw.edu.au committed Nov 25, 2009 707 708 -- zipWithFB must have arity 2 since it gets two arguments in the "zipWith" -- rule; it might not get inlined otherwise  simonmar committed Dec 21, 2001 709 {-# INLINE [0] zipWithFB #-}  Ian Lynagh committed Aug 05, 2008 710 zipWithFB :: (a -> b -> c) -> (d -> e -> a) -> d -> e -> b -> c  rl@cse.unsw.edu.au committed Nov 25, 2009 711 zipWithFB c f = \x y r -> (x f y) c r  simonmar committed Jun 28, 2001 712 713  {-# RULES  Don Stewart committed Mar 05, 2008 714 715 "zipWith" [~1] forall f xs ys. zipWith f xs ys = build (\c n -> foldr2 (zipWithFB c f) n xs ys) "zipWithList" [1] forall f. foldr2 (zipWithFB (:) f) [] = zipWith f  simonmar committed Jun 28, 2001 716 717 718 719  #-} \end{code} \begin{code}  ross committed Sep 01, 2003 720 721 722 -- | The 'zipWith3' function takes a function which combines three -- elements, as well as three lists and returns a list of their point-wise -- combination, analogous to 'zipWith'.  simonmar committed Jun 28, 2001 723 724 725 726 727 zipWith3 :: (a->b->c->d) -> [a]->[b]->[c]->[d] zipWith3 z (a:as) (b:bs) (c:cs) = z a b c : zipWith3 z as bs cs zipWith3 _ _ _ _ = []  ross committed Sep 01, 2003 728 729 -- | 'unzip' transforms a list of pairs into a list of first components -- and a list of second components.  simonmar committed Jun 28, 2001 730 731 732 733 unzip :: [(a,b)] -> ([a],[b]) {-# INLINE unzip #-} unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])  ross committed Sep 01, 2003 734 735 -- | The 'unzip3' function takes a list of triples and returns three -- lists, analogous to 'unzip'.  simonmar committed Jun 28, 2001 736 737 738 739 740 741 742 743 unzip3 :: [(a,b,c)] -> ([a],[b],[c]) {-# INLINE unzip3 #-} unzip3 = foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs)) ([],[],[]) \end{code} %*********************************************************  Don Stewart committed Mar 05, 2008 744 %* *  simonmar committed Jun 28, 2001 745 \subsection{Error code}  Don Stewart committed Mar 05, 2008 746 %* *  simonmar committed Jun 28, 2001 747 748 749 750 751 752 753 754 755 756 757 758 759 %********************************************************* Common up near identical calls to error' to reduce the number constant strings created when compiled: \begin{code} errorEmptyList :: String -> a errorEmptyList fun = error (prel_list_str ++ fun ++ ": empty list") prel_list_str :: String prel_list_str = "Prelude." \end{code}`