:: Ord a => [a] -> [a] is:exact -package:extra -package:lifted-base -package:ghc -package:errors -package:Cabal-syntax

Like nub, but has O(n log n) complexity instead of O(n^2). Code for ordNub and listUnion taken from Niklas Hambüchen's ordnub package.

A right-biased version of ordNub. Example:

>>> ordNub [1,2,1] :: [Int]
[1,2]

>>> ordNubRight [1,2,1] :: [Int]
[2,1]

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.

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

The nubOrd function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. By using a Set internally it has better asymptotics than the standard nub function.

Strictness

nubOrd is strict in the elements of the list.

Efficiency note

When applicable, it is almost always better to use nubInt or nubIntOn instead of this function, although it can be a little worse in certain pathological cases. For example, to nub a list of characters, use

nubIntOn fromEnum xs

A total variant of tail.

A total variant of init.

cycle ties a finite list into a circular one, or equivalently, the infinite repetition of the original list. It is the identity on infinite lists.

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

>>> take 20 $ cycle [42]
[42,42,42,42,42,42,42,42,42,42...

>>> take 20 $ cycle [2, 5, 7]
[2,5,7,2,5,7,2,5,7,2,5,7...

Extract the elements after the head of a list, which must be non-empty.

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

>>> tail [1]
[]

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

WARNING: This function is partial. You can use case-matching or uncons instead.

Return all the elements of a list except the last one. The list must be non-empty.

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

>>> init [1]
[]

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

WARNING: This function is partial. You can use reverse with case-matching or uncons instead.

reverse xs returns the elements of xs in reverse order. xs must be finite.

>>> reverse []
[]

>>> reverse [42]
[42]

>>> reverse [2,5,7]
[7,5,2]

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

Identical to tail, namely that fails on an empty list. Useful to avoid the x-partial warning introduced in GHC 9.8.

tailErr [] = error "Prelude.tail: empty list"
tailErr [1,2,3] = [2,3]

tailSafe [] = []
tailSafe [1,3,4] = [3,4]

Sort a vector.

The nub function which removes duplicate elements from a vector.

Sort a vector.

Removes duplicate elements from a list, keeping only the first occurrence. This is asymptotically faster than using nub from Data.List.

>>> ordNub [3,2,1,3,2,1]
[3,2,1]

List of elements of a structure, from left to right. If the entire list is intended to be reduced via a fold, just fold the structure directly bypassing the list.

Examples

Basic usage:

>>> toList Nothing
[]

>>> toList (Just 42)
[42]

>>> toList (Left "foo")
[]

>>> toList (Node (Leaf 5) 17 (Node Empty 12 (Leaf 8)))
[5,17,12,8]

For lists, toList is the identity:

>>> toList [1, 2, 3]
[1,2,3]

all nodes of a tree

O(n) Convert a vector to a list.

Take a parser that may consume input, and on failure, go back to where we started and fail as if we didn't consume input.

If x :: m a is a computation in some random monad, then interleave x works by splitting the generator, running x using one half, and using the other half as the final generator state of interleave x (replacing whatever the final generator state otherwise would have been). This means that computation needing random values which comes after interleave x does not necessarily depend on the computation of x. For example:

>>> evalRandIO $ snd <$> ((,) <$> undefined <*> getRandom)
*** Exception: Prelude.undefined
>>> evalRandIO $ snd <$> ((,) <$> interleave undefined <*> getRandom)
6192322188769041625

This can be used, for example, to allow random computations to run in parallel, or to create lazy infinite structures of random values. In the example below, the infinite tree randTree cannot be evaluated lazily: even though it is cut off at two levels deep by hew 2, the random value in the right subtree still depends on generation of all the random values in the (infinite) left subtree, even though they are ultimately unneeded. Inserting a call to interleave, as in randTreeI, solves the problem: the generator splits at each Node, so random values in the left and right subtrees are generated independently.

data Tree = Leaf | Node Int Tree Tree deriving Show

hew :: Int -> Tree -> Tree
hew 0 _    = Leaf
hew _ Leaf = Leaf
hew n (Node x l r) = Node x (hew (n-1) l) (hew (n-1) r)

randTree :: Rand StdGen Tree
randTree = Node <$> getRandom <*> randTree <*> randTree

randTreeI :: Rand StdGen Tree
randTreeI = interleave $ Node <$> getRandom <*> randTreeI <*> randTreeI

>>> hew 2 <$> evalRandIO randTree
Node 2168685089479838995 (Node (-1040559818952481847) Leaf Leaf) (Node ^CInterrupted.
>>> hew 2 <$> evalRandIO randTreeI
Node 8243316398511136358 (Node 4139784028141790719 Leaf Leaf) (Node 4473998613878251948 Leaf Leaf)