Portability | portable |
---|---|

Stability | provisional |

Maintainer | libraries@haskell.org |

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:

- Stephen Adams, "
*Efficient sets: a balancing act*", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/. - J. Nievergelt and E.M. Reingold,
"
*Binary search trees of bounded balance*", SIAM journal of computing 2(1), March 1973.

Note that the implementation is *left-biased* -- the elements of a
first argument are always preferred to the second, for example in
`union`

or `insert`

.

- data Map k a
- (!) :: Ord k => Map k a -> k -> a
- (\\) :: Ord k => Map k a -> Map k b -> Map k a
- null :: Map k a -> Bool
- size :: Map k a -> Int
- member :: Ord k => k -> Map k a -> Bool
- notMember :: Ord k => k -> Map k a -> Bool
- lookup :: (Monad m, Ord k) => k -> Map k a -> m a
- findWithDefault :: Ord k => a -> k -> Map k a -> a
- empty :: Map k a
- singleton :: k -> a -> Map k a
- insert :: Ord k => k -> a -> Map k a -> Map k a
- insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
- insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
- delete :: Ord k => k -> Map k a -> Map k a
- adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
- adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
- update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
- updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
- updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
- alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
- union :: Ord k => Map k a -> Map k a -> Map k a
- unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
- unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
- unions :: Ord k => [Map k a] -> Map k a
- unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k a
- difference :: Ord k => Map k a -> Map k b -> Map k a
- differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
- differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
- intersection :: Ord k => Map k a -> Map k b -> Map k a
- intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
- intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
- map :: (a -> b) -> Map k a -> Map k b
- mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
- mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
- mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
- mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a
- fold :: (a -> b -> b) -> b -> Map k a -> b
- foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
- elems :: Map k a -> [a]
- keys :: Map k a -> [k]
- keysSet :: Map k a -> Set k
- assocs :: Map k a -> [(k, a)]
- toList :: Map k a -> [(k, a)]
- fromList :: Ord k => [(k, a)] -> Map k a
- fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- toAscList :: Map k a -> [(k, a)]
- fromAscList :: Eq k => [(k, a)] -> Map k a
- fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- fromDistinctAscList :: [(k, a)] -> Map k a
- filter :: Ord k => (a -> Bool) -> Map k a -> Map k a
- filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k a
- partition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)
- partitionWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
- mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k b
- mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> Map k a -> Map k b
- mapEither :: Ord k => (a -> Either b c) -> Map k a -> (Map k b, Map k c)
- mapEitherWithKey :: Ord k => (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
- split :: Ord k => k -> Map k a -> (Map k a, Map k a)
- splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
- isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
- isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
- lookupIndex :: (Monad m, Ord k) => k -> Map k a -> m Int
- findIndex :: Ord k => k -> Map k a -> Int
- elemAt :: Int -> Map k a -> (k, a)
- updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
- deleteAt :: Int -> Map k a -> Map k a
- findMin :: Map k a -> (k, a)
- findMax :: Map k a -> (k, a)
- deleteMin :: Map k a -> Map k a
- deleteMax :: Map k a -> Map k a
- deleteFindMin :: Map k a -> ((k, a), Map k a)
- deleteFindMax :: Map k a -> ((k, a), Map k a)
- updateMin :: (a -> Maybe a) -> Map k a -> Map k a
- updateMax :: (a -> Maybe a) -> Map k a -> Map k a
- updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
- updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k a
- minView :: Monad m => Map k a -> m (a, Map k a)
- maxView :: Monad m => Map k a -> m (a, Map k a)
- minViewWithKey :: Monad m => Map k a -> m ((k, a), Map k a)
- maxViewWithKey :: Monad m => Map k a -> m ((k, a), Map k a)
- showTree :: (Show k, Show a) => Map k a -> String
- showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> String
- valid :: Ord k => Map k a -> Bool

# Map type

A Map from keys `k`

to values `a`

.

# Operators

(!) :: Ord k => Map k a -> k -> aSource

*O(log n)*. Find the value at a key.
Calls `error`

when the element can not be found.

# Query

findWithDefault :: Ord k => a -> k -> Map k a -> aSource

*O(log n)*. The expression `(`

returns
the value at key `findWithDefault`

def k map)`k`

or returns `def`

when the key is not in the map.

# Construction

## Insertion

insert :: Ord k => k -> a -> Map k a -> Map k aSource

*O(log n)*. Insert a new key and value in the map.
If the key is already present in the map, the associated value is
replaced with the supplied value, i.e. `insert`

is equivalent to

.
`insertWith`

`const`

insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aSource

*O(log n)*. Insert with a combining function.

will insert the pair (key, value) into `insertWith`

