Data.List

toUnfoldable :: forall f. Unfoldable f => List ~> f

Convert a list into any unfoldable structure.

Running time: O(n)

fromFoldable :: forall f. Foldable f => f ~> List

Construct a list from a foldable structure.

Running time: O(n)

singleton :: forall a. a -> List a

Create a list with a single element.

Running time: O(1)

Operator alias for Data.List.range (non-associative / precedence 8)

An infix synonym for range.

range :: Int -> Int -> List Int

Create a list containing a range of integers, including both endpoints.

some :: forall f a. Alternative f => Lazy (f (List a)) => f a -> f (List a)

Attempt a computation multiple times, requiring at least one success.

The Lazy constraint is used to generate the result lazily, to ensure termination.

someRec :: forall f a. MonadRec f => Alternative f => f a -> f (List a)

A stack-safe version of some, at the cost of a MonadRec constraint.

many :: forall f a. Alternative f => Lazy (f (List a)) => f a -> f (List a)

Attempt a computation multiple times, returning as many successful results as possible (possibly zero).

The Lazy constraint is used to generate the result lazily, to ensure termination.

manyRec :: forall f a. MonadRec f => Alternative f => f a -> f (List a)

A stack-safe version of many, at the cost of a MonadRec constraint.

null :: forall a. List a -> Boolean

Test whether a list is empty.

Running time: O(1)

length :: forall a. List a -> Int

Get the length of a list

Running time: O(n)

snoc :: forall a. List a -> a -> List a

Append an element to the end of a list, creating a new list.

Running time: O(n)

insert :: forall a. Ord a => a -> List a -> List a

Insert an element into a sorted list.

Running time: O(n)

insertBy :: forall a. (a -> a -> Ordering) -> a -> List a -> List a

Insert an element into a sorted list, using the specified function to determine the ordering of elements.

Running time: O(n)

head :: List ~> Maybe

Get the first element in a list, or Nothing if the list is empty.

Running time: O(1).

last :: List ~> Maybe

Get the last element in a list, or Nothing if the list is empty.

Running time: O(n).

tail :: forall a. List a -> Maybe (List a)

Get all but the first element of a list, or Nothing if the list is empty.

Running time: O(1)

init :: forall a. List a -> Maybe (List a)

Get all but the last element of a list, or Nothing if the list is empty.

Running time: O(n)

uncons :: forall a. List a -> Maybe { head :: a, tail :: List a }

Break a list into its first element, and the remaining elements, or Nothing if the list is empty.

Running time: O(1)

unsnoc :: forall a. List a -> Maybe { init :: List a, last :: a }

Break a list into its last element, and the preceding elements, or Nothing if the list is empty.

Running time: O(n)

Operator alias for Data.List.index (left-associative / precedence 8)

An infix synonym for index.

index :: forall a. List a -> Int -> Maybe a

Get the element at the specified index, or Nothing if the index is out-of-bounds.

Running time: O(n) where n is the required index.

elemIndex :: forall a. Eq a => a -> List a -> Maybe Int

Find the index of the first element equal to the specified element.

elemLastIndex :: forall a. Eq a => a -> List a -> Maybe Int

Find the index of the last element equal to the specified element.

findIndex :: forall a. (a -> Boolean) -> List a -> Maybe Int

Find the first index for which a predicate holds.

findLastIndex :: forall a. (a -> Boolean) -> List a -> Maybe Int

Find the last index for which a predicate holds.

insertAt :: forall a. Int -> a -> List a -> Maybe (List a)

Insert an element into a list at the specified index, returning a new list or Nothing if the index is out-of-bounds.

Running time: O(n)

deleteAt :: forall a. Int -> List a -> Maybe (List a)

Delete an element from a list at the specified index, returning a new list or Nothing if the index is out-of-bounds.

Running time: O(n)

updateAt :: forall a. Int -> a -> List a -> Maybe (List a)

Update the element at the specified index, returning a new list or Nothing if the index is out-of-bounds.

Running time: O(n)

modifyAt :: forall a. Int -> (a -> a) -> List a -> Maybe (List a)

Update the element at the specified index by applying a function to the current value, returning a new list or Nothing if the index is out-of-bounds.

Running time: O(n)

alterAt :: forall a. Int -> (a -> Maybe a) -> List a -> Maybe (List a)

Update or delete the element at the specified index by applying a function to the current value, returning a new list or Nothing if the index is out-of-bounds.

