Safe Haskell	Trustworthy
Language	Haskell2010

Data.List.Compat

Synopsis

module Data.List
compareLength :: [a] -> Int -> Ordering
inits1 :: [a] -> [NonEmpty a]
tails1 :: [a] -> [NonEmpty a]
data List a

Documentation

module Data.List

compareLength :: [a] -> Int -> Ordering Source #

Use compareLength xs n as a safer and faster alternative to compare (length xs) n. Similarly, it's better to write compareLength xs 10 == LT instead of length xs < 10.

While length would force and traverse the entire spine of xs (which could even diverge if xs is infinite), compareLength traverses at most n elements to determine its result.

>>> compareLength [] 0
EQ
>>> compareLength [] 1
LT
>>> compareLength ['a'] 1
EQ
>>> compareLength ['a', 'b'] 1
GT
>>> compareLength [0..] 100
GT
>>> compareLength undefined (-1)
GT
>>> compareLength ('a' : undefined) 0
GT

Since: 4.21.0.0

inits1 :: [a] -> [NonEmpty a] Source #

The inits1 function returns all non-empty initial segments of the argument, shortest first.

Laziness

Expand

Note that inits1 has the following strictness property: inits1 (xs ++ _|_) = inits1 xs ++ _|_

In particular, inits1 _|_ = _|_

Examples

Expand

>>> inits1 "abc"
['a' :| "",'a' :| "b",'a' :| "bc"]

>>> inits1 []
[]

inits1 is productive on infinite lists:

>>> take 3 $ inits1 [1..]
[1 :| [],1 :| [2],1 :| [2,3]]

Since: 4.21.0.0

tails1 :: [a] -> [NonEmpty a] Source #

$\mathcal{O}(n)$. The tails1 function returns all non-empty final segments of the argument, longest first.

Laziness

Expand

Note that tails1 has the following strictness property: tails1 _|_ = _|_

>>> tails1 undefined
*** Exception: Prelude.undefined

>>> drop 1 (tails1 [undefined, 1, 2])
[1 :| [2],2 :| []]

Examples

Expand

>>> tails1 "abc"
['a' :| "bc",'b' :| "c",'c' :| ""]

>>> tails1 [1, 2, 3]
[1 :| [2,3],2 :| [3],3 :| []]

>>> tails1 []
[]

Since: 4.21.0.0

data List a #

The builtin list type, usually written in its non-prefix form [a].

In Haskell, lists are one of the most important data types as they are often used analogous to loops in imperative programming languages. These lists are singly linked, which makes it unsuited for operations that require $\mathcal{O}(1)$ access. Instead, lists are intended to be traversed.

Lists are constructed recursively using the right-associative cons-operator (:) :: a -> [a] -> [a], which prepends an element to a list, and the empty list [].

(1 : 2 : 3 : []) == (1 : (2 : (3 : []))) == [1, 2, 3]

Internally and in memory, all the above are represented like this, with arrows being pointers to locations in memory.

╭───┬───┬──╮   ╭───┬───┬──╮   ╭───┬───┬──╮   ╭────╮
│(:)│   │ ─┼──>│(:)│   │ ─┼──>│(:)│   │ ─┼──>│ [] │
╰───┴─┼─┴──╯   ╰───┴─┼─┴──╯   ╰───┴─┼─┴──╯   ╰────╯
      v              v              v
      1              2              3

As seen above, lists can also be constructed using list literals of the form [x_1, x_2, ..., x_n] which are syntactic sugar and, unless -XOverloadedLists is enabled, are translated into uses of (:) and []

Similarly, String literals of the form "I 💜 hs" are translated into Lists of characters, ['I', ' ', '💜', ' ', 'h', 's'].

Examples

Expand

>>> ['H', 'a', 's', 'k', 'e', 'l', 'l']
"Haskell"

>>> 1 : [4, 1, 5, 9]
[1,4,1,5,9]

>>> [] : [] : []
[[],[]]

Since: ghc-prim-0.10.0

Instances

Instances details

MonadFail []

Since: base-4.9.0.0

Instance details

Defined in Control.Monad.Fail

Methods

fail :: String -> [a] #

MonadFix []

Since: base-2.1

Instance details

Defined in Control.Monad.Fix

Methods

mfix :: (a -> [a]) -> [a] #

