Safe Haskell  SafeInfered 

A nested map. The values in each NestedMap are tuples, with the first element of the tuple being a label that you select and the second value being another NestedMap. Functions are provided so you may query the map at any level or insert new labels (and, therefore, new keys) at any level.
 newtype NestedMap k l = NestedMap {
 unNestedMap :: Map k (l, NestedMap k l)
 empty :: NestedMap k l
 relabel :: Ord k => NestedMap k l > [(k, Maybe l > l)] > NestedMap k l
 descend :: Ord k => [k] > NestedMap k l > [(k, l)]
 insert :: (Ord k, Monoid l) => NestedMap k l > [k] > l > NestedMap k l
 cumulativeTotal :: Monoid l => NestedMap k l > (l, NestedMap k l)
 traverse :: (Monad m, Ord k) => (k > l > NestedMap k l > m (Maybe a)) > NestedMap k l > m (NestedMap k a)
 traverseWithTrail :: (Monad m, Ord k) => ([(k, l)] > k > l > NestedMap k l > m (Maybe a)) > NestedMap k l > m (NestedMap k a)
Documentation
NestedMap  

relabel :: Ord k => NestedMap k l > [(k, Maybe l > l)] > NestedMap k lSource
Descends through a NestedMap with successive keys in the list, proceeding from left to right. At any given level, if the key given does not already exist, then inserts an empty submap and applies the given label modification function to Nothing to determine the new label. If the given key already does exist, then preserves the existing submap and applies the given label modification function to (Just oldlabel) to determine the new label.
descend :: Ord k => [k] > NestedMap k l > [(k, l)]Source
Given a list of keys, find the key that is furthest down in the map that matches the requested list of keys. Returns [(k, l)], where the first item in the list is the topmost key found and its matching label, and the last item in the list is the deepest key found and its matching label. (Often you will be most interested in the deepest key.)
insert :: (Ord k, Monoid l) => NestedMap k l > [k] > l > NestedMap k lSource
Descends through the NestedMap one level at a time, proceeding key by key from left to right through the list of keys given. At the last key, appends the given label to the labels already present; if no label is present, uses mempty and mappend to create a new label. If the list of keys is empty, does nothing.
cumulativeTotal :: Monoid l => NestedMap k l > (l, NestedMap k l)Source
Leaves all keys of the map and submaps the same. Changes each label to reflect the total of that label and of all the labels of the maps within the NestedMap accompanying the label. Returns the total of the entire NestedMap.
traverse :: (Monad m, Ord k) => (k > l > NestedMap k l > m (Maybe a)) > NestedMap k l > m (NestedMap k a)Source
Supply a function that takes a key, a label, and a NestedMap. traverse will traverse the NestedMap. For each (label, NestedMap) pair, traverse will first apply the given function to the label before descending through the NestedMap. The function is applied to the present key and label and the accompanying NestedMap. The function you supply must return a Maybe. If the result is Nothing, then the pair is deleted as a value from its parent NestedMap. If the result is (Just s), then the label of this level of the NestedMap is changed to s before descending to the next level of the NestedMap.
All this is done in a monad, so you can carry out arbitrary side effects such as inspecting or changing a state or doing IO. If you don't need a monad, just use Identity.
Thus this function can be used to inspect, modify, and prune a NestedMap.
For a simpler traverse that does not provide you with so much information, NestedMap is also an instance of Data.Traversable.