O(1). The empty table.

size empty === 0

O(1). A table with a single element.

singleton 1 'a' "a" === fromList [(1,'a',"a")]
size (singleton 1 'a' "a") === 1

Build a table from a row map.

fromRowMap (Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]), (2, Map.fromList [('a',"d")])])
  === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]

Build a table from a column map.

fromColumnMap (Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]), (2, Map.fromList [('a',"d")])])
  === fromList [('a',1,"b"),('a',2,"d"),('b',1,"c")]

Flip the row and column keys.

transpose (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [('a',1,"b"),('a',2,"d"),('b',1,"c")]

Build a table from a list of key/value pairs.

fromList ([] :: [(Int, Char, String)]) === empty

O(log k). Associate with value with the row key and the column key. If the table already contains a value for those keys, the value is replaced.

insert 1 'a' "a" empty === singleton 1 'a' "a"
insert 1 'a' "a" (fromList [(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"d")]
insert 1 'a' "a" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"d")]

O(log k). Remove the value associated with the given keys.

delete 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'b',"c"),(2,'a',"d")]
delete 1 'a' (fromList [(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'b',"c"),(2,'a',"d")]

Remove an entire row.

deleteRow 1 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"
deleteRow 3 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]

Remove an entire column.

deleteColumn 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"
deleteColumn 'z' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]

O(log k), assuming the function a -> a takes O(1). Update the value at a specific row key and column key, if exists.

adjust ("new " ++) 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === fromList [(1,'a',"new b"),(1,'b',"c"),(2,'a',"d")]

O(log k), assuming the function r -> c -> a -> a takes O(1). Update the value at a specific row key and column key, if exists.

adjustWithKeys (\r c x -> show r ++ ":" ++ show c ++ ":new " ++ x) 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
  === fromList [(1,'a',"1:'a':new b"),(1,'b',"c"),(2,'a',"d")]

O(log k), assuming the function a -> Maybe a takes O(1). The expression (update f r c table) updates the value at the given row and column keys, if exists. If f returns Nothing, the value associated with those keys, if exists is deleted.

let f x = if x == "b" then Just "new b" else Nothing in do
  update f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"new b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  update f 1 'a' (fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]

O(log k), assuming the function r -> c -> a -> Maybe a takes O(1). The expression (updateWithKeys f r c table) updates the value at the given row and column keys, if exists. If f returns Nothing, the value associated with those keys, if exists is deleted.

let f r c x = if x == "b" then Just (show r ++ ":" ++ show c ++ ":new b") else Nothing in do
  updateWithKeys f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"1:'a':new b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  updateWithKeys f 1 'a' (fromList [(1,'a',"a"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]

O(log k), assuming the function Maybe a -> Maybe a takes O(1). The expression (alter f r c table) alters the value at the given row and column keys, if exists. It can be used to insert, delete or update a value.

let (f,g,h) = (const Nothing, const (Just "hello"), fmap ('z':)) in do
  alter f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alter f 4 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alter f 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alter g 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"hello"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alter g 4 'e' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c"),(4,'e',"hello")]
  alter h 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"zb"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alter h 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]

O(log k), assuming the function r -> c -> Maybe a -> Maybe a takes O(1). The expression (alterWithKeys f r c table) alters the value at the given row and column keys, if exists. It can be used to insert, delete or update a value.

let (f,g) = (\_ _ _ -> Nothing, \r c -> fmap ((show r ++ ":" ++ show c ++ ":") ++)) in do
  alterWithKeys f 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alterWithKeys f 4 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alterWithKeys f 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alterWithKeys g 1 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"1:'a':b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]
  alterWithKeys g 2 'b' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]) === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(3,'a',"c")]

O(log k). Lookup the values at a row key and column key in the map.

O(log k). Lookup the values at a row key and column key in the map.

fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] !? (1,'a') === Just "b"
fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] !? (1,'c') === Nothing

O(log k). Lookup the values at a row key and column key in the map. Calls error if the value does not exist.

fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")] ! (1,'a') === "b"

O(log k). Is there a value associated with the given row and column keys?

