-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Assorted concrete container types -- -- This package contains efficient general-purpose implementations of -- various basic immutable container types. The declared cost of each -- operation is either worst-case or amortized, but remains valid even if -- structures are shared. @package containers @version 0.1.0.1 -- | General purpose finite sequences. Apart from being finite and having -- strict operations, sequences also differ from lists in supporting a -- wider variety of operations efficiently. -- -- An amortized running time is given for each operation, with n -- referring to the length of the sequence and i being the -- integral index used by some operations. These bounds hold even in a -- persistent (shared) setting. -- -- The implementation uses 2-3 finger trees annotated with sizes, as -- described in section 4.2 of -- --
-- import Data.Set (Set) -- import qualified Data.Set as Set ---- -- The implementation of Set is based on size balanced -- binary trees (or trees of bounded balance) as described by: -- --
-- import qualified Data.Set as S -- data AB = A | B deriving Show -- instance Ord AB where compare _ _ = EQ -- instance Eq AB where _ == _ = True -- main = print (S.singleton A `S.intersection` S.singleton B, -- S.singleton B `S.intersection` S.singleton A) ---- -- prints (fromList [A],fromList [B]). intersection :: (Ord a) => Set a -> Set a -> Set a -- | O(n). Filter all elements that satisfy the predicate. filter :: (Ord a) => (a -> Bool) -> Set a -> Set a -- | O(n). Partition the set into two sets, one with all elements -- that satisfy the predicate and one with all elements that don't -- satisfy the predicate. See also split. partition :: (Ord a) => (a -> Bool) -> Set a -> (Set a, Set a) -- | O(log n). The expression (split x set) is a -- pair (set1,set2) where all elements in set1 are -- lower than x and all elements in set2 larger than -- x. x is not found in neither set1 nor -- set2. split :: (Ord a) => a -> Set a -> (Set a, Set a) -- | O(log n). Performs a split but also returns whether the -- pivot element was found in the original set. splitMember :: (Ord a) => a -> Set a -> (Set a, Bool, Set a) -- | O(n*log n). map f s is the set obtained by -- applying f to each element of s. -- -- It's worth noting that the size of the result may be smaller if, for -- some (x,y), x /= y && f x == f y map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b -- | O(n). The -- -- mapMonotonic f s == map f s, but works only -- when f is monotonic. The precondition is not checked. -- Semi-formally, we have: -- --
-- and [x < y ==> f x < f y | x <- ls, y <- ls] -- ==> mapMonotonic f s == map f s -- where ls = toList s --mapMonotonic :: (a -> b) -> Set a -> Set b -- | O(n). Fold over the elements of a set in an unspecified order. fold :: (a -> b -> b) -> b -> Set a -> b -- | O(log n). The minimal element of a set. findMin :: Set a -> a -- | O(log n). The maximal element of a set. findMax :: Set a -> a -- | O(log n). Delete the minimal element. deleteMin :: Set a -> Set a -- | O(log n). Delete the maximal element. deleteMax :: Set a -> Set a -- | O(log n). Delete and find the minimal element. -- --
-- deleteFindMin set = (findMin set, deleteMin set) --deleteFindMin :: Set a -> (a, Set a) -- | O(log n). Delete and find the maximal element. -- --
-- deleteFindMax set = (findMax set, deleteMax set) --deleteFindMax :: Set a -> (a, Set a) -- | O(log n). Retrieves the maximal key of the set, and the set -- stripped from that element fails (in the monad) when passed -- an empty set. maxView :: (Monad m) => Set a -> m (a, Set a) -- | O(log n). Retrieves the minimal key of the set, and the set -- stripped from that element fails (in the monad) when passed -- an empty set. minView :: (Monad m) => Set a -> m (a, Set a) -- | O(n). The elements of a set. elems :: Set a -> [a] -- | O(n). Convert the set to a list of elements. toList :: Set a -> [a] -- | O(n*log n). Create a set from a list of elements. fromList :: (Ord a) => [a] -> Set a -- | O(n). Convert the set to an ascending list of elements. toAscList :: Set a -> [a] -- | O(n). Build a set from an ascending list in linear time. The -- precondition (input list is ascending) is not checked. fromAscList :: (Eq a) => [a] -> Set a -- | O(n). Build a set from an ascending list of distinct elements -- in linear time. The precondition (input list is strictly ascending) -- is not checked. fromDistinctAscList :: [a] -> Set a -- | O(n). Show the tree that implements the set. The tree is shown -- in a compressed, hanging format. showTree :: (Show a) => Set a -> String -- | O(n). The expression (showTreeWith hang wide map) -- shows the tree that implements the set. If hang is -- True, a hanging tree is shown otherwise a rotated tree -- is shown. If wide is True, an extra wide version is -- shown. -- --
-- Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5] -- 4 -- +--2 -- | +--1 -- | +--3 -- +--5 -- -- Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5] -- 4 -- | -- +--2 -- | | -- | +--1 -- | | -- | +--3 -- | -- +--5 -- -- Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5] -- +--5 -- | -- 4 -- | -- | +--3 -- | | -- +--2 -- | -- +--1 --showTreeWith :: (Show a) => Bool -> Bool -> Set a -> String -- | O(n). Test if the internal set structure is valid. valid :: (Ord a) => Set a -> Bool instance Typeable1 Set instance (Read a, Ord a) => Read (Set a) instance (Show a) => Show (Set a) instance (Ord a) => Ord (Set a) instance (Eq a) => Eq (Set a) instance (Data a, Ord a) => Data (Set a) instance Foldable Set instance (Ord a) => Monoid (Set a) -- | An efficient implementation of maps from keys to values -- (dictionaries). -- -- Since many function names (but not the type name) clash with -- Prelude names, this module is usually imported -- qualified, e.g. -- --
-- import Data.Map (Map) -- import qualified Data.Map as Map ---- -- The implementation of Map is based on size balanced -- binary trees (or trees of bounded balance) as described by: -- --
-- and [x < y ==> f x < f y | x <- ls, y <- ls] -- ==> mapKeysMonotonic f s == mapKeys f s -- where ls = keys s --mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a -- | O(n). Fold the values in the map, such that fold f z -- == Prelude.foldr f z . elems. For example, -- --
-- elems map = fold (:) [] map --fold :: (a -> b -> b) -> b -> Map k a -> b -- | O(n). Fold the keys and values in the map, such that -- foldWithKey f z == Prelude.foldr (uncurry -- f) z . toAscList. For example, -- --
-- keys map = foldWithKey (\k x ks -> k:ks) [] map --foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b -- | O(n). Return all elements of the map in the ascending order of -- their keys. elems :: Map k a -> [a] -- | O(n). Return all keys of the map in ascending order. keys :: Map k a -> [k] -- | O(n). The set of all keys of the map. keysSet :: Map k a -> Set k -- | O(n). Return all key/value pairs in the map in ascending key -- order. assocs :: Map k a -> [(k, a)] -- | O(n). Convert to a list of key/value pairs. toList :: Map k a -> [(k, a)] -- | O(n*log n). Build a map from a list of key/value pairs. See -- also fromAscList. fromList :: (Ord k) => [(k, a)] -> Map k a -- | O(n*log n). Build a map from a list of key/value pairs with a -- combining function. See also fromAscListWith. fromListWith :: (Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a -- | O(n*log n). Build a map from a list of key/value pairs with a -- combining function. See also fromAscListWithKey. fromListWithKey :: (Ord k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a -- | O(n). Convert to an ascending list. toAscList :: Map k a -> [(k, a)] -- | O(n). Build a map from an ascending list in linear time. The -- precondition (input list is ascending) is not checked. fromAscList :: (Eq k) => [(k, a)] -> Map k a -- | O(n). Build a map from an ascending list in linear time with a -- combining function for equal keys. The precondition (input list is -- ascending) is not checked. fromAscListWith :: (Eq k) => (a -> a -> a) -> [(k, a)] -> Map k a -- | O(n). Build a map from an ascending list in linear time with a -- combining function for equal keys. The precondition (input list is -- ascending) is not checked. fromAscListWithKey :: (Eq k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a -- | O(n). Build a map from an ascending list of distinct elements -- in linear time. The precondition is not checked. fromDistinctAscList :: [(k, a)] -> Map k a -- | O(n). Filter all values that satisfy the predicate. filter :: (Ord k) => (a -> Bool) -> Map k a -> Map k a -- | O(n). Filter all keys/values that satisfy the predicate. filterWithKey :: (Ord k) => (k -> a -> Bool) -> Map k a -> Map k a -- | O(n). partition the map according to a predicate. The first map -- contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also split. partition :: (Ord k) => (a -> Bool) -> Map k a -> (Map k a, Map k a) -- | O(n). partition the map according to a predicate. The first map -- contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also split. partitionWithKey :: (Ord k) => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a) -- | O(n). Map values and collect the Just results. mapMaybe :: (Ord k) => (a -> Maybe b) -> Map k a -> Map k b -- | O(n). Map keys/values and collect the Just results. mapMaybeWithKey :: (Ord k) => (k -> a -> Maybe b) -> Map k a -> Map k b -- | O(n). Map values and separate the Left and Right -- results. mapEither :: (Ord k) => (a -> Either b c) -> Map k a -> (Map k b, Map k c) -- | O(n). Map keys/values and separate the Left and -- Right results. mapEitherWithKey :: (Ord k) => (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c) -- | O(log n). The expression (split k map) is a -- pair (map1,map2) where the keys in map1 are smaller -- than k and the keys in map2 larger than k. -- Any key equal to k is found in neither map1 nor -- map2. split :: (Ord k) => k -> Map k a -> (Map k a, Map k a) -- | O(log n). The expression (splitLookup k map) -- splits a map just like split but also returns lookup -- k map. splitLookup :: (Ord k) => k -> Map k a -> (Map k a, Maybe a, Map k a) -- | O(n+m). This function is defined as (isSubmapOf = -- isSubmapOfBy (==)). isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool -- | O(n+m). The expression (isSubmapOfBy f t1 t2) -- returns True if all keys in t1 are in tree -- t2, and when f returns True when applied to -- their respective values. For example, the following expressions are -- all True: -- --
-- isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) -- isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) -- isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)]) ---- -- But the following are all False: -- --
-- isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)]) -- isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) -- isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)]) --isSubmapOfBy :: (Ord k) => (a -> b -> Bool) -> Map k a -> Map k b -> Bool -- | O(n+m). Is this a proper submap? (ie. a submap but not equal). -- Defined as (isProperSubmapOf = isProperSubmapOfBy -- (==)). isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool -- | O(n+m). Is this a proper submap? (ie. a submap but not equal). -- The expression (isProperSubmapOfBy f m1 m2) returns -- True when m1 and m2 are not equal, all keys -- in m1 are in m2, and when f returns -- True when applied to their respective values. For example, the -- following expressions are all True: -- --
-- isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) -- isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) ---- -- But the following are all False: -- --
-- isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) -- isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) -- isProperSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) --isProperSubmapOfBy :: (Ord k) => (a -> b -> Bool) -> Map k a -> Map k b -> Bool -- | O(log n). Lookup the index of a key. The index is a -- number from 0 up to, but not including, the size of the -- map. lookupIndex :: (Monad m, Ord k) => k -> Map k a -> m Int -- | O(log n). Return the index of a key. The index is a -- number from 0 up to, but not including, the size of the -- map. Calls error when the key is not a member of the -- map. findIndex :: (Ord k) => k -> Map k a -> Int -- | O(log n). Retrieve an element by index. Calls -- error when an invalid index is used. elemAt :: Int -> Map k a -> (k, a) -- | O(log n). Update the element at index. Calls -- error when an invalid index is used. updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a -- | O(log n). Delete the element at index. Defined as -- (deleteAt i map = updateAt (k x -> -- Nothing) i map). deleteAt :: Int -> Map k a -> Map k a -- | O(log n). The minimal key of the map. findMin :: Map k a -> (k, a) -- | O(log n). The maximal key of the map. findMax :: Map k a -> (k, a) -- | O(log n). Delete the minimal key. deleteMin :: Map k a -> Map k a -- | O(log n). Delete the maximal key. deleteMax :: Map k a -> Map k a -- | O(log n). Delete and find the minimal element. deleteFindMin :: Map k a -> ((k, a), Map k a) -- | O(log n). Delete and find the maximal element. deleteFindMax :: Map k a -> ((k, a), Map k a) -- | O(log n). Update the value at the minimal key. updateMin :: (a -> Maybe a) -> Map k a -> Map k a -- | O(log n). Update the value at the maximal key. updateMax :: (a -> Maybe a) -> Map k a -> Map k a -- | O(log n). Update the value at the minimal key. updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a -- | O(log n). Update the value at the maximal key. updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a -- | O(log n). Retrieves the minimal key's value of the map, and the -- map stripped from that element fails (in the monad) when -- passed an empty map. minView :: (Monad m) => Map k a -> m (a, Map k a) -- | O(log n). Retrieves the maximal key's value of the map, and the -- map stripped from that element fails (in the monad) when -- passed an empty map. maxView :: (Monad m) => Map k a -> m (a, Map k a) -- | O(log n). Retrieves the minimal (key,value) pair of the map, -- and the map stripped from that element fails (in the monad) -- when passed an empty map. minViewWithKey :: (Monad m) => Map k a -> m ((k, a), Map k a) -- | O(log n). Retrieves the maximal (key,value) pair of the map, -- and the map stripped from that element fails (in the monad) -- when passed an empty map. maxViewWithKey :: (Monad m) => Map k a -> m ((k, a), Map k a) -- | O(n). Show the tree that implements the map. The tree is shown -- in a compressed, hanging format. showTree :: (Show k, Show a) => Map k a -> String -- | O(n). The expression (showTreeWith showelem hang -- wide map) shows the tree that implements the map. Elements are -- shown using the showElem function. If hang is -- True, a hanging tree is shown otherwise a rotated tree -- is shown. If wide is True, an extra wide version is -- shown. -- --
-- Map> let t = fromDistinctAscList [(x,()) | x <- [1..5]] -- Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t -- (4,()) -- +--(2,()) -- | +--(1,()) -- | +--(3,()) -- +--(5,()) -- -- Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t -- (4,()) -- | -- +--(2,()) -- | | -- | +--(1,()) -- | | -- | +--(3,()) -- | -- +--(5,()) -- -- Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t -- +--(5,()) -- | -- (4,()) -- | -- | +--(3,()) -- | | -- +--(2,()) -- | -- +--(1,()) --showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String -- | O(n). Test if the internal map structure is valid. valid :: (Ord k) => Map k a -> Bool instance Typeable2 Map instance (Show k, Show a) => Show (Map k a) instance (Ord k, Read k, Read e) => Read (Map k e) instance Foldable (Map k) instance Traversable (Map k) instance Functor (Map k) instance (Ord k, Ord v) => Ord (Map k v) instance (Eq k, Eq a) => Eq (Map k a) instance (Data k, Data a, Ord k) => Data (Map k a) instance (Ord k) => Monoid (Map k v) -- | An efficient implementation of integer sets. -- -- Since many function names (but not the type name) clash with -- Prelude names, this module is usually imported -- qualified, e.g. -- --
-- import Data.IntSet (IntSet) -- import qualified Data.IntSet as IntSet ---- -- The implementation is based on big-endian patricia trees. This -- data structure performs especially well on binary operations like -- union and intersection. However, my benchmarks show that -- it is also (much) faster on insertions and deletions when compared to -- a generic size-balanced set implementation (see Data.Set). -- --
-- split 3 (fromList [1..5]) == (fromList [1,2], fromList [3,4]) --split :: Int -> IntSet -> (IntSet, IntSet) -- | O(min(n,W)). Performs a split but also returns whether -- the pivot element was found in the original set. splitMember :: Int -> IntSet -> (IntSet, Bool, IntSet) -- | O(min(n,W)). The minimal element of a set. findMin :: IntSet -> Int -- | O(min(n,W)). The maximal element of a set. findMax :: IntSet -> Int -- | O(min(n,W)). Delete the minimal element. deleteMin :: IntSet -> IntSet -- | O(min(n,W)). Delete the maximal element. deleteMax :: IntSet -> IntSet -- | O(min(n,W)). Delete and find the minimal element. -- --
-- deleteFindMin set = (findMin set, deleteMin set) --deleteFindMin :: IntSet -> (Int, IntSet) -- | O(min(n,W)). Delete and find the maximal element. -- --
-- deleteFindMax set = (findMax set, deleteMax set) --deleteFindMax :: IntSet -> (Int, IntSet) -- | O(min(n,W)). Retrieves the maximal key of the set, and the set -- stripped from that element fails (in the monad) when passed -- an empty set. maxView :: (Monad m) => IntSet -> m (Int, IntSet) -- | O(min(n,W)). Retrieves the minimal key of the set, and the set -- stripped from that element fails (in the monad) when passed -- an empty set. minView :: (Monad m) => IntSet -> m (Int, IntSet) -- | O(n*min(n,W)). map f s is the set obtained by -- applying f to each element of s. -- -- It's worth noting that the size of the result may be smaller if, for -- some (x,y), x /= y && f x == f y map :: (Int -> Int) -> IntSet -> IntSet -- | O(n). Fold over the elements of a set in an unspecified order. -- --
-- sum set == fold (+) 0 set -- elems set == fold (:) [] set --fold :: (Int -> b -> b) -> b -> IntSet -> b -- | O(n). The elements of a set. (For sets, this is equivalent to -- toList) elems :: IntSet -> [Int] -- | O(n). Convert the set to a list of elements. toList :: IntSet -> [Int] -- | O(n*min(n,W)). Create a set from a list of integers. fromList :: [Int] -> IntSet -- | O(n). Convert the set to an ascending list of elements. toAscList :: IntSet -> [Int] -- | O(n*min(n,W)). Build a set from an ascending list of elements. fromAscList :: [Int] -> IntSet -- | O(n*min(n,W)). Build a set from an ascending list of distinct -- elements. fromDistinctAscList :: [Int] -> IntSet -- | O(n). Show the tree that implements the set. The tree is shown -- in a compressed, hanging format. showTree :: IntSet -> String -- | O(n). The expression (showTreeWith hang wide -- map) shows the tree that implements the set. If hang is -- True, a hanging tree is shown otherwise a rotated tree -- is shown. If wide is True, an extra wide version is -- shown. showTreeWith :: Bool -> Bool -> IntSet -> String instance Typeable IntSet instance Read IntSet instance Show IntSet instance Ord IntSet instance Eq IntSet instance Monad Identity instance Data IntSet instance Monoid IntSet -- | An efficient implementation of maps from integer keys to values. -- -- Since many function names (but not the type name) clash with -- Prelude names, this module is usually imported -- qualified, e.g. -- --
-- import Data.IntMap (IntMap) -- import qualified Data.IntMap as IntMap ---- -- The implementation is based on big-endian patricia trees. This -- data structure performs especially well on binary operations like -- union and intersection. However, my benchmarks show that -- it is also (much) faster on insertions and deletions when compared to -- a generic size-balanced map implementation (see Data.Map). -- --
-- elems map = fold (:) [] map --fold :: (a -> b -> b) -> b -> IntMap a -> b -- | O(n). Fold the keys and values in the map, such that -- foldWithKey f z == Prelude.foldr (uncurry -- f) z . toAscList. For example, -- --
-- keys map = foldWithKey (\k x ks -> k:ks) [] map --foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b -- | O(n). Return all elements of the map in the ascending order of -- their keys. elems :: IntMap a -> [a] -- | O(n). Return all keys of the map in ascending order. keys :: IntMap a -> [Key] -- | O(n*min(n,W)). The set of all keys of the map. keysSet :: IntMap a -> IntSet -- | O(n). Return all key/value pairs in the map in ascending key -- order. assocs :: IntMap a -> [(Key, a)] -- | O(n). Convert the map to a list of key/value pairs. toList :: IntMap a -> [(Key, a)] -- | O(n*min(n,W)). Create a map from a list of key/value pairs. fromList :: [(Key, a)] -> IntMap a -- | O(n*min(n,W)). Create a map from a list of key/value pairs with -- a combining function. See also fromAscListWith. fromListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a -- | O(n*min(n,W)). Build a map from a list of key/value pairs with -- a combining function. See also fromAscListWithKey'. fromListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a -- | O(n). Convert the map to a list of key/value pairs where the -- keys are in ascending order. toAscList :: IntMap a -> [(Key, a)] -- | O(n*min(n,W)). Build a map from a list of key/value pairs where -- the keys are in ascending order. fromAscList :: [(Key, a)] -> IntMap a -- | O(n*min(n,W)). Build a map from a list of key/value pairs where -- the keys are in ascending order, with a combining function on equal -- keys. fromAscListWith :: (a -> a -> a) -> [(Key, a)] -> IntMap a -- | O(n*min(n,W)). Build a map from a list of key/value pairs where -- the keys are in ascending order, with a combining function on equal -- keys. fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key, a)] -> IntMap a -- | O(n*min(n,W)). Build a map from a list of key/value pairs where -- the keys are in ascending order and all distinct. fromDistinctAscList :: [(Key, a)] -> IntMap a -- | O(n). Filter all values that satisfy some predicate. filter :: (a -> Bool) -> IntMap a -> IntMap a -- | O(n). Filter all keys/values that satisfy some predicate. filterWithKey :: (Key -> a -> Bool) -> IntMap a -> IntMap a -- | O(n). partition the map according to some predicate. The first -- map contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also split. partition :: (a -> Bool) -> IntMap a -> (IntMap a, IntMap a) -- | O(n). partition the map according to some predicate. The first -- map contains all elements that satisfy the predicate, the second all -- elements that fail the predicate. See also split. partitionWithKey :: (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap a) -- | O(n). Map values and collect the Just results. mapMaybe :: (a -> Maybe b) -> IntMap a -> IntMap b -- | O(n). Map keys/values and collect the Just results. mapMaybeWithKey :: (Key -> a -> Maybe b) -> IntMap a -> IntMap b -- | O(n). Map values and separate the Left and Right -- results. mapEither :: (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c) -- | O(n). Map keys/values and separate the Left and -- Right results. mapEitherWithKey :: (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c) -- | O(log n). The expression (split k map) is a -- pair (map1,map2) where all keys in map1 are lower -- than k and all keys in map2 larger than k. -- Any key equal to k is found in neither map1 nor -- map2. split :: Key -> IntMap a -> (IntMap a, IntMap a) -- | O(log n). Performs a split but also returns whether the -- pivot key was found in the original map. splitLookup :: Key -> IntMap a -> (IntMap a, Maybe a, IntMap a) -- | O(n+m). Is this a submap? Defined as (isSubmapOf = -- isSubmapOfBy (==)). isSubmapOf :: (Eq a) => IntMap a -> IntMap a -> Bool -- | O(n+m). The expression (isSubmapOfBy f m1 m2) -- returns True if all keys in m1 are in m2, and -- when f returns True when applied to their respective -- values. For example, the following expressions are all True: -- --
-- isSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) -- isSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) -- isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) ---- -- But the following are all False: -- --
-- isSubmapOfBy (==) (fromList [(1,2)]) (fromList [(1,1),(2,2)]) -- isSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) -- isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) --isSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool -- | O(log n). Retrieves the maximal key of the map, and the map -- stripped from that element. fails (in the monad) when passed -- an empty map. -- -- O(log n). Retrieves the minimal key of the map, and the map -- stripped from that element. fails (in the monad) when passed -- an empty map. -- -- O(log n). Delete and find the maximal element. -- -- O(log n). Delete and find the minimal element. -- -- O(log n). The minimal key of the map. -- -- O(log n). The maximal key of the map. -- -- O(log n). Delete the minimal key. -- -- O(log n). Delete the maximal key. -- -- O(n+m). Is this a proper submap? (ie. a submap but not equal). -- Defined as (isProperSubmapOf = isProperSubmapOfBy -- (==)). isProperSubmapOf :: (Eq a) => IntMap a -> IntMap a -> Bool -- | O(n+m). Is this a proper submap? (ie. a submap but not equal). -- The expression (isProperSubmapOfBy f m1 m2) returns -- True when m1 and m2 are not equal, all keys -- in m1 are in m2, and when f returns -- True when applied to their respective values. For example, the -- following expressions are all True: -- --
-- isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) -- isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) ---- -- But the following are all False: -- --
-- isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)]) -- isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)]) -- isProperSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)]) --isProperSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool maxView :: (Monad m) => IntMap b -> m (b, IntMap b) minView :: (Monad m) => IntMap b -> m (b, IntMap b) findMin :: IntMap b -> b findMax :: IntMap b -> b deleteMin :: IntMap b -> IntMap b deleteMax :: IntMap b -> IntMap b deleteFindMin :: IntMap b -> (b, IntMap b) deleteFindMax :: IntMap b -> (b, IntMap b) -- | O(log n). Update the value at the minimal key. updateMin :: (a -> a) -> IntMap a -> IntMap a -- | O(log n). Update the value at the maximal key. updateMax :: (a -> a) -> IntMap a -> IntMap a -- | O(log n). Update the value at the minimal key. updateMinWithKey :: (Key -> a -> a) -> IntMap a -> IntMap a -- | O(log n). Update the value at the maximal key. updateMaxWithKey :: (Key -> a -> a) -> IntMap a -> IntMap a -- | O(log n). Retrieves the minimal (key,value) couple of the map, -- and the map stripped from that element. fails (in the monad) -- when passed an empty map. minViewWithKey :: (Monad m) => IntMap a -> m ((Key, a), IntMap a) -- | O(log n). Retrieves the maximal (key,value) couple of the map, -- and the map stripped from that element. fails (in the monad) -- when passed an empty map. maxViewWithKey :: (Monad m) => IntMap a -> m ((Key, a), IntMap a) -- | O(n). Show the tree that implements the map. The tree is shown -- in a compressed, hanging format. showTree :: (Show a) => IntMap a -> String -- | O(n). The expression (showTreeWith hang wide -- map) shows the tree that implements the map. If hang is -- True, a hanging tree is shown otherwise a rotated tree -- is shown. If wide is True, an extra wide version is -- shown. showTreeWith :: (Show a) => Bool -> Bool -> IntMap a -> String instance Typeable1 IntMap instance (Read e) => Read (IntMap e) instance (Show a) => Show (IntMap a) instance Functor IntMap instance (Ord a) => Ord (IntMap a) instance (Eq a) => Eq (IntMap a) instance Monad Identity instance (Data a) => Data (IntMap a) instance Foldable IntMap instance Monoid (IntMap a) -- | Multi-way trees (aka rose trees) and forests. module Data.Tree -- | Multi-way trees, also known as rose trees. data Tree a Node :: a -> Forest a -> Tree a -- | label value rootLabel :: Tree a -> a -- | zero or more child trees subForest :: Tree a -> Forest a type Forest a = [Tree a] -- | Neat 2-dimensional drawing of a tree. drawTree :: Tree String -> String -- | Neat 2-dimensional drawing of a forest. drawForest :: Forest String -> String -- | The elements of a tree in pre-order. flatten :: Tree a -> [a] -- | Lists of nodes at each level of the tree. levels :: Tree a -> [[a]] -- | Build a tree from a seed value unfoldTree :: (b -> (a, [b])) -> b -> Tree a -- | Build a forest from a list of seed values unfoldForest :: (b -> (a, [b])) -> [b] -> Forest a -- | Monadic tree builder, in depth-first order unfoldTreeM :: (Monad m) => (b -> m (a, [b])) -> b -> m (Tree a) -- | Monadic forest builder, in depth-first order unfoldForestM :: (Monad m) => (b -> m (a, [b])) -> [b] -> m (Forest a) -- | Monadic tree builder, in breadth-first order, using an algorithm -- adapted from Breadth-First Numbering: Lessons from a Small Exercise -- in Algorithm Design, by Chris Okasaki, ICFP'00. unfoldTreeM_BF :: (Monad m) => (b -> m (a, [b])) -> b -> m (Tree a) -- | Monadic forest builder, in breadth-first order, using an algorithm -- adapted from Breadth-First Numbering: Lessons from a Small Exercise -- in Algorithm Design, by Chris Okasaki, ICFP'00. unfoldForestM_BF :: (Monad m) => (b -> m (a, [b])) -> [b] -> m (Forest a) instance (Eq a) => Eq (Tree a) instance (Read a) => Read (Tree a) instance (Show a) => Show (Tree a) instance (Data a) => Data (Tree a) instance Foldable Tree instance Traversable Tree instance Monad Tree instance Applicative Tree instance Functor Tree instance Typeable1 Tree -- | A version of the graph algorithms described in: -- -- Lazy Depth-First Search and Linear Graph Algorithms in Haskell, -- by David King and John Launchbury. module Data.Graph -- | The strongly connected components of a directed graph, topologically -- sorted. stronglyConnComp :: (Ord key) => [(node, key, [key])] -> [SCC node] -- | The strongly connected components of a directed graph, topologically -- sorted. The function is the same as stronglyConnComp, except -- that all the information about each node retained. This interface is -- used when you expect to apply SCC to (some of) the result of -- SCC, so you don't want to lose the dependency information. stronglyConnCompR :: (Ord key) => [(node, key, [key])] -> [SCC (node, key, [key])] -- | Strongly connected component. data SCC vertex -- | A single vertex that is not in any cycle. AcyclicSCC :: vertex -> SCC vertex -- | A maximal set of mutually reachable vertices. CyclicSCC :: [vertex] -> SCC vertex -- | The vertices of a strongly connected component. flattenSCC :: SCC vertex -> [vertex] -- | The vertices of a list of strongly connected components. flattenSCCs :: [SCC a] -> [a] -- | Adjacency list representation of a graph, mapping each vertex to its -- list of successors. type Graph = Table [Vertex] -- | Table indexed by a contiguous set of vertices. type Table a = Array Vertex a -- | The bounds of a Table. type Bounds = (Vertex, Vertex) -- | An edge from the first vertex to the second. type Edge = (Vertex, Vertex) -- | Abstract representation of vertices. type Vertex = Int -- | Build a graph from a list of nodes uniquely identified by keys, with a -- list of keys of nodes this node should have edges to. The out-list may -- contain keys that don't correspond to nodes of the graph; they are -- ignored. graphFromEdges :: (Ord key) => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex) -- | Identical to graphFromEdges, except that the return value does -- not include the function which maps keys to vertices. This version of -- graphFromEdges is for backwards compatibility. graphFromEdges' :: (Ord key) => [(node, key, [key])] -> (Graph, Vertex -> (node, key, [key])) -- | Build a graph from a list of edges. buildG :: Bounds -> [Edge] -> Graph -- | The graph obtained by reversing all edges. transposeG :: Graph -> Graph -- | All vertices of a graph. vertices :: Graph -> [Vertex] -- | All edges of a graph. edges :: Graph -> [Edge] -- | A table of the count of edges from each node. outdegree :: Graph -> Table Int -- | A table of the count of edges into each node. indegree :: Graph -> Table Int -- | A spanning forest of the part of the graph reachable from the listed -- vertices, obtained from a depth-first search of the graph starting at -- each of the listed vertices in order. dfs :: Graph -> [Vertex] -> Forest Vertex -- | A spanning forest of the graph, obtained from a depth-first search of -- the graph starting from each vertex in an unspecified order. dff :: Graph -> Forest Vertex -- | A topological sort of the graph. The order is partially specified by -- the condition that a vertex i precedes j whenever -- j is reachable from i but not vice versa. topSort :: Graph -> [Vertex] -- | The connected components of a graph. Two vertices are connected if -- there is a path between them, traversing edges in either direction. components :: Graph -> Forest Vertex -- | The strongly connected components of a graph. scc :: Graph -> Forest Vertex -- | The biconnected components of a graph. An undirected graph is -- biconnected if the deletion of any vertex leaves it connected. bcc :: Graph -> Forest [Vertex] -- | A list of vertices reachable from a given vertex. reachable :: Graph -> Vertex -> [Vertex] -- | Is the second vertex reachable from the first? path :: Graph -> Vertex -> Vertex -> Bool instance Monad (SetM s)