Markieren von Bäumen in Haskell

Question

Ich habe einen arbiträre Baum und möchte ihn in einen Baum von ganzen Zahlen umwandeln, die ursprünglichen Werte sollten durch ganze Zahlen ersetzt werden. Derselbe Wert muss bei jedem Auftreten durch die gleiche Zahl ersetzt werden.

Funktion für Baum durchquert vorgesehen ist, und dies ist meine Etikettierfunktion

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

Ich glaube, dass ich einen Stapel benötigen Etiketten zu speichern, aber ich bin nicht sicher, wie es anzuwenden würde jede Führung sein

geschätzt

Answer 1

Wenn Sie eine Traversal-Funktion haben

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

wie von der Traversable typeclass gegeben, dann sind Sie ha in voller ve f ~ State (Store a Int), so

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

so sollten Sie nur in der Lage sein traverse label zu Ihrem Baum anzuwenden, dann diesen Zustand Aktion ausführen Ihre markierten Baum zu bekommen, so wäre es

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

I‘ Als Argument zur Verfügung gestellt labelStore, weil es wünschenswert sein kann, diese Funktion mit einer Reihe von vorhandenen Etiketten zu liefern, und weil es nicht klar ist, wie man eine neue Store konstruieren.

Allerdings werde ich darauf hinweisen, dass es nichts Besonderes sogar einen Baum hier verwendet wird, jede Traversable würde ausreichen, so können Sie diese auf Listen anwenden könnten, Map s, benutzerdefinierte Typen, oder was auch immer, vorausgesetzt, es ist ein Traversable Behälter Halten Ord a => a Werte.