Data.List
- Package
- 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.
#mapWithIndex Source
mapWithIndex :: forall a b. (Int -> a -> b) -> List a -> List b
Apply a function to each element and its index in a list starting at 0.
Deprecated. Use Data.FunctorWithIndex instead.
#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. Ord a => (a -> a -> Boolean) -> List a -> List (NonEmptyList a)
Group equal elements of a list into lists, using the specified equivalence relation to determine equality.
For example,
groupAllBy (\a b -> odd a && odd b) (1 : 3 : 2 : 4 : 3 : 3 : Nil) ==
(NonEmptyList (NonEmpty 1 Nil)) : (NonEmptyList (NonEmpty 2 Nil)) : (NonEmptyList (NonEmpty 3 (3 : 3 : Nil))) : (NonEmptyList (NonEmpty 4 Nil)) : Nil
#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
MonadZero 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]