zu geordneten Sequenz Werte eines Baumes Blatt ändern, während die Struktur des Baumes Erhaltung

Question

Gegeben ist eine rekursive Strukturbaum

data Tree = Leaf Int | Node Tree Tree deriving Show 

Ich möchte es in einer Art und Weise normalisieren, dass der Baum die Struktur bewahrt, macht aber die ganzen Zahlen an die Blätter folgen in Tiefen erster Ordnung. Wie kann ich das erreichen? Mein aktueller Setup-Code sieht wie folgt aus:

myTree = Node (Leaf 3) (Node (Leaf 5) (Leaf 2)) 

myTree' = normalize myTree 

-- preserve tree structure, but make Ints sequential in depths-first traversal 
normalize :: Tree -> Tree 
normalize = id -- todo: implement 

main = do 
    print myTree -- prints  : Node (Leaf 3) (Node (Leaf 5) (Leaf 2)) 
    print myTree' -- should print: Node (Leaf 1) (Node (Leaf 2) (Leaf 3)) 

Answer 1

Monaden Ohne verwenden, können Sie eine Funktionszuordnung Bäume, die bestimmten Zustand

mapLRS :: (s -> Int -> (s, Int)) -> s -> Tree -> (Tree, s) 
mapLRS f s (Leaf x ) = 
    let (s', x') = f s x 
    in (Leaf x', s')     -- the mapped leaf and the new state 
mapLRS f s (Node l r) = 
    let (l', s') = mapLRS f s l  -- the mapped left branch and the new state 
     (r', s'') = mapLRS f s' r  -- the mapped right branch and the new state 
    in (Node l' r', s'') 

jetzt schreiben

normalize :: Tree -> Tree 
normalize = fst . mapWithStateLeftRight (\s _ -> (s + 1, s)) 1 

Monaden verwenden könnte besser lesbar (f ist nicht der Einfachheit halber mit state identisch)

import Control.Monad.State 

mapLRS :: (s -> (Int, s)) -> Tree -> State s Tree 
mapLRS f (Leaf x) = Leaf <$> state f 
mapLRS f (Node l r) = Node <$> mapLRS f l <*> mapLRS f r 

normalize :: Tree -> Tree 
normalize tree = evalState (mapLRS (\s -> (s, s + 1)) tree) 1 

Answer 2

Der üblicher Weg, dies zu tun ist, um die aktuelle Bezeichnung in einem Zustand Monade aufnehmen:

import Control.Monad.State 

data Tree = Leaf Int | Node Tree Tree deriving (Show) 

normalize :: Tree -> Tree 
normalize t = evalState (go t) 1 where 

    go :: Tree -> State Int Tree 
    go (Leaf _) = Leaf <$> (get <* modify (+1)) 
    go (Node l r) = Node <$> go l <*> go r 

Diese Lösung initialisiert der Zustand 1, durchquert dann den Baum und auf jedem begegnete Leaf es setzt das aktuelle Label in der zurückgegebenen Leaf und erhöht die Bezeichnung.

Alternativ können wir die Traversable Instanz für Tree ableiten:

{-# language DeriveFunctor, DeriveFoldable, DeriveTraversable #-} 

import Control.Monad.State 

data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Show, Functor, Foldable, Traversable) 

normalize :: Tree a -> Tree Int 
normalize = (`evalState` 1) . traverse (\_ -> get <* modify (+1)) 

Dies funktioniert auf die gleiche Art und Weise, aber das zur Kenntnis, dass es auf der Tatsache beruht, dass die abgeleitete Traversable Instanz das Recht Traversierfolgeliste hat. Natürlich, wenn wir eine andere Reihenfolge wollten, müßten wir unsere eigenen Traversalen schreiben.