:: [a] -> [[a]]

The subsequences function returns the list of all subsequences of the argument.

Laziness

subsequences does not look ahead unless it must:

>>> take 1 (subsequences undefined)
[[]]

>>> take 2 (subsequences ('a' : undefined))
["","a"]

Examples

>>> subsequences "abc"
["","a","b","ab","c","ac","bc","abc"]

This function is productive on infinite inputs:

>>> take 8 $ subsequences ['a'..]
["","a","b","ab","c","ac","bc","abc"]

The permutations function returns the list of all permutations of the argument. Note that the order of permutations is not lexicographic. It satisfies the following property:

map (take n) (take (product [1..n]) (permutations ([1..n] ++ undefined))) == permutations [1..n]

Laziness

The permutations function is maximally lazy: for each n, the value of permutations xs starts with those permutations that permute take n xs and keep drop n xs.

Examples

>>> permutations "abc"
["abc","bac","cba","bca","cab","acb"]

>>> permutations [1, 2]
[[1,2],[2,1]]

>>> permutations []
[[]]

This function is productive on infinite inputs:

>>> take 6 $ map (take 3) $ permutations ['a'..]
["abc","bac","cba","bca","cab","acb"]

The inits function returns all initial segments of the argument, shortest first. inits is semantically equivalent to map reverse . scanl (flip (:)) [], but under the hood uses a queue to amortize costs of reverse.

Laziness

Note that inits has the following strictness property: inits (xs ++ _|_) = inits xs ++ _|_ In particular, inits _|_ = [] : _|_

Examples

>>> inits "abc"
["","a","ab","abc"]

>>> inits []
[[]]

inits is productive on infinite lists:

>>> take 5 $ inits [1..]
[[],[1],[1,2],[1,2,3],[1,2,3,4]]

The tails function returns all final segments of the argument, longest first.

Laziness

Note that tails has the following strictness property: tails _|_ = _|_ : _|_

>>> tails undefined
[*** Exception: Prelude.undefined

>>> drop 1 (tails [undefined, 1, 2])
[[1, 2], [2], []]

Examples

>>> tails "abc"
["abc","bc","c",""]

>>> tails [1, 2, 3]
[[1,2,3],[2,3],[3],[]]

>>> tails []
[[]]

Shrink a list by edging towards the empty list.

>>> list [1,2,3]
[[],[2,3],[1,3],[1,2]]

>>> list "abcd"
["","cd","ab","bcd","acd","abd","abc"]

Note we always try the empty list first, as that is the optimal shrink.

Split a list into lists that are small enough to have a corresponding tuple arity. The sub-lists of the result all have length <= mAX_TUPLE_SIZE But there may be more than mAX_TUPLE_SIZE sub-lists

This function is lazier than the one suggested in the Haskell 98 report. It is inits undefined = [] : undefined, in contrast to Data.List.inits undefined = undefined.

This function is lazier than the one suggested in the Haskell 98 report. It is tails undefined = ([] : undefined) : undefined, in contrast to Data.List.tails undefined = undefined.

The subsequences function returns the list of all subsequences of the argument.

>>> subsequences "abc"
["","a","b","ab","c","ac","bc","abc"]

The permutations function returns the list of all permutations of the argument.

>>> permutations "abc"
["abc","bac","cba","bca","cab","acb"]

The inits function returns all initial segments of the argument, shortest first. For example,

>>> inits "abc"
["","a","ab","abc"]

Note that inits has the following strictness property: inits (xs ++ _|_) = inits xs ++ _|_ In particular, inits _|_ = [] : _|_

The tails function returns all final segments of the argument, longest first. For example,

>>> tails "abc"
["abc","bc","c",""]

Note that tails has the following strictness property: tails _|_ = _|_ : _|_

List.inits is defined by inits = foldr (x ys -> [] : map (x:) ys) [[]] This is too strict for our application.

Prelude> List.inits (0:1:2:undefined)
[[],[0],[0,1]*** Exception: Prelude.undefined

The following routine is more lazy than inits and even lazier than inits from utility-ht package, but it is restricted to infinite lists. This degree of laziness is needed for sqrtFP.

Prelude> lazyInits (0:1:2:undefined)
[[],[0],[0,1],[0,1,2],[0,1,2,*** Exception: Prelude.undefined

The inits function returns all initial segments of the argument, shortest first. For example,

>>> inits "abc"
["","a","ab","abc"]

Note that inits has the following strictness property: inits (xs ++ _|_) = inits xs ++ _|_ In particular, inits _|_ = [] : _|_ inits is semantically equivalent to map reverse . scanl (flip (:)) [], but under the hood uses a queue to amortize costs of reverse.

The subsequences function returns the list of all subsequences of the argument.

>>> subsequences "abc"
["","a","b","ab","c","ac","bc","abc"]

This function is productive on infinite inputs:

>>> take 8 $ subsequences ['a'..]
["","a","b","ab","c","ac","bc","abc"]

The permutations function returns the list of all permutations of the argument.

>>> permutations "abc"
["abc","bac","cba","bca","cab","acb"]

The permutations function is maximally lazy: for each n, the value of permutations xs starts with those permutations that permute take n xs and keep drop n xs. This function is productive on infinite inputs:

>>> take 6 $ map (take 3) $ permutations ['a'..]
["abc","bac","cba","bca","cab","acb"]

Note that the order of permutations is not lexicographic. It satisfies the following property:

map (take n) (take (product [1..n]) (permutations ([1..n] ++ undefined))) == permutations [1..n]

Takes a list of values xs and transform it into tiers on which each tier is occupied by a single element from xs.

toTiers [x, y, z, ...]  =  [[x], [y], [z], ...]

To convert back to a list, just concat.

Chunk in groups of 4. (This function must be in some standard library, where?)

Return all combinations of a sequence of values.

Generate list of all permutations of the input list. The list is sorted lexicographically.

>>> Comb.permute "abc"
["abc","acb","bac","bca","cab","cba"]

>>> Comb.permute "aabc"
["aabc","aacb","abac","abca","acab","acba","aabc","aacb","abac","abca","acab","acba","baac","baca","baac","baca","bcaa","bcaa","caab","caba","caab","caba","cbaa","cbaa"]

QC.forAll (take 6 <$> QC.arbitrary :: QC.Gen [Int]) $ \xs -> allEqual $ map (\p -> sort (p xs)) $ Comb.permute : Comb.permuteFast : Comb.permuteShare : []

Generate list of all permutations of the input list. It is not lexicographically sorted. It is slightly faster and consumes less memory than the lexicographical ordering permute.