Running time: O(n)

reverse :: List ~> List

Reverse a list.

Running time: O(n)

concat :: forall a. List (List a) -> List a

Flatten a list of lists.

Running time: O(n), where n is the total number of elements.

concatMap :: forall a b. (a -> List b) -> List a -> List b

Apply a function to each element in a list, and flatten the results into a single, new list.

Running time: O(n), where n is the total number of elements.

filter :: forall a. (a -> Boolean) -> List a -> List a

Filter a list, keeping the elements which satisfy a predicate function.

Running time: O(n)

filterM :: forall a m. Monad m => (a -> m Boolean) -> List a -> m (List a)

Filter where the predicate returns a monadic Boolean.

For example:

powerSet :: forall a. [a] -> [[a]]
powerSet = filterM (const [true, false])

mapMaybe :: forall a b. (a -> Maybe b) -> List a -> List b

Apply a function to each element in a list, keeping only the results which contain a value.

Running time: O(n)

catMaybes :: forall a. List (Maybe a) -> List a

Filter a list of optional values, keeping only the elements which contain a value.

sort :: forall a. Ord a => List a -> List a

Sort the elements of an list in increasing order.

sortBy :: forall a. (a -> a -> Ordering) -> List a -> List a

Sort the elements of a list in increasing order, where elements are compared using the specified ordering.

newtype Pattern a

A newtype used in cases where there is a list to be matched.

Constructors

• Pattern (List a)

Instances

• (Eq a) => Eq (Pattern a)
• (Ord a) => Ord (Pattern a)
• Newtype (Pattern a) _
• (Show a) => Show (Pattern a)

stripPrefix :: forall a. Eq a => Pattern a -> List a -> Maybe (List a)

If the list starts with the given prefix, return the portion of the list left after removing it, as a Just value. Otherwise, return Nothing.

• stripPrefix (Pattern (1:Nil)) (1:2:Nil) == Just (2:Nil)
• stripPrefix (Pattern Nil) (1:Nil) == Just (1:Nil)
• stripPrefix (Pattern (2:Nil)) (1:Nil) == Nothing

Running time: O(n) where n is the number of elements to strip.

slice :: Int -> Int -> List ~> List

Extract a sublist by a start and end index.

take :: forall a. Int -> List a -> List a

Take the specified number of elements from the front of a list.

Running time: O(n) where n is the number of elements to take.

takeEnd :: forall a. Int -> List a -> List a

Take the specified number of elements from the end of a list.

Running time: O(2n - m) where n is the number of elements in list and m is number of elements to take.

takeWhile :: forall a. (a -> Boolean) -> List a -> List a

Take those elements from the front of a list which match a predicate.

Running time (worst case): O(n)

drop :: forall a. Int -> List a -> List a

Drop the specified number of elements from the front of a list.

Running time: O(n) where n is the number of elements to drop.

dropEnd :: forall a. Int -> List a -> List a

Drop the specified number of elements from the end of a list.

Running time: O(2n - m) where n is the number of elements in list and m is number of elements to drop.

dropWhile :: forall a. (a -> Boolean) -> List a -> List a

Drop those elements from the front of a list which match a predicate.

Running time (worst case): O(n)

span :: forall a. (a -> Boolean) -> List a -> { init :: List a, rest :: List a }

Split a list into two parts:

1. the longest initial segment for which all elements satisfy the specified predicate
2. the remaining elements

For example,

span (\n -> n % 2 == 1) (1 : 3 : 2 : 4 : 5 : Nil) == { init: (1 : 3 : Nil), rest: (2 : 4 : 5 : Nil) }

Running time: O(n)

group :: forall a. Eq a => List a -> List (NonEmptyList a)

Group equal, consecutive elements of a list into lists.

For example,

group (1 : 1 : 2 : 2 : 1 : Nil) ==
  (NonEmptyList (NonEmpty 1 (1 : Nil))) : (NonEmptyList (NonEmpty 2 (2 : Nil))) : (NonEmptyList (NonEmpty 1 Nil)) : Nil

Running time: O(n)

groupAll :: forall a. Ord a => List a -> List (NonEmptyList a)

Group equal elements of a list into lists.

For example,

groupAll (1 : 1 : 2 : 2 : 1 : Nil) ==
  (NonEmptyList (NonEmpty 1 (1 : 1 : Nil))) : (NonEmptyList (NonEmpty 2 (2 : Nil))) : Nil

