I have an arbitrary tree and want to transform it into a tree of integers, the original values should be replaced by integers. The same value has to be replaced by the same number at every occurrence.
function for traversing tree is provided, and this is my labeling function
label :: Ord a => a -> State (Store a Int) Int
I believe i need a stack to store labels, but i'm not sure how to apply it , any guidance would be appreciated
If you have a traversal function
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
as given by the Traversable typeclass, then you have f ~ State (Store a Int), so
traverse label :: (Ord a, Traversable t) => t a -> State (Store a Int) (t Int)
so you should just be able to apply traverse label to your tree, then execute that state action to get your labeled tree, so in full it would be
labelTree :: (Tree t, Ord a) => t a -> Store a Int -> (t Int, Store a Int)
labelTree tree labelStore = runState (traverse label tree) labelStore
I've provided labelStore as an argument because it may be desirable to provide this function with a set of existing labels, and because it isn't clear how to construct a new Store.
However, I'll point out that there's nothing special about even using a tree here, any Traversable would be sufficient, so you could apply this to lists, Maps, custom types, or whatever, provided it's a Traversable container holding Ord a => a values.