在 haskell 中标记树

Question

我有一棵任意树，想把它变成一棵整数树，原来的值应该用整数代替。必须在每次出现时用相同的数字替换相同的值。

提供了遍历树的功能，这是我的标注功能

label :: Ord a => a -> State (Store a Int) Int

我想我需要一个堆栈来存储标签，但我不确定如何应用它 , 任何指导将不胜感激

Answer 1

如果你有遍历功能

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

由 Traversable 类型类给出，那么你有 f ~ State (Store a Int)，所以

traverse label :: (Ord a, Traversable t) => t a -> State (Store a Int) (t Int)

所以你应该能够将 traverse label 应用于你的树，然后执行该状态操作以获得你的标记树，所以完整的它会是

labelTree :: (Tree t, Ord a) => t a -> Store a Int -> (t Int, Store a Int)
labelTree tree labelStore = runState (traverse label tree) labelStore

我提供了 labelStore 作为参数，因为可能需要为该函数提供一组现有标签，并且不清楚如何构建新的 Store .

但是，我要指出的是，即使在这里使用树也没有什么特别之处，任何 Traversable 就足够了，因此您可以将其应用于列表、Map、自定义类型，或其他任何东西，前提是它是一个 Traversable 容器，其中包含 Ord a => a 个值。