hasCell (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (1,'a') === True
hasCell (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (1,'c') === False

O(log r). Is there a row with the given row key that has at least one value?

hasRow (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 1 === True
hasRow (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 3 === False

O(log c). Is there a column with the given column key that has at least one value?

hasColumn (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 'a' === True
hasColumn (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) 'c' === False

O(1). Is the table empty?

Data.Multimap.Table.null empty === True
Data.Multimap.Table.null (singleton 1 'a' "a") === False

O(1). Is the table non-empty?

notNull empty === False
notNull (singleton 1 'a' "a") === True

The total number of values for all row and column keys.

size is evaluated lazily. Forcing the size for the first time takes up to O(n) and subsequent forces take O(1).

size empty === 0
size (singleton 1 'a' "a") === 1
size (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === 3

Union two tables, preferring values from the first table upon duplicate keys.

union (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
  === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]

Union two tables with a combining function for duplicate keys.

unionWith (++) (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
  === fromList [(1,'a',"bc"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]

Union two tables with a combining function for duplicate keys.

let f r c a a' = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ a' in do
  unionWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")])
    === fromList [(1,'a',"1:'a':b|c"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]

Union a number of tables, preferring values from the leftmost table upon duplicate keys.

unions [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
  === fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]

Union a number of tables with a combining function for duplicate keys.

unionsWith (++) [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
  === fromList [(1,'a',"bc"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]

Union a number of tables with a combining function for duplicate keys.

let f r c a a' = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ a' in do
  unionsWithKeys f [fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")], fromList [(1,'a',"c"),(2,'b',"d"),(3,'c',"e")]]
    === fromList [(1,'a',"1:'a':b|c"),(1,'b',"c"),(2,'a',"b"),(2,'b',"d"),(3,'c',"e")]

Difference of two tables. Return values in the first table whose row and column keys do not have an associated value in the second table.

difference (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) (fromList [(1,'a',"c"),(1,'b',"d"),(2,'b',"b")])
  === singleton 2 'a' "b"

O(n), assuming the function a -> b takes O(1). Map a function over all values in the table.

Data.Multimap.Table.map (++ "x") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === fromList [(1,'a',"bx"),(1,'b',"cx"),(2,'a',"bx")]

O(n), assuming the function r -> c -> a -> b takes O(1). Map a function over all values in the table.

mapWithKeys (\r c x -> show r ++ ":" ++ show c ++ ":" ++ x) (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")])
  === fromList [(1,'a',"1:'a':b"),(1,'b',"1:'b':c"),(2,'a',"2:'a':b")]

Traverse the (row key, column key, value) triples and collect the results.

let f r c a = if odd r && c > 'a' then Just (a ++ "x") else Nothing in do
  traverseWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"b")]) === Nothing
  traverseWithKeys f (fromList [(1,'b',"b"),(1,'c',"c"),(3,'d',"b")]) === Just (fromList [(1,'b',"bx"),(1,'c',"cx"),(3,'d',"bx")])

Traverse the (row key, column key, value) triples and collect the Just results.

O(n). Fold the values in the table row by row using the given right-associative binary operator.

Data.Multimap.Table.foldr (:) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "bcd"

O(n). Fold the values in the table row by row using the given left-associative binary operator.

Data.Multimap.Table.foldl (flip (:)) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "dcb"

O(n). Fold the (row key, column key value) triplets in the table row by row using the given right-associative binary operator.

let f r c a b = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ b in do
  foldrWithKeys f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"

O(n). Fold the (row key, column key, value) triplets in the table row by row using the given left-associative binary operator.

let f a r c b = show r ++ ":" ++ show c ++ ":" ++ b ++ "|" ++ a in do
  foldlWithKeys f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "2:'a':d|1:'b':c|1:'a':b|"

O(n). Fold the (row key, column key, value) triplets in the map row by row using the given monoid.

let f r c a = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" in do
  foldMapWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"

O(n). A strict version of foldr. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

Data.Multimap.Table.foldr' (:) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "bcd"

O(n). A strict version of foldl. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

Data.Multimap.Table.foldl' (flip (:)) "" (fromList [(1,'a','b'),(1,'b','c'),(2,'a','d')]) === "dcb"

O(n). A strict version of foldrWithKey. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

let f r c a b = show r ++ ":" ++ show c ++ ":" ++ a ++ "|" ++ b in do
  foldrWithKeys' f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "1:'a':b|1:'b':c|2:'a':d|"

O(n). A strict version of foldlWithKey. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

let f a r c b = show r ++ ":" ++ show c ++ ":" ++ b ++ "|" ++ a in do
  foldlWithKeys' f "" (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === "2:'a':d|1:'b':c|1:'a':b|"

O(r). Return a mapping from column keys to values for the given row key.

row 1 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.fromList [('a',"b"),('b',"c")]
row 3 (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.empty

O(c). Return a mapping from row keys to values for the given column key.

column 'a' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.fromList [(1,"b"),(2,"d")]
column 'c' (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Map.empty

Return a mapping from row keys to maps from column keys to values.

rowMap (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
  === Map.fromList [(1, Map.fromList [('a',"b"),('b',"c")]),(2, Map.fromList [('a',"d")])]

Return a mapping from column keys to maps from row keys to values.

columnMap (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")])
  === Map.fromList [('a', Map.fromList [(1,"b"),(2,"d")]),('b', Map.fromList [(1,"c")])]

Return, in ascending order, the list of all row keys of that have at least one value in the table.

rowKeys (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [1,2]

Return, in ascending order, the list of all column keys of that have at least one value in the table.

columnKeys (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === ['a','b']

Return the set of all row keys of that have at least one value in the table.

rowKeysSet (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Set.fromList [1,2]

Return the set of all column keys of that have at least one value in the table.

columnKeysSet (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === Set.fromList ['a','b']

Convert the table into a list of (row key, column key, value) triples.

toList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]

Convert the table into a list of (row key, column key, value) triples in ascending order of row keys, and ascending order of column keys with a row.

toRowAscList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]

Convert the table into a list of (column key, row key, value) triples in ascending order of column keys, and ascending order of row keys with a column.

toColumnAscList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [('a',1,"b"),('a',2,"d"),('b',1,"c")]

Convert the table into a list of (row key, column key, value) triples in descending order of row keys, and descending order of column keys with a row.

toRowDescList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [(2,'a',"d"),(1,'b',"c"),(1,'a',"b")]

Convert the table into a list of (column key, row key, value) triples in descending order of column keys, and descending order of row keys with a column.

toColumnDescList (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === [('b',1,"c"),('a',2,"d"),('a',1,"b")]

O(n), assuming the predicate function takes O(1). Retain all values that satisfy the predicate.

Data.Multimap.Table.filter (> "c") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"
Data.Multimap.Table.filter (> "d") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === empty

O(r), assuming the predicate function takes O(1). Retain all rows that satisfy the predicate.

filterRow even (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 2 'a' "d"

O(c), assuming the predicate function takes O(1). Retain all columns that satisfy the predicate.

filterColumn (> 'a') (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"

O(c), assuming the predicate function takes O(1). Retain all (row key, column key, value) triples that satisfy the predicate.

filterWithKeys (\r c a -> odd r && c > 'a' && a > "b") (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "c"

O(n), assuming the function a -> Maybe b takes O(1). Map values and collect the Just results.

mapMaybe (\a -> if a == "a" then Just "new a" else Nothing) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
  === fromList [(1,'a',"new a"),(2,'b',"new a")]

O(n), assuming the function r -> c -> a -> Maybe b takes O(1). Map (row key, column key, value) triples and collect the Just results.

let f r c a = if r == 1 && a == "c" then Just "new c" else Nothing in do
  mapMaybeWithKeys f (fromList [(1,'a',"b"),(1,'b',"c"),(2,'a',"d")]) === singleton 1 'b' "new c"

O(n), assuming the function a -> Either a1 a2 takes O(1). Map values and separate the Left and Right results.

mapEither (\a -> if a == "a" then Left a else Right a) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
  === (fromList [(1,'a',"a"),(2,'b',"a")],fromList [(1,'b',"c")])

O(n), assuming the function r -> c -> a -> Either a1 a2 takes O(1). Map (row key, column key, value) triples and separate the Left and Right results.

mapEitherWithKeys (\r c a -> if r == 1 && c == 'a' then Left a else Right a) (fromList [(1,'a',"a"),(1,'b',"c"),(2,'b',"a")])
  === (fromList [(1,'a',"a")],fromList [(1,'b',"c"),(2,'b',"a")])