groupBy :: forall a. (a -> a -> Boolean) -> List a -> List (NonEmptyList a)

Group equal, consecutive elements of a list into lists, using the specified equivalence relation to determine equality.

For example,

groupBy (\a b -> odd a && odd b) (1 : 3 : 2 : 4 : 3 : 3 : Nil) ==
  (NonEmptyList (NonEmpty 1 (3 : Nil))) : (NonEmptyList (NonEmpty 2 Nil)) : (NonEmptyList (NonEmpty 4 Nil)) : (NonEmptyList (NonEmpty 3 (3 : Nil))) : Nil

Running time: O(n)

groupAllBy :: forall a. (a -> a -> Ordering) -> List a -> List (NonEmptyList a)

Sort, then group equal elements of a list into lists, using the provided comparison function.

groupAllBy (compare `on` (_ `div` 10)) (32 : 31 : 21 : 22 : 11 : 33 : Nil) ==
  NonEmptyList (11 :| Nil) : NonEmptyList (21 :| 22 : Nil) : NonEmptyList (32 :| 31 : 33) : Nil

Running time: O(n log n)

partition :: forall a. (a -> Boolean) -> List a -> { no :: List a, yes :: List a }

Returns a lists of elements which do and do not satisfy a predicate.

Running time: O(n)

nub :: forall a. Ord a => List a -> List a

Remove duplicate elements from a list. Keeps the first occurrence of each element in the input list, in the same order they appear in the input list.

nub 1:2:1:3:3:Nil == 1:2:3:Nil

Running time: O(n log n)

nubBy :: forall a. (a -> a -> Ordering) -> List a -> List a

Remove duplicate elements from a list based on the provided comparison function. Keeps the first occurrence of each element in the input list, in the same order they appear in the input list.

nubBy (compare `on` Array.length) ([1]:[2]:[3,4]:Nil) == [1]:[3,4]:Nil

Running time: O(n log n)

nubEq :: forall a. Eq a => List a -> List a

Remove duplicate elements from a list. Keeps the first occurrence of each element in the input list, in the same order they appear in the input list. This less efficient version of nub only requires an Eq instance.

nubEq 1:2:1:3:3:Nil == 1:2:3:Nil

Running time: O(n^2)

nubByEq :: forall a. (a -> a -> Boolean) -> List a -> List a

Remove duplicate elements from a list, using the provided equivalence function. Keeps the first occurrence of each element in the input list, in the same order they appear in the input list. This less efficient version of nubBy only requires an equivalence function, rather than an ordering function.

mod3eq = eq `on` \n -> mod n 3
nubByEq mod3eq 1:3:4:5:6:Nil == 1:3:5:Nil

Running time: O(n^2)

union :: forall a. Eq a => List a -> List a -> List a

Calculate the union of two lists.

Running time: O(n^2)

unionBy :: forall a. (a -> a -> Boolean) -> List a -> List a -> List a

Calculate the union of two lists, using the specified function to determine equality of elements.

Running time: O(n^2)

delete :: forall a. Eq a => a -> List a -> List a

Delete the first occurrence of an element from a list.

Running time: O(n)

deleteBy :: forall a. (a -> a -> Boolean) -> a -> List a -> List a

Delete the first occurrence of an element from a list, using the specified function to determine equality of elements.

Running time: O(n)

Operator alias for Data.List.difference (non-associative / precedence 5)

difference :: forall a. Eq a => List a -> List a -> List a

Delete the first occurrence of each element in the second list from the first list.

Running time: O(n^2)

intersect :: forall a. Eq a => List a -> List a -> List a

Calculate the intersection of two lists.

Running time: O(n^2)

intersectBy :: forall a. (a -> a -> Boolean) -> List a -> List a -> List a

Calculate the intersection of two lists, using the specified function to determine equality of elements.

Running time: O(n^2)

zipWith :: forall a b c. (a -> b -> c) -> List a -> List b -> List c

Apply a function to pairs of elements at the same positions in two lists, collecting the results in a new list.

If one list is longer, elements will be discarded from the longer list.

For example

zipWith (*) (1 : 2 : 3 : Nil) (4 : 5 : 6 : 7 Nil) == 4 : 10 : 18 : Nil

Running time: O(min(m, n))

zipWithA :: forall m a b c. Applicative m => (a -> b -> m c) -> List a -> List b -> m (List c)

