Movatterモバイル変換

{-# LANGUAGE Trustworthy #-}{-# LANGUAGE CPP, NoImplicitPrelude, MagicHash #-}{-# OPTIONS_HADDOCK hide #-}------------------------------------------------------------------------------- |-- 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--------------------------------------------------------------------------------- #hidemoduleGHC.List(-- [] (..),          -- Not Haskell 98; built in syntaxmap,(++),filter,concat,head,last,tail,init,null,length,(!!),foldl,scanl,scanl1,foldr,foldr1,scanr,scanr1,iterate,repeat,replicate,cycle,take,drop,splitAt,takeWhile,dropWhile,span,break,reverse,and,or,any,all,elem,notElem,lookup,concatMap,zip,zip3,zipWith,zipWith3,unzip,unzip3,errorEmptyList,#ifndef USE_REPORT_PRELUDE-- non-standard, but hidden when creating the Prelude-- export list.takeUInt_append#endif)whereimportData.MaybeimportGHC.Baseinfixl9!!infix4`elem`,`notElem`

-- | Extract the first element of a list, which must be non-empty.head::[a]->ahead(x:_)=xhead[]=badHeadbadHead::abadHead=errorEmptyList"head"-- This rule is useful in cases like--      head [y | (x,y) <- ps, x==t]{-# RULES"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) #-}-- | Extract the elements after the head of a list, which must be non-empty.tail::[a]->[a]tail(_:xs)=xstail[]=errorEmptyList"tail"-- | Extract the last element of a list, which must be finite and non-empty.last::[a]->a#ifdef USE_REPORT_PRELUDElast[x]=xlast(_:xs)=lastxslast[]=errorEmptyList"last"#else-- eliminate repeated caseslast[]=errorEmptyList"last"last(x:xs)=last'xxswherelast'y[]=ylast'_(y:ys)=last'yys#endif-- | Return all the elements of a list except the last one.-- The list must be non-empty.init::[a]->[a]#ifdef USE_REPORT_PRELUDEinit[x]=[]init(x:xs)=x:initxsinit[]=errorEmptyList"init"#else-- eliminate repeated casesinit[]=errorEmptyList"init"init(x:xs)=init'xxswhereinit'_[]=[]init'y(z:zs)=y:init'zzs#endif-- | Test whether a list is empty.null::[a]->Boolnull[]=Truenull(_:_)=False-- | /O(n)/. 'length' returns the length of a finite list as an 'Int'.-- It is an instance of the more general 'Data.List.genericLength',-- the result type of which may be any kind of number.length::[a]->Intlengthl=lenl0#wherelen::[a]->Int#->Intlen[]a#=I#a#len(_:xs)a#=lenxs(a#+#1#)-- | '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]filter::(a->Bool)->[a]->[a]filter_pred[]=[]filterpred(x:xs)|predx=x:filterpredxs|otherwise=filterpredxs{-# NOINLINE [0] filterFB #-}filterFB::(a->b->b)->(a->Bool)->a->b->bfilterFBcpxr|px=x`c`r|otherwise=r{-# RULES"filter"     [~1] forall p xs.  filter p xs = build (\c n -> foldr (filterFB c p) n xs)"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) #-}-- 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.-- | '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.-- 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 xsfoldl::(a->b->a)->a->[b]->afoldlfz0xs0=lgoz0xs0wherelgoz[]=zlgoz(x:xs)=lgo(fzx)xs-- | '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.scanl::(a->b->a)->a->[b]->[a]scanlfqls=q:(caselsof[]->[]x:xs->scanlf(fqx)xs)-- | 'scanl1' is a variant of 'scanl' that has no starting value argument:---- > scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]scanl1::(a->a->a)->[a]->[a]scanl1f(x:xs)=scanlfxxsscanl1_[]=[]-- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the-- above functions.-- | 'foldr1' is a variant of 'foldr' that has no starting value argument,-- and thus must be applied to non-empty lists.foldr1::(a->a->a)->[a]->afoldr1_[x]=xfoldr1f(x:xs)=fx(foldr1fxs)foldr1_[]=errorEmptyList"foldr1"-- | 'scanr' is the right-to-left dual of 'scanl'.-- Note that---- > head (scanr f z xs) == foldr f z xs.scanr::(a->b->b)->b->[a]->[b]scanr_q0[]=[q0]scanrfq0(x:xs)=fxq:qswhereqs@(q:_)=scanrfq0xs-- | 'scanr1' is a variant of 'scanr' that has no starting value argument.scanr1::(a->a->a)->[a]->[a]scanr1_[]=[]scanr1_[x]=[x]scanr1f(x:xs)=fxq:qswhereqs@(q:_)=scanr1fxs-- | 'iterate' @f x@ returns an infinite list of repeated applications-- of @f@ to @x@:---- > iterate f x == [x, f x, f (f x), ...]iterate::(a->a)->a->[a]iteratefx=x:iteratef(fx)iterateFB::(a->b->b)->(a->a)->a->biterateFBcfx=x`c`iterateFBcf(fx){-# RULES"iterate"    [~1] forall f x.   iterate f x = build (\c _n -> iterateFB c f x)"iterateFB"  [1]                iterateFB (:) = iterate #-}-- | 'repeat' @x@ is an infinite list, with @x@ the value of every element.repeat::a->[a]{-# INLINE [0] repeat #-}-- The pragma just gives the rules more chance to firerepeatx=xswherexs=x:xs{-# INLINE [0] repeatFB #-}-- dittorepeatFB::(a->b->b)->a->brepeatFBcx=xswherexs=x`c`xs{-# RULES"repeat"    [~1] forall x. repeat x = build (\c _n -> repeatFB c x)"repeatFB"  [1]  repeatFB (:)       = repeat #-}-- | '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.{-# INLINE replicate #-}replicate::Int->a->[a]replicatenx=taken(repeatx)-- | 'cycle' ties a finite list into a circular one, or equivalently,-- the infinite repetition of the original list.  It is the identity-- on infinite lists.cycle::[a]->[a]cycle[]=error"Prelude.cycle: empty list"cyclexs=xs'wherexs'=xs++xs'-- | 'takeWhile', applied to a predicate @p@ and a list @xs@, returns the-- 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] == []--takeWhile::(a->Bool)->[a]->[a]takeWhile_[]=[]takeWhilep(x:xs)|px=x:takeWhilepxs|otherwise=[]-- | '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]--dropWhile::(a->Bool)->[a]->[a]dropWhile_[]=[]dropWhilepxs@(x:xs')|px=dropWhilepxs'|otherwise=xs-- | 'take' @n@, applied to a list @xs@, returns the prefix of @xs@-- 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] == []---- It is an instance of the more general 'Data.List.genericTake',-- in which @n@ may be of any integral type.take::Int->[a]->[a]-- | 'drop' @n xs@ returns the suffix of @xs@-- 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]---- It is an instance of the more general 'Data.List.genericDrop',-- in which @n@ may be of any integral type.drop::Int->[a]->[a]-- | '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])---- It is equivalent to @('take' n xs, 'drop' n xs)@ when @n@ is not @_|_@-- (@splitAt _|_ xs = _|_@).-- 'splitAt' is an instance of the more general 'Data.List.genericSplitAt',-- in which @n@ may be of any integral type.splitAt::Int->[a]->([a],[a])#ifdef USE_REPORT_PRELUDEtaken_|n<=0=[]take_[]=[]taken(x:xs)=x:take(n-1)xsdropnxs|n<=0=xsdrop_[]=[]dropn(_:xs)=drop(n-1)xssplitAtnxs=(takenxs,dropnxs)#else /* hack away */{-# RULES"take"     [~1] forall n xs . take n xs = takeFoldr n xs"takeList"  [1] forall n xs . foldr (takeFB (:) []) (takeConst []) xs n = takeUInt n xs #-}{-# INLINE takeFoldr #-}takeFoldr::Int->[a]->[a]takeFoldr(I#n#)xs=build(\cnil->ifn#<=#0#thennilelsefoldr(takeFBcnil)(takeConstnil)xsn#){-# 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#->atakeConstx_=x{-# NOINLINE [0] takeFB #-}takeFB::(a->b->b)->b->a->(Int#->b)->Int#->btakeFBcnxxsm|m<=#1#=x`c`n|otherwise=x`c`xs(m-#1#){-# INLINE [0] take #-}take(I#n#)xs=takeUIntn#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 <= maxInttakeUInt::Int#->[b]->[b]takeUIntnxs|n>=#0#=take_unsafe_UIntnxs|otherwise=[]take_unsafe_UInt::Int#->[b]->[b]take_unsafe_UInt0#_=[]take_unsafe_UIntmls=caselsof[]->[](x:xs)->x:take_unsafe_UInt(m-#1#)xstakeUInt_append::Int#->[b]->[b]->[b]takeUInt_appendnxsrs|n>=#0#=take_unsafe_UInt_appendnxsrs|otherwise=[]take_unsafe_UInt_append::Int#->[b]->[b]->[b]take_unsafe_UInt_append0#_rs=rstake_unsafe_UInt_appendmlsrs=caselsof[]->rs(x:xs)->x:take_unsafe_UInt_append(m-#1#)xsrsdrop(I#n#)ls|n#<#0#=ls|otherwise=drop#n#lswheredrop#::Int#->[a]->[a]drop#0#xs=xsdrop#_xs@[]=xsdrop#m#(_:xs)=drop#(m#-#1#)xssplitAt(I#n#)ls|n#<#0#=([],ls)|otherwise=splitAt#n#lswheresplitAt#::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#endif /* USE_REPORT_PRELUDE */-- | '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)@span::(a->Bool)->[a]->([a],[a])span_xs@[]=(xs,xs)spanpxs@(x:xs')|px=let(ys,zs)=spanpxs'in(x:ys,zs)|otherwise=([],xs)-- | '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)@.break::(a->Bool)->[a]->([a],[a])#ifdef USE_REPORT_PRELUDEbreakp=span(not.p)#else-- HBC version (stolen)break_xs@[]=(xs,xs)breakpxs@(x:xs')|px=([],xs)|otherwise=let(ys,zs)=breakpxs'in(x:ys,zs)#endif-- | 'reverse' @xs@ returns the elements of @xs@ in reverse order.-- @xs@ must be finite.reverse::[a]->[a]#ifdef USE_REPORT_PRELUDEreverse=foldl(flip(:))[]#elsereversel=revl[]whererev[]a=arev(x:xs)a=revxs(x:a)#endif-- | '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#ifdef USE_REPORT_PRELUDEand=foldr(&&)Trueor=foldr(||)False#elseand[]=Trueand(x:xs)=x&&andxsor[]=Falseor(x:xs)=x||orxs{-# RULES"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 #-}#endif-- | Applied to a predicate and a list, 'any' determines if any element-- 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.any::(a->Bool)->[a]->Bool-- | Applied to a predicate and a list, 'all' determines if all elements-- 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.all::(a->Bool)->[a]->Bool#ifdef USE_REPORT_PRELUDEanyp=or.mappallp=and.mapp#elseany_[]=Falseanyp(x:xs)=px||anypxsall_[]=Trueallp(x:xs)=px&&allpxs{-# 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@.  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::(Eqa)=>a->[a]->Bool-- | 'notElem' is the negation of 'elem'.notElem::(Eqa)=>a->[a]->Bool#ifdef USE_REPORT_PRELUDEelemx=any(==x)notElemx=all(/=x)#elseelem_[]=Falseelemx(y:ys)=x==y||elemxysnotElem_[]=TruenotElemx(y:ys)=x/=y&&notElemxys#endif-- | 'lookup' @key assocs@ looks up a key in an association list.lookup::(Eqa)=>a->[(a,b)]->Maybeblookup_key[]=Nothinglookupkey((x,y):xys)|key==x=Justy|otherwise=lookupkeyxys-- | Map a function over a list and concatenate the results.concatMap::(a->[b])->[a]->[b]concatMapf=foldr((++).f)[]-- | Concatenate a list of lists.concat::[[a]]->[a]concat=foldr(++)[]{-# RULES  "concat" forall xs. concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)-- We don't bother to turn non-fusible applications of concat back into concat #-}

-- | 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.(!!)::[a]->Int->a#ifdef USE_REPORT_PRELUDExs!!n|n<0=error"Prelude.!!: negative index"[]!!_=error"Prelude.!!: index too large"(x:_)!!0=x(_:xs)!!n=xs!!(n-1)#else-- HBC version (stolen), then unboxified-- The semantics is not quite the same for error conditions-- in the more efficient version.--xs!!(I#n0)|n0<#0#=error"Prelude.(!!): negative index\n"|otherwise=subxsn0wheresub::[a]->Int#->asub[]_=error"Prelude.(!!): index too large\n"sub(y:ys)n=ifn==#0#thenyelsesubys(n-#1#)#endif

foldr2::(a->b->c->c)->c->[a]->[b]->cfoldr2_kz[]_ys=zfoldr2_kz_xs[]=zfoldr2kz(x:xs)(y:ys)=kxy(foldr2kzxsys)foldr2_left::(a->b->c->d)->d->a->([b]->c)->[b]->dfoldr2_left_kz_x_r[]=zfoldr2_leftk_zxr(y:ys)=kxy(rys)foldr2_right::(a->b->c->d)->d->b->([a]->c)->[a]->dfoldr2_right_kz_y_r[]=zfoldr2_rightk_zyr(x:xs)=kxy(rxs)-- 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"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"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 #-}

------------------------------------------------ | '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.zip::[a]->[b]->[(a,b)]zip(a:as)(b:bs)=(a,b):zipasbszip__=[]{-# INLINE [0] zipFB #-}zipFB::((a,b)->c->d)->a->b->c->dzipFBc=\xyr->(x,y)`c`r{-# RULES"zip"      [~1] forall xs ys. zip xs ys = build (\c n -> foldr2 (zipFB c) n xs ys)"zipList"  [1]  foldr2 (zipFB (:)) []   = zip #-}

------------------------------------------------ | 'zip3' takes three lists and returns a list of triples, analogous to-- 'zip'.zip3::[a]->[b]->[c]->[(a,b,c)]-- Specification-- zip3 =  zipWith3 (,,)zip3(a:as)(b:bs)(c:cs)=(a,b,c):zip3asbscszip3___=[]

------------------------------------------------ | '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.zipWith::(a->b->c)->[a]->[b]->[c]zipWithf(a:as)(b:bs)=fab:zipWithfasbszipWith___=[]-- zipWithFB must have arity 2 since it gets two arguments in the "zipWith"-- rule; it might not get inlined otherwise{-# INLINE [0] zipWithFB #-}zipWithFB::(a->b->c)->(d->e->a)->d->e->b->czipWithFBcf=\xyr->(x`f`y)`c`r{-# RULES"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  #-}

-- | 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'.zipWith3::(a->b->c->d)->[a]->[b]->[c]->[d]zipWith3z(a:as)(b:bs)(c:cs)=zabc:zipWith3zasbscszipWith3____=[]-- | 'unzip' transforms a list of pairs into a list of first components-- and a list of second components.unzip::[(a,b)]->([a],[b]){-# INLINE unzip #-}unzip=foldr(\(a,b)~(as,bs)->(a:as,b:bs))([],[])-- | The 'unzip3' function takes a list of triples and returns three-- lists, analogous to 'unzip'.unzip3::[(a,b,c)]->([a],[b],[c]){-# INLINE unzip3 #-}unzip3=foldr(\(a,b,c)~(as,bs,cs)->(a:as,b:bs,c:cs))([],[],[])

errorEmptyList::String->aerrorEmptyListfun=error(prel_list_str++fun++": empty list")prel_list_str::Stringprel_list_str="Prelude."