MonadZip []

Since: base-4.3.1.0

Instance details

Defined in Control.Monad.Zip

Methods

mzip :: [a] -> [b] -> [(a, b)] #

mzipWith :: (a -> b -> c) -> [a] -> [b] -> [c] #

munzip :: [(a, b)] -> ([a], [b]) #

Foldable []

Since: base-2.1

Instance details

Defined in Data.Foldable

Methods

fold :: Monoid m => [m] -> m #

foldMap :: Monoid m => (a -> m) -> [a] -> m #

foldMap' :: Monoid m => (a -> m) -> [a] -> m #

foldr :: (a -> b -> b) -> b -> [a] -> b #

foldr' :: (a -> b -> b) -> b -> [a] -> b #

foldl :: (b -> a -> b) -> b -> [a] -> b #

foldl' :: (b -> a -> b) -> b -> [a] -> b #

foldr1 :: (a -> a -> a) -> [a] -> a #

foldl1 :: (a -> a -> a) -> [a] -> a #

toList :: [a] -> [a] #

null :: [a] -> Bool #

length :: [a] -> Int #

elem :: Eq a => a -> [a] -> Bool #

maximum :: Ord a => [a] -> a #

minimum :: Ord a => [a] -> a #

sum :: Num a => [a] -> a #

product :: Num a => [a] -> a #

Eq1 []

Since: base-4.9.0.0

Instance details

Defined in Data.Functor.Classes

Methods

liftEq :: (a -> b -> Bool) -> [a] -> [b] -> Bool #

Ord1 []

Since: base-4.9.0.0

Instance details

Defined in Data.Functor.Classes

Methods

liftCompare :: (a -> b -> Ordering) -> [a] -> [b] -> Ordering #

Read1 []

Since: base-4.9.0.0

Instance details

Defined in Data.Functor.Classes

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS [a] #

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [[a]] #

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [a] #

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [[a]] #

Show1 []

Since: base-4.9.0.0

Instance details

Defined in Data.Functor.Classes

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> [a] -> ShowS #

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [[a]] -> ShowS #

Traversable []

Since: base-2.1

Instance details

Defined in Data.Traversable

Methods

traverse :: Applicative f => (a -> f b) -> [a] -> f [b] #

sequenceA :: Applicative f => [f a] -> f [a] #

mapM :: Monad m => (a -> m b) -> [a] -> m [b] #

sequence :: Monad m => [m a] -> m [a] #

Alternative []

Combines lists by concatenation, starting from the empty list.

Since: base-2.1

Instance details

Defined in GHC.Base

Methods

empty :: [a] #

(<|>) :: [a] -> [a] -> [a] #

some :: [a] -> [[a]] #

many :: [a] -> [[a]] #

Applicative []

Since: base-2.1

Instance details

Defined in GHC.Base

Methods

pure :: a -> [a] #

(<*>) :: [a -> b] -> [a] -> [b] #

liftA2 :: (a -> b -> c) -> [a] -> [b] -> [c] #

(*>) :: [a] -> [b] -> [b] #

(<*) :: [a] -> [b] -> [a] #

Functor []

Since: base-2.1

Instance details

Defined in GHC.Base

Methods

fmap :: (a -> b) -> [a] -> [b] #

(<$) :: a -> [b] -> [a] #

Monad []

Since: base-2.1

Instance details

Defined in GHC.Base

Methods

(>>=) :: [a] -> (a -> [b]) -> [b] #

(>>) :: [a] -> [b] -> [b] #

return :: a -> [a] #

MonadPlus []

Combines lists by concatenation, starting from the empty list.

Since: base-2.1

Instance details

Defined in GHC.Base

Methods

mzero :: [a] #

mplus :: [a] -> [a] -> [a] #

Generic1 []

Instance details

Defined in GHC.Generics

Associated Types

type Rep1 []

Since: base-4.6.0.0

Instance details

Defined in GHC.Generics

type Rep1 [] = D1 ('MetaData "List" "GHC.Types" "ghc-prim" 'False) (C1 ('MetaCons "[]" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons ":" ('InfixI 'RightAssociative 5) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 [])))

Methods

from1 :: [a] -> Rep1 [] a #

to1 :: Rep1 [] a -> [a] #

Data a => Data [a]

For historical reasons, the constructor name used for (:) is "(:)". In a derived instance, it would be ":".

Since: base-4.0.0.0

Instance details

Defined in Data.Data

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> [a] -> c [a] #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c [a] #

toConstr :: [a] -> Constr #

dataTypeOf :: [a] -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c [a]) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c [a]) #