A generalization of zipWith which accumulates results in some Applicative functor.

zip :: forall a b. List a -> List b -> List (Tuple a b)

Collect pairs of elements at the same positions in two lists.

Running time: O(min(m, n))

unzip :: forall a b. List (Tuple a b) -> Tuple (List a) (List b)

Transforms a list of pairs into a list of first components and a list of second components.

transpose :: forall a. List (List a) -> List (List a)

The 'transpose' function transposes the rows and columns of its argument. For example,

transpose ((1:2:3:Nil) : (4:5:6:Nil) : Nil) ==
  ((1:4:Nil) : (2:5:Nil) : (3:6:Nil) : Nil)

If some of the rows are shorter than the following rows, their elements are skipped:

transpose ((10:11:Nil) : (20:Nil) : Nil : (30:31:32:Nil) : Nil) ==
  ((10:20:30:Nil) : (11:31:Nil) : (32:Nil) : Nil)

foldM :: forall m a b. Monad m => (b -> a -> m b) -> b -> List a -> m b

Perform a fold using a monadic step function.

foldMap :: forall f a m. Foldable f => Monoid m => (a -> m) -> f a -> m

foldl :: forall f a b. Foldable f => (b -> a -> b) -> b -> f a -> b

foldr :: forall f a b. Foldable f => (a -> b -> b) -> b -> f a -> b

notElem :: forall a f. Foldable f => Eq a => a -> f a -> Boolean

Test whether a value is not an element of a data structure.

intercalate :: forall f m. Foldable f => Monoid m => m -> f m -> m

Fold a data structure, accumulating values in some Monoid, combining adjacent elements using the specified separator.

For example:

> intercalate ", " ["Lorem", "ipsum", "dolor"]
= "Lorem, ipsum, dolor"

> intercalate "*" ["a", "b", "c"]
= "a*b*c"

> intercalate [1] [[2, 3], [4, 5], [6, 7]]
= [2, 3, 1, 4, 5, 1, 6, 7]

fold :: forall f m. Foldable f => Monoid m => f m -> m

Fold a data structure, accumulating values in some Monoid.

findMap :: forall a b f. Foldable f => (a -> Maybe b) -> f a -> Maybe b

Try to find an element in a data structure which satisfies a predicate mapping.

find :: forall a f. Foldable f => (a -> Boolean) -> f a -> Maybe a

Try to find an element in a data structure which satisfies a predicate.

elem :: forall a f. Foldable f => Eq a => a -> f a -> Boolean

Test whether a value is an element of a data structure.

any :: forall a b f. Foldable f => HeytingAlgebra b => (a -> b) -> f a -> b

any f is the same as or <<< map f; map a function over the structure, and then get the disjunction of the results.

all :: forall a b f. Foldable f => HeytingAlgebra b => (a -> b) -> f a -> b

all f is the same as and <<< map f; map a function over the structure, and then get the conjunction of the results.

data List a

Constructors

• Nil
• Cons a (List a)

Instances

• (Show a) => Show (List a)
• (Eq a) => Eq (List a)
• Eq1 List
• (Ord a) => Ord (List a)
• Ord1 List
• Semigroup (List a)
• Monoid (List a)
• Functor List
• FunctorWithIndex Int List
• Foldable List
• FoldableWithIndex Int List
• Unfoldable1 List
• Unfoldable List
• Traversable List
• TraversableWithIndex Int List
• Apply List
• Applicative List
• Bind List
• Monad List
• Alt List
• Plus List
• Alternative List
• MonadPlus List
• Extend List

Operator alias for Data.List.Types.Cons (right-associative / precedence 6)

scanr :: forall a b f. Traversable f => (a -> b -> b) -> b -> f a -> f b

Fold a data structure from the right, keeping all intermediate results instead of only the final result. Note that the initial value does not appear in the result (unlike Haskell's Prelude.scanr).

scanr (+) 0 [1,2,3] = [6,5,3]
scanr (flip (-)) 10 [1,2,3] = [4,5,7]

scanl :: forall a b f. Traversable f => (b -> a -> b) -> b -> f a -> f b

Fold a data structure from the left, keeping all intermediate results instead of only the final result. Note that the initial value does not appear in the result (unlike Haskell's Prelude.scanl).

scanl (+) 0  [1,2,3] = [1,3,6]
scanl (-) 10 [1,2,3] = [9,7,4]