List.lhs 27.1 KB
 simonmar committed Jun 28, 2001 1 \begin{code} dterei committed Jun 18, 2011 2 {-# LANGUAGE Trustworthy #-} Joachim Breitner committed Feb 10, 2014 3 {-# LANGUAGE CPP, NoImplicitPrelude, ScopedTypeVariables, MagicHash #-} Ross Paterson committed Jan 20, 2008 4 {-# OPTIONS_HADDOCK hide #-} 5 simonmar committed Apr 26, 2002 6 7 8 9 10 ----------------------------------------------------------------------------- -- | -- Module : GHC.List -- Copyright : (c) The University of Glasgow 1994-2002 -- License : see libraries/base/LICENSE Jan Stolarek committed Sep 18, 2013 11 -- simonmar committed Apr 26, 2002 12 13 14 15 16 17 18 -- 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 20 module GHC.List ( ian@well-typed.com committed Nov 17, 2012 21 -- [] (..), -- built-in syntax; can't be used in export list simonmar committed Jun 28, 2001 22 23 map, (++), filter, concat, David Feuer committed Sep 04, 2014 24 head, last, tail, init, uncons, null, length, (!!), simonmar committed Sep 28, 2004 25 foldl, scanl, scanl1, foldr, foldr1, scanr, scanr1, simonmar committed Jun 28, 2001 26 27 28 29 iterate, repeat, replicate, cycle, take, drop, splitAt, takeWhile, dropWhile, span, break, reverse, and, or, any, all, elem, notElem, lookup, simonmar committed Sep 28, 2004 30 concatMap, simonmar committed Jun 28, 2001 31 zip, zip3, zipWith, zipWith3, unzip, unzip3, simonmar committed Sep 28, 2004 32 errorEmptyList, simonmar committed Jun 28, 2001 33 simonmar committed Sep 28, 2004 34 #ifndef USE_REPORT_PRELUDE simonmar committed Jun 28, 2001 35 36 37 38 39 40 41 -- non-standard, but hidden when creating the Prelude -- export list. takeUInt_append #endif ) where simonmar committed Jul 03, 2001 42 import Data.Maybe simonmar committed Jun 28, 2001 43 44 45 46 47 48 49 import GHC.Base infixl 9 !! infix 4 elem, notElem \end{code} %********************************************************* Don Stewart committed Mar 05, 2008 50 %* * simonmar committed Jun 28, 2001 51 \subsection{List-manipulation functions} Don Stewart committed Mar 05, 2008 52 %* * simonmar committed Jun 28, 2001 53 54 55 %********************************************************* \begin{code} ross committed Sep 01, 2003 56 -- | Extract the first element of a list, which must be non-empty. simonmar committed Jun 28, 2001 57 58 59 head :: [a] -> a head (x:_) = x head [] = badHead pcapriotti committed Jul 25, 2012 60 {-# NOINLINE [1] head #-} simonmar committed Jun 28, 2001 61 Ian Lynagh committed Aug 05, 2008 62 badHead :: a simonmar committed Jun 28, 2001 63 64 badHead = errorEmptyList "head" Jan Stolarek committed Sep 18, 2013 65 -- This rule is useful in cases like Don Stewart committed Mar 05, 2008 66 -- head [y | (x,y) <- ps, x==t] simonmar committed Jun 28, 2001 67 {-# RULES Don Stewart committed Mar 05, 2008 68 69 "head/build" forall (g::forall b.(a->b->b)->b->b) . head (build g) = g (\x _ -> x) badHead Jan Stolarek committed Sep 18, 2013 70 "head/augment" forall xs (g::forall b. (a->b->b) -> b -> b) . Don Stewart committed Mar 05, 2008 71 head (augment g xs) = g (\x _ -> x) (head xs) simonmar committed Jun 28, 2001 72 73 #-} David Feuer committed Sep 04, 2014 74 75 76 -- | Decompose a list into its head and tail. If the list is empty, -- returns 'Nothing'. If the list is non-empty, returns @'Just' (x, xs)@, -- where @x@ is the head of the list and @xs@ its tail. Herbert Valerio Riedel committed Sep 04, 2014 77 78 -- -- /Since: 4.8.0.0/ David Feuer committed Sep 04, 2014 79 80 81 82 uncons :: [a] -> Maybe (a, [a]) uncons [] = Nothing uncons (x:xs) = Just (x, xs) ross committed Sep 01, 2003 83 -- | Extract the elements after the head of a list, which must be non-empty. simonmar committed Jun 28, 2001 84 85 86 87 tail :: [a] -> [a] tail (_:xs) = xs tail [] = errorEmptyList "tail" ross committed Sep 01, 2003 88 -- | Extract the last element of a list, which must be finite and non-empty. simonmar committed Jun 28, 2001 89 90 91 92 93 94 last :: [a] -> a #ifdef USE_REPORT_PRELUDE last [x] = x last (_:xs) = last xs last [] = errorEmptyList "last" #else Joachim Breitner committed Jul 22, 2014 95 96 -- use foldl to allow fusion last = foldl (\_ x -> x) (errorEmptyList "last") simonmar committed Jun 28, 2001 97 98 #endif ross committed Sep 01, 2003 99 -- | Return all the elements of a list except the last one. Ian Lynagh committed Sep 11, 2009 100 -- The list must be non-empty. simonmar committed Jun 28, 2001 101 102 103 104 105 106 107 108 109 110 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 111 init' y (z:zs) = y : init' z zs simonmar committed Jun 28, 2001 112 113 #endif ross committed Sep 01, 2003 114 -- | Test whether a list is empty. simonmar committed Jun 28, 2001 115 116 117 118 null :: [a] -> Bool null [] = True null (_:_) = False Ian Lynagh committed Feb 21, 2010 119 -- | /O(n)/. 'length' returns the length of a finite list as an 'Int'. ross committed Sep 01, 2003 120 121 -- It is an instance of the more general 'Data.List.genericLength', -- the result type of which may be any kind of number. Simon Peyton Jones committed Feb 14, 2013 122 {-# NOINLINE [1] length #-} simonpj@microsoft committed May 08, 2006 123 length :: [a] -> Int Simon Peyton Jones committed Feb 14, 2013 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 length l = lenAcc l 0# lenAcc :: [a] -> Int# -> Int lenAcc [] a# = I# a# lenAcc (_:xs) a# = lenAcc xs (a# +# 1#) incLen :: a -> (Int# -> Int) -> Int# -> Int incLen _ g x = g (x +# 1#) -- These rules make length into a good consumer -- Note that we use a higher-order-style use of foldr, so that -- the accumulating parameter can be evaluated strictly -- See Trac #876 for what goes wrong otherwise {-# RULES "length" [~1] forall xs. length xs = foldr incLen I# xs 0# "lengthList" [1] foldr incLen I# = lenAcc #-} simonmar committed Jun 28, 2001 141 ross committed Sep 01, 2003 142 143 144 145 146 -- | '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 147 {-# NOINLINE [1] filter #-} simonmar committed Jun 28, 2001 148 filter :: (a -> Bool) -> [a] -> [a] simonmar committed Feb 05, 2002 149 150 151 filter _pred [] = [] filter pred (x:xs) | pred x = x : filter pred xs Don Stewart committed Mar 05, 2008 152 | otherwise = filter pred xs simonmar committed Jun 28, 2001 153 simonmar committed Feb 05, 2002 154 {-# NOINLINE [0] filterFB #-} Ian Lynagh committed Aug 05, 2008 155 filterFB :: (a -> b -> b) -> (a -> Bool) -> a -> b -> b simonmar committed Jun 28, 2001 156 filterFB c p x r | p x = x c r Don Stewart committed Mar 05, 2008 157 | otherwise = r simonmar committed Jun 28, 2001 158 159 {-# RULES simonmar committed Feb 05, 2002 160 "filter" [~1] forall p xs. filter p xs = build (\c n -> foldr (filterFB c p) n xs) Don Stewart committed Mar 05, 2008 161 162 "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 163 164 165 166 167 168 169 170 171 172 173 174 #-} -- 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 175 176 177 178 179 180 181 -- | '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 182 183 184 185 186 -- 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 Joachim Breitner committed Feb 10, 2014 187 188 189 190 191 192 foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b {-# INLINE foldl #-} foldl k z0 xs = foldr (\(v::a) (fn::b->b) (z::b) -> fn (k z v)) (id :: b -> b) xs z0 -- Implementing foldl via foldr is only a good idea if the compiler can optimize -- the resulting code (eta-expand the recursive "go"), so this needs -fcall-arity! -- Also see #7994 simonmar committed Jun 28, 2001 193 ross committed Sep 01, 2003 194 195 196 197 198 199 200 201 202 -- | '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. 203 scanl :: (b -> a -> b) -> b -> [a] -> [b] simonmar committed Jun 28, 2001 204 205 206 207 scanl f q ls = q : (case ls of [] -> [] x:xs -> scanl f (f q x) xs) ross committed Sep 01, 2003 208 209 210 211 -- | '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 212 213 214 scanl1 :: (a -> a -> a) -> [a] -> [a] scanl1 f (x:xs) = scanl f x xs scanl1 _ [] = [] simonmar committed Jun 28, 2001 215 216 217 218 -- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the -- above functions. ross committed Sep 01, 2003 219 220 221 -- | '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 222 223 224 225 226 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 227 228 229 230 231 -- | 'scanr' is the right-to-left dual of 'scanl'. -- Note that -- -- > head (scanr f z xs) == foldr f z xs. David Feuer committed Oct 01, 2014 232 {-# NOINLINE [1] scanr #-} simonmar committed Jun 28, 2001 233 234 235 scanr :: (a -> b -> b) -> b -> [a] -> [b] scanr _ q0 [] = [q0] scanr f q0 (x:xs) = f x q : qs Jan Stolarek committed Sep 18, 2013 236 where qs@(q:_) = scanr f q0 xs simonmar committed Jun 28, 2001 237 David Feuer committed Oct 01, 2014 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 {-# INLINE [0] strictUncurryScanr #-} strictUncurryScanr :: (a -> b -> c) -> (a, b) -> c strictUncurryScanr f pair = case pair of (x, y) -> f x y {-# INLINE [0] scanrFB #-} scanrFB :: (a -> b -> b) -> (b -> c -> c) -> a -> (b, c) -> (b, c) scanrFB f c = \x (r, est) -> (f x r, r c est) {-# RULES "scanr" [~1] forall f q0 ls . scanr f q0 ls = build (\c n -> strictUncurryScanr c (foldr (scanrFB f c) (q0,n) ls)) "scanrList" [1] forall f q0 ls . strictUncurryScanr (:) (foldr (scanrFB f (:)) (q0,[]) ls) = scanr f q0 ls #-} ross committed Sep 01, 2003 255 256 -- | 'scanr1' is a variant of 'scanr' that has no starting value argument. simonmar committed Jun 28, 2001 257 scanr1 :: (a -> a -> a) -> [a] -> [a] Ian Lynagh committed Aug 05, 2008 258 259 scanr1 _ [] = [] scanr1 _ [x] = [x] Don Stewart committed Mar 05, 2008 260 scanr1 f (x:xs) = f x q : qs Jan Stolarek committed Sep 18, 2013 261 where qs@(q:_) = scanr1 f xs simonmar committed Jun 28, 2001 262 ross committed Sep 01, 2003 263 264 265 266 267 -- | '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 268 {-# NOINLINE [1] iterate #-} simonmar committed Jun 28, 2001 269 iterate :: (a -> a) -> a -> [a] simonmar committed Feb 05, 2002 270 iterate f x = x : iterate f (f x) simonmar committed Jun 28, 2001 271 pcapriotti committed Jul 25, 2012 272 {-# NOINLINE [0] iterateFB #-} Ian Lynagh committed Aug 05, 2008 273 iterateFB :: (a -> b -> b) -> (a -> a) -> a -> b simonmar committed Jun 28, 2001 274 275 276 iterateFB c f x = x c iterateFB c f (f x) {-# RULES Don Stewart committed Mar 05, 2008 277 278 "iterate" [~1] forall f x. iterate f x = build (\c _n -> iterateFB c f x) "iterateFB" [1] iterateFB (:) = iterate simonmar committed Jun 28, 2001 279 280 281 #-} ross committed Sep 01, 2003 282 -- | 'repeat' @x@ is an infinite list, with @x@ the value of every element. simonmar committed Jun 28, 2001 283 repeat :: a -> [a] simonmar committed Feb 05, 2002 284 285 286 {-# 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 287 Don Stewart committed Mar 05, 2008 288 {-# INLINE [0] repeatFB #-} -- ditto Ian Lynagh committed Aug 05, 2008 289 repeatFB :: (a -> b -> b) -> a -> b simonmar committed Jun 28, 2001 290 repeatFB c x = xs where xs = x c xs simonmar committed Dec 21, 2001 291 simonmar committed Jun 28, 2001 292 293 {-# RULES simonmar committed Feb 05, 2002 294 "repeat" [~1] forall x. repeat x = build (\c _n -> repeatFB c x) Don Stewart committed Mar 05, 2008 295 "repeatFB" [1] repeatFB (:) = repeat simonmar committed Jun 28, 2001 296 297 #-} ross committed Sep 01, 2003 298 299 300 301 -- | '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 302 {-# INLINE replicate #-} simonmar committed Jun 28, 2001 303 304 305 replicate :: Int -> a -> [a] replicate n x = take n (repeat x) ross committed Sep 01, 2003 306 -- | 'cycle' ties a finite list into a circular one, or equivalently, simonmar committed Jun 28, 2001 307 308 309 310 -- the infinite repetition of the original list. It is the identity -- on infinite lists. cycle :: [a] -> [a] Don Stewart committed Mar 05, 2008 311 312 cycle [] = error "Prelude.cycle: empty list" cycle xs = xs' where xs' = xs ++ xs' simonmar committed Jun 28, 2001 313 ross committed Sep 01, 2003 314 -- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the 315 316 317 318 319 320 -- 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 321 322 323 takeWhile :: (a -> Bool) -> [a] -> [a] takeWhile _ [] = [] Jan Stolarek committed Sep 18, 2013 324 takeWhile p (x:xs) simonmar committed Jun 28, 2001 325 326 327 | p x = x : takeWhile p xs | otherwise = [] 328 329 330 331 332 333 -- | '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 334 simonmar committed Jun 28, 2001 335 336 337 338 339 340 dropWhile :: (a -> Bool) -> [a] -> [a] dropWhile _ [] = [] dropWhile p xs@(x:xs') | p x = dropWhile p xs' | otherwise = xs ross committed Sep 01, 2003 341 -- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@ 342 343 344 345 346 347 348 349 350 -- 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 351 352 -- 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 353 take :: Int -> [a] -> [a] ross committed Sep 01, 2003 354 355 -- | 'drop' @n xs@ returns the suffix of @xs@ 356 357 358 359 360 361 362 363 364 -- 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 365 366 367 368 -- It is an instance of the more general 'Data.List.genericDrop', -- in which @n@ may be of any integral type. drop :: Int -> [a] -> [a] 369 370 371 372 373 374 375 376 377 378 379 -- | '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 380 381 -- It is equivalent to @('take' n xs, 'drop' n xs)@ when @n@ is not @_|_@ -- (@splitAt _|_ xs = _|_@). 382 -- 'splitAt' is an instance of the more general 'Data.List.genericSplitAt', ross committed Sep 01, 2003 383 384 385 386 -- in which @n@ may be of any integral type. splitAt :: Int -> [a] -> ([a],[a]) #ifdef USE_REPORT_PRELUDE simonmar committed Jul 31, 2001 387 take n _ | n <= 0 = [] simonmar committed Jun 28, 2001 388 take _ [] = [] simonmar committed Jul 31, 2001 389 take n (x:xs) = x : take (n-1) xs simonmar committed Jun 28, 2001 390 simonmar committed Jul 31, 2001 391 drop n xs | n <= 0 = xs simonmar committed Jun 28, 2001 392 drop _ [] = [] simonmar committed Jul 31, 2001 393 drop n (_:xs) = drop (n-1) xs simonmar committed Jun 28, 2001 394 ross committed Sep 01, 2003 395 splitAt n xs = (take n xs, drop n xs) simonmar committed Jun 28, 2001 396 397 #else /* hack away */ Simon Marlow committed Jan 26, 2006 398 {-# RULES Jan Stolarek committed Sep 18, 2013 399 "take" [~1] forall n xs . take n xs = takeFoldr n xs Simon Marlow committed Jan 26, 2006 400 401 402 "takeList" [1] forall n xs . foldr (takeFB (:) []) (takeConst []) xs n = takeUInt n xs #-} Simon Marlow committed Mar 27, 2007 403 404 405 {-# INLINE takeFoldr #-} takeFoldr :: Int -> [a] -> [a] takeFoldr (I# n#) xs Jan Stolarek committed Sep 18, 2013 406 = build (\c nil -> if isTrue# (n# <=# 0#) then nil else Simon Marlow committed Mar 27, 2007 407 408 foldr (takeFB c nil) (takeConst nil) xs n#) Simon Marlow committed Jan 26, 2006 409 410 411 412 413 414 {-# 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 Simon Peyton Jones committed Aug 28, 2014 415 {-# INLINE [0] takeFB #-} Simon Marlow committed Mar 27, 2007 416 takeFB :: (a -> b -> b) -> b -> a -> (Int# -> b) -> Int# -> b Simon Peyton Jones committed Aug 28, 2014 417 418 419 420 421 422 423 424 425 -- The \m accounts for the fact that takeFB is used in a higher-order -- way by takeFoldr, so it's better to inline. A good example is -- take n (repeat x) -- for which we get excellent code... but only if we inline takeFB -- when given four arguments takeFB c n x xs = \ m -> if isTrue# (m <=# 1#) then x c n else x c xs (m -# 1#) Simon Marlow committed Jan 26, 2006 426 427 {-# INLINE [0] take #-} simonmar committed Jun 28, 2001 428 429 430 431 432 433 434 435 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 Jan Stolarek committed Sep 18, 2013 436 437 | isTrue# (n >=# 0#) = take_unsafe_UInt n xs | otherwise = [] simonmar committed Jun 28, 2001 438 439 440 441 442 443 444 445 446 447 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 Jan Stolarek committed Sep 18, 2013 448 449 | isTrue# (n >=# 0#) = take_unsafe_UInt_append n xs rs | otherwise = [] simonmar committed Jun 28, 2001 450 Don Stewart committed Mar 05, 2008 451 452 453 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 454 455 456 457 458 case ls of [] -> rs (x:xs) -> x : take_unsafe_UInt_append (m -# 1#) xs rs drop (I# n#) ls Jan Stolarek committed Sep 18, 2013 459 460 | isTrue# (n# <# 0#) = ls | otherwise = drop# n# ls simonmar committed Jun 28, 2001 461 where Don Stewart committed Mar 05, 2008 462 463 464 465 drop# :: Int# -> [a] -> [a] drop# 0# xs = xs drop# _ xs@[] = xs drop# m# (_:xs) = drop# (m# -# 1#) xs simonmar committed Jun 28, 2001 466 467 splitAt (I# n#) ls Jan Stolarek committed Sep 18, 2013 468 469 | isTrue# (n# <# 0#) = ([], ls) | otherwise = splitAt# n# ls simonmar committed Jun 28, 2001 470 where Don Stewart committed Mar 05, 2008 471 472 473 474 475 476 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 477 478 479 #endif /* USE_REPORT_PRELUDE */ 480 481 482 -- | '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: Jan Stolarek committed Sep 18, 2013 483 -- 484 485 486 -- > 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]) Jan Stolarek committed Sep 18, 2013 487 -- 488 -- 'span' @p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@ ross committed Sep 01, 2003 489 490 span :: (a -> Bool) -> [a] -> ([a],[a]) simonmar committed Jun 28, 2001 491 492 493 494 495 span _ xs@[] = (xs, xs) span p xs@(x:xs') | p x = let (ys,zs) = span p xs' in (x:ys,zs) | otherwise = ([],xs) 496 497 498 -- | '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: Jan Stolarek committed Sep 18, 2013 499 -- 500 501 502 503 504 -- > 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 505 506 break :: (a -> Bool) -> [a] -> ([a],[a]) simonmar committed Jun 28, 2001 507 508 509 510 #ifdef USE_REPORT_PRELUDE break p = span (not . p) #else -- HBC version (stolen) Don Stewart committed Mar 05, 2008 511 break _ xs@[] = (xs, xs) simonmar committed Jun 28, 2001 512 break p xs@(x:xs') Don Stewart committed Mar 05, 2008 513 514 | p x = ([],xs) | otherwise = let (ys,zs) = break p xs' in (x:ys,zs) simonmar committed Jun 28, 2001 515 516 #endif ross committed Sep 01, 2003 517 518 -- | 'reverse' @xs@ returns the elements of @xs@ in reverse order. -- @xs@ must be finite. simonmar committed Jun 28, 2001 519 520 521 522 523 524 525 526 527 528 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 529 530 531 532 533 534 535 536 537 -- | '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 538 539 540 541 #ifdef USE_REPORT_PRELUDE and = foldr (&&) True or = foldr (||) False #else Don Stewart committed Mar 05, 2008 542 543 544 545 and [] = True and (x:xs) = x && and xs or [] = False or (x:xs) = x || or xs simonmar committed Jun 28, 2001 546 pcapriotti committed Jul 25, 2012 547 548 549 {-# NOINLINE [1] and #-} {-# NOINLINE [1] or #-} simonmar committed Jun 28, 2001 550 {-# RULES Jan Stolarek committed Sep 18, 2013 551 "and/build" forall (g::forall b.(Bool->b->b)->b->b) . Don Stewart committed Mar 05, 2008 552 and (build g) = g (&&) True Jan Stolarek committed Sep 18, 2013 553 "or/build" forall (g::forall b.(Bool->b->b)->b->b) . Don Stewart committed Mar 05, 2008 554 or (build g) = g (||) False simonmar committed Jun 28, 2001 555 556 557 #-} #endif ross committed Sep 01, 2003 558 -- | Applied to a predicate and a list, 'any' determines if any element Simon Marlow committed Jul 14, 2010 559 560 561 -- 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 562 563 564 any :: (a -> Bool) -> [a] -> Bool -- | Applied to a predicate and a list, 'all' determines if all elements Simon Marlow committed Jul 14, 2010 565 566 567 -- 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 568 all :: (a -> Bool) -> [a] -> Bool simonmar committed Jun 28, 2001 569 570 571 572 #ifdef USE_REPORT_PRELUDE any p = or . map p all p = and . map p #else Don Stewart committed Mar 05, 2008 573 574 any _ [] = False any p (x:xs) = p x || any p xs simonmar committed Jun 28, 2001 575 Don Stewart committed Mar 05, 2008 576 577 all _ [] = True all p (x:xs) = p x && all p xs pcapriotti committed Jul 25, 2012 578 579 580 581 {-# NOINLINE [1] any #-} {-# NOINLINE [1] all #-} simonmar committed Jun 28, 2001 582 {-# RULES Jan Stolarek committed Sep 18, 2013 583 "any/build" forall p (g::forall b.(a->b->b)->b->b) . Don Stewart committed Mar 05, 2008 584 any p (build g) = g ((||) . p) False Jan Stolarek committed Sep 18, 2013 585 "all/build" forall p (g::forall b.(a->b->b)->b->b) . Don Stewart committed Mar 05, 2008 586 all p (build g) = g ((&&) . p) True simonmar committed Jun 28, 2001 587 588 589 #-} #endif ross committed Sep 01, 2003 590 -- | 'elem' is the list membership predicate, usually written in infix form, Simon Marlow committed Jul 14, 2010 591 592 -- 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 593 594 595 596 elem :: (Eq a) => a -> [a] -> Bool -- | 'notElem' is the negation of 'elem'. notElem :: (Eq a) => a -> [a] -> Bool simonmar committed Jun 28, 2001 597 598 599 600 #ifdef USE_REPORT_PRELUDE elem x = any (== x) notElem x = all (/= x) #else Don Stewart committed Mar 05, 2008 601 602 elem _ [] = False elem x (y:ys) = x==y || elem x ys simonmar committed Jun 28, 2001 603 Don Stewart committed Mar 05, 2008 604 notElem _ [] = True simonmar committed Jun 28, 2001 605 606 607 notElem x (y:ys)= x /= y && notElem x ys #endif ross committed Sep 01, 2003 608 -- | 'lookup' @key assocs@ looks up a key in an association list. simonmar committed Jun 28, 2001 609 610 611 612 613 614 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 615 -- | Map a function over a list and concatenate the results. simonmar committed Jun 28, 2001 616 617 618 concatMap :: (a -> [b]) -> [a] -> [b] concatMap f = foldr ((++) . f) [] ross committed Sep 01, 2003 619 -- | Concatenate a list of lists. simonmar committed Jun 28, 2001 620 621 622 concat :: [[a]] -> [a] concat = foldr (++) [] pcapriotti committed Jul 25, 2012 623 624 {-# NOINLINE [1] concat #-} simonmar committed Jun 28, 2001 625 626 {-# RULES "concat" forall xs. concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs) simonmar committed Feb 05, 2002 627 -- We don't bother to turn non-fusible applications of concat back into concat simonmar committed Jun 28, 2001 628 #-} simonmar committed Feb 05, 2002 629 simonmar committed Jun 28, 2001 630 631 632 633 \end{code} \begin{code} ross committed Sep 01, 2003 634 635 636 -- | 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 637 638 (!!) :: [a] -> Int -> a #ifdef USE_REPORT_PRELUDE simonmar committed Dec 21, 2001 639 640 641 642 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 643 644 #else -- HBC version (stolen), then unboxified Jan Stolarek committed Sep 18, 2013 645 646 xs !! (I# n0) | isTrue# (n0 <# 0#) = error "Prelude.(!!): negative index\n" | otherwise = sub xs n0 simonmar committed Jun 28, 2001 647 where Don Stewart committed Mar 05, 2008 648 sub :: [a] -> Int# -> a simonmar committed Jun 28, 2001 649 sub [] _ = error "Prelude.(!!): index too large\n" Jan Stolarek committed Sep 18, 2013 650 sub (y:ys) n = if isTrue# (n ==# 0#) Don Stewart committed Mar 05, 2008 651 652 then y else sub ys (n -# 1#) simonmar committed Jun 28, 2001 653 654 655 656 657 #endif \end{code} %********************************************************* Don Stewart committed Mar 05, 2008 658 %* * simonmar committed Jun 28, 2001 659 \subsection{The zip family} Don Stewart committed Mar 05, 2008 660 %* * simonmar committed Jun 28, 2001 661 662 663 %********************************************************* \begin{code} Ian Lynagh committed Aug 05, 2008 664 foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c Joachim Breitner committed Jan 28, 2014 665 666 foldr2 k z = go where David Feuer committed Oct 01, 2014 667 go [] ys = ys seq z -- see #9495 for the seq Herbert Valerio Riedel committed Sep 24, 2014 668 669 go _xs [] = z go (x:xs) (y:ys) = k x y (go xs ys) Joachim Breitner committed Jan 28, 2014 670 {-# INLINE [0] foldr2 #-} pcapriotti committed Jul 25, 2012 671 Ian Lynagh committed Aug 05, 2008 672 foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d simonmar committed Jun 28, 2001 673 674 675 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 676 foldr2_right :: (a -> b -> c -> d) -> d -> b -> ([a] -> c) -> [a] -> d simonmar committed Jun 28, 2001 677 678 679 680 681 682 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 Jan Stolarek committed Sep 18, 2013 683 "foldr2/left" forall k z ys (g::forall b.(a->b->b)->b->b) . Don Stewart committed Mar 05, 2008 684 foldr2 k z (build g) ys = g (foldr2_left k z) (\_ -> z) ys simonmar committed Jun 28, 2001 685 Jan Stolarek committed Sep 18, 2013 686 "foldr2/right" forall k z xs (g::forall b.(a->b->b)->b->b) . Don Stewart committed Mar 05, 2008 687 foldr2 k z xs (build g) = g (foldr2_right k z) (\_ -> z) xs simonmar committed Jun 28, 2001 688 689 690 #-} \end{code} ross committed Sep 01, 2003 691 Zips for larger tuples are in the List module. simonmar committed Jun 28, 2001 692 693 694 \begin{code} ---------------------------------------------- ross committed Sep 01, 2003 695 696 697 -- | '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. David Feuer committed Oct 01, 2014 698 699 700 701 702 703 704 705 706 707 708 -- -- NOTE: GHC's implementation of @zip@ deviates slightly from the -- standard. In particular, Haskell 98 and Haskell 2010 require that -- @zip [x1,x2,...,xn] (y1:y2:...:yn:_|_) = [(x1,y1),(x2,y2),...,(xn,yn)]@ -- In GHC, however, -- @zip [x1,x2,...,xn] (y1:y2:...:yn:_|_) = (x1,y1):(x2,y2):...:(xn,yn):_|_@ -- That is, you cannot use termination of the left list to avoid hitting -- bottom in the right list. -- This deviation is necessary to make fusion with 'build' in the right -- list preserve semantics. pcapriotti committed Jul 25, 2012 709 {-# NOINLINE [1] zip #-} simonmar committed Jun 28, 2001 710 zip :: [a] -> [b] -> [(a,b)] David Feuer committed Oct 01, 2014 711 712 zip [] bs = bs seq [] -- see #9495 for the seq zip _as [] = [] simonmar committed Feb 05, 2002 713 zip (a:as) (b:bs) = (a,b) : zip as bs simonmar committed Jun 28, 2001 714 simonmar committed Dec 21, 2001 715 {-# INLINE [0] zipFB #-} Ian Lynagh committed Aug 05, 2008 716 zipFB :: ((a, b) -> c -> d) -> a -> b -> c -> d rl@cse.unsw.edu.au committed Nov 26, 2009 717 zipFB c = \x y r -> (x,y) c r simonmar committed Jun 28, 2001 718 719 {-# RULES Don Stewart committed Mar 05, 2008 720 721 "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 722 723 724 725 726 #-} \end{code} \begin{code} ---------------------------------------------- ross committed Sep 01, 2003 727 728 -- | 'zip3' takes three lists and returns a list of triples, analogous to -- 'zip'. simonmar committed Jun 28, 2001 729 730 731 732 733 734 735 736 737 738 739 740 741 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 742 743 744 745 -- | '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. David Feuer committed Oct 01, 2014 746 747 748 749 750 751 752 753 754 755 756 757 -- -- NOTE: GHC's implementation of @zipWith@ deviates slightly from the -- standard. In particular, Haskell 98 and Haskell 2010 require that -- @zipWith (,) [x1,x2,...,xn] (y1:y2:...:yn:_|_) = [(x1,y1),(x2,y2),...,(xn,yn)]@ -- In GHC, however, -- @zipWith (,) [x1,x2,...,xn] (y1:y2:...:yn:_|_) = (x1,y1):(x2,y2):...:(xn,yn):_|_@ -- That is, you cannot use termination of the left list to avoid hitting -- bottom in the right list. -- This deviation is necessary to make fusion with 'build' in the right -- list preserve semantics. pcapriotti committed Jul 25, 2012 758 {-# NOINLINE [1] zipWith #-} simonmar committed Jun 28, 2001 759 zipWith :: (a->b->c) -> [a]->[b]->[c] David Feuer committed Oct 01, 2014 760 761 762 zipWith _f [] bs = bs seq [] -- see #9495 for the seq zipWith _f _as [] = [] zipWith f (a:as) (b:bs) = f a b : zipWith f as bs simonmar committed Jun 28, 2001 763 rl@cse.unsw.edu.au committed Nov 25, 2009 764 765 -- 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 766 {-# INLINE [0] zipWithFB #-} Ian Lynagh committed Aug 05, 2008 767 zipWithFB :: (a -> b -> c) -> (d -> e -> a) -> d -> e -> b -> c rl@cse.unsw.edu.au committed Nov 25, 2009 768 zipWithFB c f = \x y r -> (x f y) c r simonmar committed Jun 28, 2001 769 770 {-# RULES Don Stewart committed Mar 05, 2008 771 772 "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 773 774 775 776 #-} \end{code} \begin{code} ross committed Sep 01, 2003 777 778 779 -- | 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 780 781 782 783 784 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 785 786 -- | 'unzip' transforms a list of pairs into a list of first components -- and a list of second components. simonmar committed Jun 28, 2001 787 788 789 790 unzip :: [(a,b)] -> ([a],[b]) {-# INLINE unzip #-} unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[]) ross committed Sep 01, 2003 791 792 -- | The 'unzip3' function takes a list of triples and returns three -- lists, analogous to 'unzip'. simonmar committed Jun 28, 2001 793 794 795 796 797 798 799 800 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 801 %* * simonmar committed Jun 28, 2001 802 \subsection{Error code} Don Stewart committed Mar 05, 2008 803 %* * simonmar committed Jun 28, 2001 804 805 806 807 808 809 810 811 812 813 814 815 816 %********************************************************* 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}