# Alternative f => [f a] -> f a -fgl +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"
Show more results