Data.List.Linear

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

\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]

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}(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}(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). 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). 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"

\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

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