# Data.List

- Package
- purescript-lists
- Repository
- purescript/purescript-lists

This module defines a type of *strict* linked lists, and associated helper
functions and type class instances.

*Note*: Depending on your use-case, you may prefer to use
`Data.Sequence`

instead, which might give better performance for certain
use cases. This module is an improvement over `Data.Array`

when working with
immutable lists of data in a purely-functional setting, but does not have
good random-access performance.

### #toUnfoldable Source

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

Convert a list into any unfoldable structure.

Running time: `O(n)`

### #fromFoldable Source

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

Construct a list from a foldable structure.

Running time: `O(n)`

### #(..) Source

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

An infix synonym for `range`

.

### #some Source

`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 Source

`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 Source

`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 Source

`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.

### #(!!) Source

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

An infix synonym for `index`

.

### #elemLastIndex Source

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

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

### #findLastIndex Source

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

Find the last index for which a predicate holds.

### #stripPrefix Source

`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.

### #span Source

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

Split a list into two parts:

- the longest initial segment for which all elements satisfy the specified predicate
- 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 Source

`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 Source

`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 Source

`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 Source

`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)`

### #nubBy Source

`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 Source

`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 Source

`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)`

### #difference Source

`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)`

### #intersectBy Source

`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 Source

`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 Source

`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.

### #transpose Source

`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)
```

## Re-exports from **Data.**Foldable

### #intercalate Source

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

### #any Source

`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 Source

`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.

## Re-exports from **Data.**List.Types

### #List Source

`data List a`

#### Constructors

#### 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`

## Re-exports from **Data.**Traversable

### #scanr Source

`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 Source

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