Haskell: Traversal on a Map

Question

我正在寻找一个具有此签名的函数:

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

你给它一个起始键，一个函数和一个映射。

它将提取位于Map中位置k的元素，并将该元素提供给函数。基于此，该函数将返回另一个键以供下一步查看。

这是过滤器和遍历的混合，元素本身给出了下一个打开的位置。结果是遍历的元素列表。可以比原地图短。

编辑:考虑到注释

Answer 1

由于所有查找都是在原始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

之类的

您必须根据您选择的lookupNN函数之一来实现at函数。

它不是一个过滤器，因为它必须在f产生的第一个Nothing时停止。

Answer 2

不存在具有该签名和行为的函数。你得自己写。