在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值的容器.