# Alternative f => [f a] -> f a +containers

The union of a list of maps.
> unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
> == fromList [(3, "b"), (5, "a"), (7, "C")]
> unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
> == fromList [(3, "B3"), (5, "A3"), (7, "C")]

The union of a list of maps, with a combining operation.
> unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
> == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]

*O(min(n,W))*. Delete the maximal key. Returns an empty map if the map is empty.
Note that this is a change of behaviour for consistency with Map versions prior to 0.5 threw an error if the IntMap was already empty.
*O(min(n,W))*. Delete the minimal key. Returns an empty map if the map is empty.
Note that this is a change of behaviour for consistency with Map versions prior to 0.5 threw an error if the IntMap was already empty.
*O(n)*. The reverse of a sequence.

*O(log n)*. Delete the maximal element. Returns an empty set if the set is empty.

*O(log n)*. Delete the minimal element. Returns an empty set if the set is empty.

*O(n)*. Filter all values that satisfy some predicate.
> filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
> filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty
> filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty

*O(log n)*. Update the value at the maximal key.
> updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
> updateMax (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

*O(min(n,W))*. Update the value at the maximal key.
> updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
> updateMax (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

*O(log n)*. Update the value at the minimal key.
> updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
> updateMin (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

*O(min(n,W))*. Update the value at the minimal key.
> updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
> updateMin (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

*O(n+m)*. Difference between two maps (based on keys).
> difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"

*O(n+m)*. The (left-biased) intersection of two maps (based on keys).
> intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"

*O(n+m)*. The (left-biased) union of two maps. It prefers the first map when duplicate keys are encountered, i.e. (union == unionWith const).
> union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
scanl1 is a variant of scanl that has no starting value argument:
> scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...]
scanr1 is a variant of scanr that has no starting value argument.
*O(n log n)*. sortBy sorts the specified Seq according to the specified comparator. The sort is stable. If stability is not required, unstableSortBy can be considerably faster, and in particular uses less memory.
*O(n log n)*. A generalization of unstableSort, unstableSortBy takes an arbitrary comparator and sorts the specified sequence. The sort is not stable. This algorithm is frequently faster and uses less memory than sortBy, and performs extremely well -- frequently twice as fast as sortBy -- when the sequence is already nearly sorted.
*O(i)* p xs</tt> returns the suffix remaining after takeWhileL p xs.
*O(n)*. The filter function takes a predicate p and a sequence xs and returns a sequence of those elements which satisfy the predicate.
*O(i)* applied to a predicate p and a sequence xs, returns the longest prefix (possibly empty) of xs of elements that satisfy p.

*O(i)* applied to a predicate p and a sequence xs, returns the longest suffix (possibly empty) of xs of elements that satisfy p.
takeWhileR p xs is equivalent to reverse (takeWhileL p (reverse xs)).
*O(1)*. Add an element to the left end of a sequence. Mnemonic: a triangle with the single element at the pointy end.

*O(log(min(i,n-i)))*. Elements of a sequence after the first i. If i is negative, drop i s yields the whole sequence. If the sequence contains fewer than i elements, the empty sequence is returned.
*O(log(min(i,n-i)))*. The first i elements of a sequence. If i is negative, take i s yields the empty sequence. If the sequence contains fewer than i elements, the whole sequence is returned.
*O(1)*. Add an element to the right end of a sequence. Mnemonic: a triangle with the single element at the pointy end.

*O(log(min(n1,n2)))*. Concatenate two sequences.

*O(n)*. Filter all elements that satisfy the predicate.

*O(log n)*. Delete the element at *index*, i.e. by its zero-based index in the sorted sequence of elements. If the *index* is out of range (less than zero, greater or equal to size of the set), error is called.
> deleteAt 0 (fromList [5,3]) == singleton 5
> deleteAt 1 (fromList [5,3]) == singleton 3
> deleteAt 2 (fromList [5,3]) Error: index out of range
> deleteAt (-1) (fromList [5,3]) Error: index out of range
*O(n)*. Filter all keys/values that satisfy some predicate.
> filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

*O(log n)*. Update the value at the maximal key.
> updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
> updateMaxWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

*O(min(n,W))*. Update the value at the maximal key.
> updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
> updateMaxWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

*O(log n)*. Update the value at the minimal key.
> updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
> updateMinWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

*O(min(n,W))*. Update the value at the minimal key.
> updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
> updateMinWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"

*O(n*min(n,W))*. mapKeys f s is the map obtained by applying f to each key of s.
The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the value at the greatest of the original keys is retained.
> mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
> mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c"
> mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
*O(n*min(n,W))*. mapKeysMonotonic f s == mapKeys f s, but works only when f is strictly monotonic. That is, for any values x and y, if x < y then f x < f y. *The precondition is not checked.* Semi-formally, we have:
> and [x < y ==> f x < f y | x <- ls, y <- ls]
> ==> mapKeysMonotonic f s == mapKeys f s
>
This means that f maps distinct original keys to distinct resulting keys. This function has slightly better performance than mapKeys.
> mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
*O(min(n,W))*. Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.
> delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
> delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
> delete 5 empty == empty

*O(n log n)*. sort sorts the specified Seq by the natural ordering of its elements. The sort is stable. If stability is not required, unstableSort can be considerably faster, and in particular uses less memory.
*O(n log n)*. unstableSort sorts the specified Seq by the natural ordering of its elements, but the sort is not stable. This algorithm is frequently faster and uses less memory than sort, and performs extremely well -- frequently twice as fast as sort -- when the sequence is already nearly sorted.
*O(n)*. Returns a sequence of all prefixes of this sequence, shortest first. For example,
> inits (fromList "abc") = fromList [fromList "", fromList "a", fromList "ab", fromList "abc"]
Evaluating the *i*th prefix takes *O(log(min(i, n-i)))*, but evaluating every prefix in the sequence takes *O(n)* due to sharing.

*O(n)*. Returns a sequence of all suffixes of this sequence, longest first. For example,
> tails (fromList "abc") = fromList [fromList "abc", fromList "bc", fromList "c", fromList ""]
Evaluating the *i*th suffix takes *O(log(min(i, n-i)))*, but evaluating every suffix in the sequence takes *O(n)* due to sharing.

*O(log n)*. The maximal element of a set.

*O(log n)*. The minimal element of a set.

label value

zero or more child trees

*O(n+m)*. Difference with a combining function.
> let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
> differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
> == singleton 3 "b:B"

*O(n+m)*. The union with a combining function.
> unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]

*O(log(min(i,n-i)))*. Update the element at the specified position. If the position is out of range, the original sequence is returned.

*O(log(min(i,n-i)))*. Replace the element at the specified position. If the position is out of range, the original sequence is returned.

*O(n*log n)*. mapKeysWith c f s is the map obtained by applying f to each key of s.
The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the associated values will be combined using c.
> mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab"
> mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"
*O(n*min(n,W))*. mapKeysWith c f s is the map obtained by applying f to each key of s.
The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the associated values will be combined using c.
> mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab"
> mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"
*O(min(n,W))*. Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.
> adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
> adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
> adjust ("new " ++) 7 empty == empty

*O(min(n,W))*. The expression (update f k map) updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.
> let f x = if x == "a" then Just "new a" else Nothing
> update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
> update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
> update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
*O(n+m)*. Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.
> let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
> differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
> == singleton 3 "3:b|B"
*O(n+m)*. The union with a combining function.
> let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
> unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]

Show more results