f key value mp`mp`

if key does
not exist in the map. If the key does exist, the function will
insert the pair `(key, f new_value old_value)`

.

insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k aSource

*O(log n)*. Insert with a combining function.

will insert the pair (key, value) into `insertWithKey`

f key value mp`mp`

if key does
not exist in the map. If the key does exist, the function will
insert the pair `(key,f key new_value old_value)`

.
Note that the key passed to f is the same key passed to `insertWithKey`

.

insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)Source

*O(log n)*. The expression (

)
is a pair where the first element is equal to (`insertLookupWithKey`

f k x map

)
and the second element equal to (`lookup`

k map

).
`insertWithKey`

f k x map

insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k aSource

Same as `insertWith`

, but the combining function is applied strictly.

insertWithKey' :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k aSource

Same as `insertWithKey`

, but the combining function is applied strictly.

## Delete/Update

delete :: Ord k => k -> Map k a -> Map k aSource

*O(log n)*. Delete a key and its value from the map. When the key is not
a member of the map, the original map is returned.

adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k aSource

*O(log n)*. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.

adjustWithKey :: Ord k => (k -> a -> a) -> k -> Map k a -> Map k aSource

*O(log n)*. Adjust a value at a specific key. When the key is not
a member of the map, the original map is returned.

updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k aSource

*O(log n)*. The expression (

) updates the
value `updateWithKey`

f k map`x`

at `k`

(if it is in the map). If (`f k x`

) is `Nothing`

,
the element is deleted. If it is (

), the key `Just`

y`k`

is bound
to the new value `y`

.

updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)Source

*O(log n)*. Lookup and update.

# Combine

## Union

unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k aSource

*O(n+m)*. Union with a combining function. The implementation uses the efficient *hedge-union* algorithm.

unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k aSource

*O(n+m)*.
Union with a combining function. The implementation uses the efficient *hedge-union* algorithm.
Hedge-union is more efficient on (bigset `union`

smallset).

unionsWith :: Ord k => (a -> a -> a) -> [Map k a] -> Map k aSource

The union of a list of maps, with a combining operation:
(

).
`unionsWith`

f == `Prelude.foldl`

(`unionWith`

f) `empty`

## Difference

difference :: Ord k => Map k a -> Map k b -> Map k aSource

*O(n+m)*. Difference of two maps.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

differenceWith :: Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k aSource

*O(n+m)*. Difference with a combining function.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k aSource

*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 (

), the element is updated with a new value `Just`

y`y`

.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

## Intersection

intersection :: Ord k => Map k a -> Map k b -> Map k aSource

*O(n+m)*. Intersection of two maps. The values in the first
map are returned, i.e. (

).
`intersection`

m1 m2 == `intersectionWith`

`const`

m1 m2

intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k cSource

*O(n+m)*. Intersection with a combining function.

intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k cSource

*O(n+m)*. Intersection with a combining function.
Intersection is more efficient on (bigset `intersection`

smallset)
intersectionWithKey :: Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey f Tip t = Tip
intersectionWithKey f t Tip = Tip
intersectionWithKey f t1 t2 = intersectWithKey f t1 t2

intersectWithKey f Tip t = Tip intersectWithKey f t Tip = Tip intersectWithKey f t (Bin _ kx x l r) = case found of Nothing -> merge tl tr Just y -> join kx (f kx y x) tl tr where (lt,found,gt) = splitLookup kx t tl = intersectWithKey f lt l tr = intersectWithKey f gt r

# Traversal

## Map

mapWithKey :: (k -> a -> b) -> Map k a -> Map k bSource

*O(n)*. Map a function over all values in the map.

mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)Source

*O(n)*. The function `mapAccum`

threads an accumulating
argument through the map in ascending order of keys.

mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)Source

*O(n)*. The function `mapAccumWithKey`

threads an accumulating
argument through the map in ascending order of keys.

mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 aSource

*O(n*log n)*.

is the map obtained by applying `mapKeys`

