Search code examples
dictionaryhaskelltraversal

Haskell: Traversal on a Map


I'm looking for a function with this signature:

chainTraversal :: k -> (k -> a -> Maybe (k, b)) -> Map k a -> Map k b

You give it an initial key to start at, a function and a map.

It will extract the element at the position k in the Map, and feed that element to the function. Based on this, the function will return another key to look at next.

It's some mix between a filter and a traversal, with the elements themselves giving the next position to open. The result is the list of elements that has been traversed. It can be shorter than the original map.

Edit: taking into account a comment.


Solution

  • Since all the lookups are done in the original Map:

    foo :: k -> (k -> a -> Maybe (k, b)) -> Map k a -> Map k b
    foo k f m = fromList $ unfoldr g k
      where
      g k = (\(k', b) -> (k', (k, b)))    -- k ? k' ? you decide
               <$> (f' k =<< (m `at` k))
      f' k (k', a) = f k a          -- or:   f k' a ? you decide
    

    or something like that.

    You'll have to implement the at function in terms of one of the lookupNN functions of your choosing.

    It's not a filter since it must stop on the first Nothing produced by f.