CODEWITHSUNDEEP
dictionaryhaskelltraversal
cdupont
cdupont

Reputation: 1188

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.

Upvotes: 1

Views: 133

Answers (2)

Will Ness
Will Ness

Reputation: 71065

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.

Upvotes: 3

Daniel Wagner
Daniel Wagner

Reputation: 152707

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

Upvotes: 1

Related Questions