Data.List.Linear

filter p xs returns a list with elements satisfying the predicate.

See mapMaybe if you do not want the Dupable constraint.

\mathcal{O}(1). Extract the first element of a list, which must be non-empty.

To disable the warning about partiality put {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of the file. To disable it throughout a package put the same options into ghc-options section of Cabal file. To disable it in GHCi put :set -Wno-x-partial -Wno-unrecognised-warning-flags into ~/.ghci config file. See also the migration guide.

Examples

>>> head [1, 2, 3]1

>>> head [1..]1

>>> head []*** Exception: Prelude.head: empty list

\mathcal{O}(1). Extract the elements after the head of a list, which must be non-empty.

To disable the warning about partiality put {-# OPTIONS_GHC -Wno-x-partial -Wno-unrecognised-warning-flags #-} at the top of the file. To disable it throughout a package put the same options into ghc-options section of Cabal file. To disable it in GHCi put :set -Wno-x-partial -Wno-unrecognised-warning-flags into ~/.ghci config file. See also the migration guide.

Examples

>>> tail [1, 2, 3][2,3]

>>> tail [1][]

>>> tail []*** Exception: Prelude.tail: empty list

\mathcal{O}(n). Extract the last element of a list, which must be finite and non-empty.

WARNING: This function is partial. Consider using unsnoc instead.

Examples

>>> last [1, 2, 3]3

>>> last [1..]* Hangs forever *

>>> last []*** Exception: Prelude.last: empty list

\mathcal{O}(n). Return all the elements of a list except the last one. The list must be non-empty.

WARNING: This function is partial. Consider using unsnoc instead.

Examples

>>> init [1, 2, 3][1,2]

>>> init [1][]

>>> init []*** Exception: Prelude.init: empty list

\mathcal{O}(n). lookup key assocs looks up a key in an association list. For the result to be Nothing, the list must be finite.

Examples

>>> lookup 2 []Nothing

>>> lookup 2 [(1, "first")]Nothing

>>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]Just "second"

Return the length of the given list alongside with the list itself.

Test whether the structure is empty. The default implementation is Left-associative and lazy in both the initial element and the accumulator. Thus optimised for structures where the first element can be accessed in constant time. Structures where this is not the case should have a non-default implementation.

Examples

Basic usage:

>>> null []True

>>> null [1]False

null is expected to terminate even for infinite structures. The default implementation terminates provided the structure is bounded on the left (there is a leftmost element).

>>> null [1..]False

NOTE: This does not short-circuit and always traverses the entire list to consume the rest of the elements.

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.

NOTE: This does not short-circuit and always traverses the entire list to consume the rest of the elements.

The find function takes a predicate and a structure and returns the leftmost element of the structure matching the predicate, or Nothing if there is no such element.

Examples

Basic usage:

>>> find (> 42) [0, 5..]Just 45

>>> find (> 12) [1..7]Nothing

The intersperse function takes an element and a list and intersperses that element between the elements of the list.

intercalate xs xss is equivalent to (concat (intersperse xs xss)). It inserts the list xs in between the lists in xss and concatenates the result.

The transpose function transposes the rows and columns of its argument.

Map each element of the structure to a monoid, and combine the results.

A variant of foldMap that is strict in the accumulator.

NOTE: This does not short-circuit, and always consumes the entire container.

NOTE: This does not short-circuit, and always consumes the entire container.

NOTE: This does not short-circuit, and always consumes the entire container.

NOTE: This does not short-circuit, and always consumes the entire container.

The sort function implements a stable sorting algorithm. It is a special case of sortBy, which allows the programmer to supply their own comparison function.

Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input.

The argument must be finite.

Examples

>>> sort [1,6,4,3,2,5][1,2,3,4,5,6]

>>> sort "haskell""aehklls"

>>> import Data.Semigroup(Arg(..))>>> sort [Arg ":)" 0, Arg ":D" 0, Arg ":)" 1, Arg ":3" 0, Arg ":D" 1][Arg ":)" 0,Arg ":)" 1,Arg ":3" 0,Arg ":D" 0,Arg ":D" 1]

Sort a list by comparing the results of a key function applied to each element. sortOn f is equivalent to sortBy (comparing f), but has the performance advantage of only evaluating f once for each element in the input list. This is called the decorate-sort-undecorate paradigm, or Schwartzian transform.

Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input.

The argument must be finite.

Examples

>>> sortOn fst [(2, "world"), (4, "!"), (1, "Hello")][(1,"Hello"),(2,"world"),(4,"!")]

>>> sortOn length ["jim", "creed", "pam", "michael", "dwight", "kevin"]["jim","pam","creed","kevin","dwight","michael"]

Performance notes

This function minimises the projections performed, by materialising the projections in an intermediate list.

For trivial projections, you should prefer using sortBy with comparing, for example:

>>> sortBy (comparing fst) [(3, 1), (2, 2), (1, 3)][(1,3),(2,2),(3,1)]

Or, for the exact same API as sortOn, you can use `sortBy . comparing`:

>>> (sortBy . comparing) fst [(3, 1), (2, 2), (1, 3)][(1,3),(2,2),(3,1)]

\mathcal{O}(n). The insert function takes an element and a list and inserts the element into the list at the first position where it is less than or equal to the next element. In particular, if the list is sorted before the call, the result will also be sorted. It is a special case of insertBy, which allows the programmer to supply their own comparison function.

Examples

>>> insert (-1) [1, 2, 3][-1,1,2,3]

>>> insert 'd' "abcefg""abcdefg"

>>> insert 4 [1, 2, 3, 5, 6, 7][1,2,3,4,5,6,7]

Same as zip, but returns the leftovers instead of consuming them.

Same as zipWith, but returns the leftovers instead of consuming them.