Movatterモバイル変換

{-# LANGUAGE DeriveDataTypeable #-}{-# LANGUAGE DeriveGeneric #-}{-# LANGUAGE Trustworthy #-}-- can't use Safe due to IsList instance{-# LANGUAGE TypeFamilies #-}------------------------------------------------------------------------------- |-- Module      :  Data.List.NonEmpty-- Copyright   :  (C) 2011-2015 Edward Kmett,--                (C) 2010 Tony Morris, Oliver Taylor, Eelis van der Weegen-- License     :  BSD-style (see the file LICENSE)---- Maintainer  :  libraries@haskell.org-- Stability   :  provisional-- Portability :  portable---- A 'NonEmpty' list is one which always has at least one element, but-- is otherwise identical to the traditional list type in complexity-- and in terms of API. You will almost certainly want to import this-- module @qualified@.---- @since 4.9.0.0----------------------------------------------------------------------------moduleData.List.NonEmpty(-- * The type of non-empty streamsNonEmpty(..)-- * Non-empty stream transformations,map-- :: (a -> b) -> NonEmpty a -> NonEmpty b,intersperse-- :: a -> NonEmpty a -> NonEmpty a,scanl-- :: Foldable f => (b -> a -> b) -> b -> f a -> NonEmpty b,scanr-- :: Foldable f => (a -> b -> b) -> b -> f a -> NonEmpty b,scanl1-- :: (a -> a -> a) -> NonEmpty a -> NonEmpty a,scanr1-- :: (a -> a -> a) -> NonEmpty a -> NonEmpty a,transpose-- :: NonEmpty (NonEmpty a) -> NonEmpty (NonEmpty a),sortBy-- :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a,sortWith-- :: Ord o => (a -> o) -> NonEmpty a -> NonEmpty a-- * Basic functions,length-- :: NonEmpty a -> Int,head-- :: NonEmpty a -> a,tail-- :: NonEmpty a -> [a],last-- :: NonEmpty a -> a,init-- :: NonEmpty a -> [a],(<|),cons-- :: a -> NonEmpty a -> NonEmpty a,uncons-- :: NonEmpty a -> (a, Maybe (NonEmpty a)),unfoldr-- :: (a -> (b, Maybe a)) -> a -> NonEmpty b,sort-- :: NonEmpty a -> NonEmpty a,reverse-- :: NonEmpty a -> NonEmpty a,inits-- :: Foldable f => f a -> NonEmpty a,tails-- :: Foldable f => f a -> NonEmpty a-- * Building streams,iterate-- :: (a -> a) -> a -> NonEmpty a,repeat-- :: a -> NonEmpty a,cycle-- :: NonEmpty a -> NonEmpty a,unfold-- :: (a -> (b, Maybe a) -> a -> NonEmpty b,insert-- :: (Foldable f, Ord a) => a -> f a -> NonEmpty a,some1-- :: Alternative f => f a -> f (NonEmpty a)-- * Extracting sublists,take-- :: Int -> NonEmpty a -> [a],drop-- :: Int -> NonEmpty a -> [a],splitAt-- :: Int -> NonEmpty a -> ([a], [a]),takeWhile-- :: Int -> NonEmpty a -> [a],dropWhile-- :: Int -> NonEmpty a -> [a],span-- :: Int -> NonEmpty a -> ([a],[a]),break-- :: Int -> NonEmpty a -> ([a],[a]),filter-- :: (a -> Bool) -> NonEmpty a -> [a],partition-- :: (a -> Bool) -> NonEmpty a -> ([a],[a]),group-- :: Foldable f => Eq a => f a -> [NonEmpty a],groupBy-- :: Foldable f => (a -> a -> Bool) -> f a -> [NonEmpty a],groupWith-- :: (Foldable f, Eq b) => (a -> b) -> f a -> [NonEmpty a],groupAllWith-- :: (Foldable f, Ord b) => (a -> b) -> f a -> [NonEmpty a],group1-- :: Eq a => NonEmpty a -> NonEmpty (NonEmpty a),groupBy1-- :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty (NonEmpty a),groupWith1-- :: (Foldable f, Eq b) => (a -> b) -> f a -> NonEmpty (NonEmpty a),groupAllWith1-- :: (Foldable f, Ord b) => (a -> b) -> f a -> NonEmpty (NonEmpty a)-- * Sublist predicates,isPrefixOf-- :: Foldable f => f a -> NonEmpty a -> Bool-- * \"Set\" operations,nub-- :: Eq a => NonEmpty a -> NonEmpty a,nubBy-- :: (a -> a -> Bool) -> NonEmpty a -> NonEmpty a-- * Indexing streams,(!!)-- :: NonEmpty a -> Int -> a-- * Zipping and unzipping streams,zip-- :: NonEmpty a -> NonEmpty b -> NonEmpty (a,b),zipWith-- :: (a -> b -> c) -> NonEmpty a -> NonEmpty b -> NonEmpty c,unzip-- :: NonEmpty (a, b) -> (NonEmpty a, NonEmpty b)-- * Converting to and from a list,fromList-- :: [a] -> NonEmpty a,toList-- :: NonEmpty a -> [a],nonEmpty-- :: [a] -> Maybe (NonEmpty a),xor-- :: NonEmpty a -> Bool)whereimportPreludehiding(break,cycle,drop,dropWhile,filter,foldl,foldr,head,init,iterate,last,length,map,repeat,reverse,scanl,scanl1,scanr,scanr1,span,splitAt,tail,take,takeWhile,unzip,zip,zipWith,(!!))importqualifiedPreludeimportControl.Applicative(Applicative(..),Alternative(many))importData.Foldablehiding(length,toList)importqualifiedData.FoldableasFoldableimportData.Function(on)importqualifiedData.ListasListimportData.Ord(comparing)importGHC.Base(NonEmpty(..))infixr5<|-- | Number of elements in 'NonEmpty' list.length::NonEmptya->Intlength(_:|xs)=1+Prelude.lengthxs-- | Compute n-ary logic exclusive OR operation on 'NonEmpty' list.xor::NonEmptyBool->Boolxor(x:|xs)=foldrxor'xxswherexor'Truey=notyxor'Falsey=y-- | 'unfold' produces a new stream by repeatedly applying the unfolding-- function to the seed value to produce an element of type @b@ and a new-- seed value.  When the unfolding function returns 'Nothing' instead of-- a new seed value, the stream ends.unfold::(a->(b,Maybea))->a->NonEmptybunfoldfa=casefaof(b,Nothing)->b:|[](b,Justc)->b<|unfoldfc{-# DEPRECATEDunfold"Use unfoldr"#-}-- Deprecated in 8.2.1, remove in 8.4-- | 'nonEmpty' efficiently turns a normal list into a 'NonEmpty' stream,-- producing 'Nothing' if the input is empty.nonEmpty::[a]->Maybe(NonEmptya)nonEmpty[]=NothingnonEmpty(a:as)=Just(a:|as)-- | 'uncons' produces the first element of the stream, and a stream of the-- remaining elements, if any.uncons::NonEmptya->(a,Maybe(NonEmptya))uncons~(a:|as)=(a,nonEmptyas)-- | The 'unfoldr' function is analogous to "Data.List"'s-- 'Data.List.unfoldr' operation.unfoldr::(a->(b,Maybea))->a->NonEmptybunfoldrfa=casefaof(b,mc)->b:|maybe[]gomcwheregoc=casefcof(d,me)->d:maybe[]gome-- | Extract the first element of the stream.head::NonEmptya->ahead~(a:|_)=a-- | Extract the possibly-empty tail of the stream.tail::NonEmptya->[a]tail~(_:|as)=as-- | Extract the last element of the stream.last::NonEmptya->alast~(a:|as)=List.last(a:as)-- | Extract everything except the last element of the stream.init::NonEmptya->[a]init~(a:|as)=List.init(a:as)-- | Prepend an element to the stream.(<|)::a->NonEmptya->NonEmptyaa<|~(b:|bs)=a:|b:bs-- | Synonym for '<|'.cons::a->NonEmptya->NonEmptyacons=(<|)-- | Sort a stream.sort::Orda=>NonEmptya->NonEmptyasort=liftList.sort-- | Converts a normal list to a 'NonEmpty' stream.---- Raises an error if given an empty list.fromList::[a]->NonEmptyafromList(a:as)=a:|asfromList[]=errorWithoutStackTrace"NonEmpty.fromList: empty list"-- | Convert a stream to a normal list efficiently.toList::NonEmptya->[a]toList~(a:|as)=a:as-- | Lift list operations to work on a 'NonEmpty' stream.---- /Beware/: If the provided function returns an empty list,-- this will raise an error.lift::Foldablef=>([a]->[b])->fa->NonEmptybliftf=fromList.f.Foldable.toList-- | Map a function over a 'NonEmpty' stream.map::(a->b)->NonEmptya->NonEmptybmapf~(a:|as)=fa:|fmapfas-- | The 'inits' function takes a stream @xs@ and returns all the-- finite prefixes of @xs@.inits::Foldablef=>fa->NonEmpty[a]inits=fromList.List.inits.Foldable.toList-- | The 'tails' function takes a stream @xs@ and returns all the-- suffixes of @xs@.tails::Foldablef=>fa->NonEmpty[a]tails=fromList.List.tails.Foldable.toList-- | @'insert' x xs@ inserts @x@ into the last position in @xs@ where it-- is still less than or equal to the next element. In particular, if the-- list is sorted beforehand, the result will also be sorted.insert::(Foldablef,Orda)=>a->fa->NonEmptyainserta=fromList.List.inserta.Foldable.toList-- | @'some1' x@ sequences @x@ one or more times.some1::Alternativef=>fa->f(NonEmptya)some1x=liftA2(:|)x(manyx)-- | 'scanl' is similar to 'foldl', but returns a stream 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::Foldablef=>(b->a->b)->b->fa->NonEmptybscanlfz=fromList.List.scanlfz.Foldable.toList-- | 'scanr' is the right-to-left dual of 'scanl'.-- Note that---- > head (scanr f z xs) == foldr f z xs.scanr::Foldablef=>(a->b->b)->b->fa->NonEmptybscanrfz=fromList.List.scanrfz.Foldable.toList-- | 'scanl1' is a variant of 'scanl' that has no starting value argument:---- > scanl1 f [x1, x2, ...] == x1 :| [x1 `f` x2, x1 `f` (x2 `f` x3), ...]scanl1::(a->a->a)->NonEmptya->NonEmptyascanl1f~(a:|as)=fromList(List.scanlfaas)-- | 'scanr1' is a variant of 'scanr' that has no starting value argument.scanr1::(a->a->a)->NonEmptya->NonEmptyascanr1f~(a:|as)=fromList(List.scanr1f(a:as))-- | 'intersperse x xs' alternates elements of the list with copies of @x@.---- > intersperse 0 (1 :| [2,3]) == 1 :| [0,2,0,3]intersperse::a->NonEmptya->NonEmptyainterspersea~(b:|bs)=b:|casebsof[]->[]_->a:List.intersperseabs-- | @'iterate' f x@ produces the infinite sequence-- of repeated applications of @f@ to @x@.---- > iterate f x = x :| [f x, f (f x), ..]iterate::(a->a)->a->NonEmptyaiteratefa=a:|List.iteratef(fa)-- | @'cycle' xs@ returns the infinite repetition of @xs@:---- > cycle (1 :| [2,3]) = 1 :| [2,3,1,2,3,...]cycle::NonEmptya->NonEmptyacycle=fromList.List.cycle.toList-- | 'reverse' a finite NonEmpty stream.reverse::NonEmptya->NonEmptyareverse=liftList.reverse-- | @'repeat' x@ returns a constant stream, where all elements are-- equal to @x@.repeat::a->NonEmptyarepeata=a:|List.repeata-- | @'take' n xs@ returns the first @n@ elements of @xs@.take::Int->NonEmptya->[a]taken=List.taken.toList-- | @'drop' n xs@ drops the first @n@ elements off the front of-- the sequence @xs@.drop::Int->NonEmptya->[a]dropn=List.dropn.toList-- | @'splitAt' n xs@ returns a pair consisting of the prefix of @xs@-- of length @n@ and the remaining stream immediately following this prefix.---- > 'splitAt' n xs == ('take' n xs, 'drop' n xs)-- > xs == ys ++ zs where (ys, zs) = 'splitAt' n xssplitAt::Int->NonEmptya->([a],[a])splitAtn=List.splitAtn.toList-- | @'takeWhile' p xs@ returns the longest prefix of the stream-- @xs@ for which the predicate @p@ holds.takeWhile::(a->Bool)->NonEmptya->[a]takeWhilep=List.takeWhilep.toList-- | @'dropWhile' p xs@ returns the suffix remaining after-- @'takeWhile' p xs@.dropWhile::(a->Bool)->NonEmptya->[a]dropWhilep=List.dropWhilep.toList-- | @'span' p xs@ returns the longest prefix of @xs@ that satisfies-- @p@, together with the remainder of the stream.---- > 'span' p xs == ('takeWhile' p xs, 'dropWhile' p xs)-- > xs == ys ++ zs where (ys, zs) = 'span' p xsspan::(a->Bool)->NonEmptya->([a],[a])spanp=List.spanp.toList-- | The @'break' p@ function is equivalent to @'span' (not . p)@.break::(a->Bool)->NonEmptya->([a],[a])breakp=span(not.p)-- | @'filter' p xs@ removes any elements from @xs@ that do not satisfy @p@.filter::(a->Bool)->NonEmptya->[a]filterp=List.filterp.toList-- | The 'partition' function takes a predicate @p@ and a stream-- @xs@, and returns a pair of lists. The first list corresponds to the-- elements of @xs@ for which @p@ holds; the second corresponds to the-- elements of @xs@ for which @p@ does not hold.---- > 'partition' p xs = ('filter' p xs, 'filter' (not . p) xs)partition::(a->Bool)->NonEmptya->([a],[a])partitionp=List.partitionp.toList-- | The 'group' function takes a stream and returns a list of-- streams such that flattening the resulting list is equal to the-- argument.  Moreover, each stream in the resulting list-- contains only equal elements.  For example, in list notation:---- > 'group' $ 'cycle' "Mississippi"-- >   = "M" : "i" : "ss" : "i" : "ss" : "i" : "pp" : "i" : "M" : "i" : ...group::(Foldablef,Eqa)=>fa->[NonEmptya]group=groupBy(==)-- | 'groupBy' operates like 'group', but uses the provided equality-- predicate instead of `==`.groupBy::Foldablef=>(a->a->Bool)->fa->[NonEmptya]groupByeq0=goeq0.Foldable.toListwherego_[]=[]goeq(x:xs)=(x:|ys):groupByeqzswhere(ys,zs)=List.span(eqx)xs-- | 'groupWith' operates like 'group', but uses the provided projection when-- comparing for equalitygroupWith::(Foldablef,Eqb)=>(a->b)->fa->[NonEmptya]groupWithf=groupBy((==)`on`f)-- | 'groupAllWith' operates like 'groupWith', but sorts the list-- first so that each equivalence class has, at most, one list in the-- outputgroupAllWith::(Ordb)=>(a->b)->[a]->[NonEmptya]groupAllWithf=groupWithf.List.sortBy(compare`on`f)-- | 'group1' operates like 'group', but uses the knowledge that its-- input is non-empty to produce guaranteed non-empty output.group1::Eqa=>NonEmptya->NonEmpty(NonEmptya)group1=groupBy1(==)-- | 'groupBy1' is to 'group1' as 'groupBy' is to 'group'.groupBy1::(a->a->Bool)->NonEmptya->NonEmpty(NonEmptya)groupBy1eq(x:|xs)=(x:|ys):|groupByeqzswhere(ys,zs)=List.span(eqx)xs-- | 'groupWith1' is to 'group1' as 'groupWith' is to 'group'groupWith1::(Eqb)=>(a->b)->NonEmptya->NonEmpty(NonEmptya)groupWith1f=groupBy1((==)`on`f)-- | 'groupAllWith1' is to 'groupWith1' as 'groupAllWith' is to 'groupWith'groupAllWith1::(Ordb)=>(a->b)->NonEmptya->NonEmpty(NonEmptya)groupAllWith1f=groupWith1f.sortWithf-- | The 'isPrefix' function returns @True@ if the first argument is-- a prefix of the second.isPrefixOf::Eqa=>[a]->NonEmptya->BoolisPrefixOf[]_=TrueisPrefixOf(y:ys)(x:|xs)=(y==x)&&List.isPrefixOfysxs-- | @xs !! n@ returns the element of the stream @xs@ at index-- @n@. Note that the head of the stream has index 0.---- /Beware/: a negative or out-of-bounds index will cause an error.(!!)::NonEmptya->Int->a(!!)~(x:|xs)n|n==0=x|n>0=xsList.!!(n-1)|otherwise=errorWithoutStackTrace"NonEmpty.!! negative argument"infixl9!!-- | The 'zip' function takes two streams and returns a stream of-- corresponding pairs.zip::NonEmptya->NonEmptyb->NonEmpty(a,b)zip~(x:|xs)~(y:|ys)=(x,y):|List.zipxsys-- | The 'zipWith' function generalizes 'zip'. Rather than tupling-- the elements, the elements are combined using the function-- passed as the first argument.zipWith::(a->b->c)->NonEmptya->NonEmptyb->NonEmptyczipWithf~(x:|xs)~(y:|ys)=fxy:|List.zipWithfxsys-- | The 'unzip' function is the inverse of the 'zip' function.unzip::Functorf=>f(a,b)->(fa,fb)unzipxs=(fst<$>xs,snd<$>xs)-- | The 'nub' function removes duplicate elements from a list. In-- particular, it keeps only the first occurrence of each element.-- (The name 'nub' means \'essence\'.)-- It is a special case of 'nubBy', which allows the programmer to-- supply their own inequality test.nub::Eqa=>NonEmptya->NonEmptyanub=nubBy(==)-- | The 'nubBy' function behaves just like 'nub', except it uses a-- user-supplied equality predicate instead of the overloaded '=='-- function.nubBy::(a->a->Bool)->NonEmptya->NonEmptyanubByeq(a:|as)=a:|List.nubByeq(List.filter(\b->not(eqab))as)-- | 'transpose' for 'NonEmpty', behaves the same as 'Data.List.transpose'-- The rows/columns need not be the same length, in which case-- > transpose . transpose /= idtranspose::NonEmpty(NonEmptya)->NonEmpty(NonEmptya)transpose=fmapfromList.fromList.List.transpose.toList.fmaptoList-- | 'sortBy' for 'NonEmpty', behaves the same as 'Data.List.sortBy'sortBy::(a->a->Ordering)->NonEmptya->NonEmptyasortByf=lift(List.sortByf)-- | 'sortWith' for 'NonEmpty', behaves the same as:---- > sortBy . comparingsortWith::Ordo=>(a->o)->NonEmptya->NonEmptyasortWith=sortBy.comparing