f s`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 smallest of
these keys is retained.

mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 aSource

*O(n*log n)*.

is the map obtained by applying `mapKeysWith`

c f s`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`

.

mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 aSource

*O(n)*.

, but works only when `mapKeysMonotonic`

f s == `mapKeys`

f s`f`

is strictly monotonic.
*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 where ls = keys s

## Fold

foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> bSource

*O(n)*. Fold the keys and values in the map, such that

.
For example,
`foldWithKey`

f z == `Prelude.foldr`

(`uncurry`

f) z . `toAscList`

keys map = foldWithKey (\k x ks -> k:ks) [] map

# Conversion

*O(n)*.
Return all elements of the map in the ascending order of their keys.

assocs :: Map k a -> [(k, a)]Source

*O(n)*. Return all key/value pairs in the map in ascending key order.

## Lists

fromList :: Ord k => [(k, a)] -> Map k aSource

*O(n*log n)*. Build a map from a list of key/value pairs. See also `fromAscList`

.

fromListWith :: Ord k => (a -> a -> a) -> [(k, a)] -> Map k aSource

*O(n*log n)*. Build a map from a list of key/value pairs with a combining function. See also `fromAscListWith`

.

fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k aSource

*O(n*log n)*. Build a map from a list of key/value pairs with a combining function. See also `fromAscListWithKey`

.

## Ordered lists

fromAscList :: Eq k => [(k, a)] -> Map k aSource

*O(n)*. Build a map from an ascending list in linear time.
*The precondition (input list is ascending) is not checked.*

fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k aSource

*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 aSource

*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.*

fromDistinctAscList :: [(k, a)] -> Map k aSource

*O(n)*. Build a map from an ascending list of distinct elements in linear time.
*The precondition is not checked.*

# Filter

filter :: Ord k => (a -> Bool) -> Map k a -> Map k aSource

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

filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k aSource

*O(n)*. Filter all keys/values that satisfy the predicate.

partition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)Source

*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)Source

*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`

.

mapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k bSource

*O(n)*. Map values and collect the `Just`

results.

mapMaybeWithKey :: Ord k => (k -> a -> Maybe b) -> Map k a -> Map k bSource

*O(n)*. Map keys/values and collect the `Just`

results.

split :: Ord k => k -> Map k a -> (Map k a, Map k a)Source

*O(log n)*. The expression (

) is a pair `split`

k map`(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`

.

splitLookup :: Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)Source

*O(log n)*. The expression (

) splits a map just
like `splitLookup`

k map`split`

but also returns

.
`lookup`

k map

# Submap

isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> BoolSource

*O(n+m)*.
This function is defined as (

).
`isSubmapOf`

= `isSubmapOfBy`

(==)

isSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> BoolSource

*O(n+m)*.
The expression (

) returns `isSubmapOfBy`

f t1 t2`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)])

isProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> BoolSource

*O(n+m)*. Is this a proper submap? (ie. a submap but not equal).
Defined as (

).
`isProperSubmapOf`

= `isProperSubmapOfBy`

(==)

isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> BoolSource

*O(n+m)*. Is this a proper submap? (ie. a submap but not equal).
The expression (

) returns `isProperSubmapOfBy`

f m1 m2`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)])

# Indexed

lookupIndex :: (Monad m, Ord k) => k -> Map k a -> m IntSource

*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.

elemAt :: Int -> Map k a -> (k, a)Source

*O(log n)*. Retrieve an element by *index*. Calls `error`

when an
invalid index is used.

updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k aSource

*O(log n)*. Update the element at *index*. Calls `error`

when an
invalid index is used.

# Min/Max

deleteFindMin :: Map k a -> ((k, a), Map k a)Source

*O(log n)*. Delete and find the minimal element.

deleteFindMax :: Map k a -> ((k, a), Map k a)Source

*O(log n)*. Delete and find the maximal element.

updateMin :: (a -> Maybe a) -> Map k a -> Map k aSource

*O(log n)*. Update the value at the minimal key.

updateMax :: (a -> Maybe a) -> Map k a -> Map k aSource

*O(log n)*. Update the value at the maximal key.

updateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k aSource

*O(log n)*. Update the value at the minimal key.

updateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k aSource

*O(log n)*. Update the value at the maximal key.

minView :: Monad m => Map k a -> m (a, Map k a)Source

*O(log n)*. Retrieves the minimal key's value of the map, and the map stripped from that element
`fail`

s (in the monad) when passed an empty map.

maxView :: Monad m => Map k a -> m (a, Map k a)Source

*O(log n)*. Retrieves the maximal key's value of the map, and the map stripped from that element
`fail`

s (in the monad) when passed an empty map.

minViewWithKey :: Monad m => Map k a -> m ((k, a), Map k a)Source

*O(log n)*. Retrieves the minimal (key,value) pair of the map, and the map stripped from that element
`fail`

s (in the monad) when passed an empty map.

maxViewWithKey :: Monad m => Map k a -> m ((k, a), Map k a)Source

*O(log n)*. Retrieves the maximal (key,value) pair of the map, and the map stripped from that element
`fail`

s (in the monad) when passed an empty map.

# Debugging

showTree :: (Show k, Show a) => Map k a -> StringSource

*O(n)*. Show the tree that implements the map. The tree is shown
in a compressed, hanging format.

showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> StringSource

*O(n)*. The expression (

) shows
the tree that implements the map. Elements are shown using the `showTreeWith`

showelem hang wide map`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,())