Haskell: Traversal on a Map-CodePudding

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.

CodePudding user response：

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.

CodePudding user response：

There is no existing function with that signature and behavior. You'll have to write it yourself.