gmapT :: (forall b. Data b => b -> b) -> [a] -> [a] #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> [a] -> r #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> [a] -> r #

gmapQ :: (forall d. Data d => d -> u) -> [a] -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> [a] -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> [a] -> m [a] #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> [a] -> m [a] #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> [a] -> m [a] #

a ~ Char => IsString [a]

(a ~ Char) context was introduced in 4.9.0.0

Since: base-2.1

Instance details

Defined in Data.String

Methods

fromString :: String -> [a] #

Monoid [a]

Since: base-2.1

Instance details

Defined in GHC.Base

Methods

mempty :: [a] #

mappend :: [a] -> [a] -> [a] #

mconcat :: [[a]] -> [a] #

Semigroup [a]

Since: base-4.9.0.0

Instance details

Defined in GHC.Base

Methods

(<>) :: [a] -> [a] -> [a] #

sconcat :: NonEmpty [a] -> [a] #

stimes :: Integral b => b -> [a] -> [a] #

Generic [a]

Instance details

Defined in GHC.Generics

Associated Types

type Rep [a]

Since: base-4.6.0.0

Instance details

Defined in GHC.Generics

type Rep [a] = D1 ('MetaData "List" "GHC.Types" "ghc-prim" 'False) (C1 ('MetaCons "[]" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons ":" ('InfixI 'RightAssociative 5) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [a])))

Methods

from :: [a] -> Rep [a] x #

to :: Rep [a] x -> [a] #

IsList [a]

Since: base-4.7.0.0

Instance details

Defined in GHC.IsList

Associated Types

type Item [a]
Instance details Defined in GHC.IsList type Item [a] = a

Methods

fromList :: [Item [a]] -> [a] #

fromListN :: Int -> [Item [a]] -> [a] #

toList :: [a] -> [Item [a]] #

Read a => Read [a]

Since: base-2.1

Instance details

Defined in GHC.Read

Methods

readsPrec :: Int -> ReadS [a] #

readList :: ReadS [[a]] #

readPrec :: ReadPrec [a] #

readListPrec :: ReadPrec [[a]] #

Show a => Show [a]

Since: base-2.1

Instance details

Defined in GHC.Show

Methods

showsPrec :: Int -> [a] -> ShowS #

show :: [a] -> String #

showList :: [[a]] -> ShowS #

IsChar c => PrintfArg [c]

Since: base-2.1

Instance details

Defined in Text.Printf

Methods

formatArg :: [c] -> FieldFormatter #

parseFormat :: [c] -> ModifierParser #

IsChar c => PrintfType [c]

Since: base-2.1

Instance details

Defined in Text.Printf

Methods

spr :: String -> [UPrintf] -> [c]

Eq a => Eq [a]

Instance details

Defined in GHC.Classes

Methods

(==) :: [a] -> [a] -> Bool #

(/=) :: [a] -> [a] -> Bool #

Ord a => Ord [a]

Instance details

Defined in GHC.Classes

Methods

compare :: [a] -> [a] -> Ordering #

(<) :: [a] -> [a] -> Bool #

(<=) :: [a] -> [a] -> Bool #

(>) :: [a] -> [a] -> Bool #

(>=) :: [a] -> [a] -> Bool #

max :: [a] -> [a] -> [a] #

min :: [a] -> [a] -> [a] #

type Rep1 []

Since: base-4.6.0.0

Instance details

Defined in GHC.Generics

type Rep1 [] = D1 ('MetaData "List" "GHC.Types" "ghc-prim" 'False) (C1 ('MetaCons "[]" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons ":" ('InfixI 'RightAssociative 5) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 [])))

type Rep [a]

Since: base-4.6.0.0

Instance details

Defined in GHC.Generics

type Rep [a] = D1 ('MetaData "List" "GHC.Types" "ghc-prim" 'False) (C1 ('MetaCons "[]" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons ":" ('InfixI 'RightAssociative 5) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [a])))

type Item [a]

Instance details

Defined in GHC.IsList

type Item [a] = a