Haskell: Wie reverse ich die Kinder eines Baumes rekursiv

Question

Ich versuche, die Kinder eines Baumes in Haskell umzukehren. Der Baum sieht wie folgt aus:

data Tree v e = Node v [(e,Tree v e)] 

Im Moment habe ich es mit diesen beiden Funktionen zu tun:

rev :: Tree v e -> Tree v e 
rev (Node v []) = Node v [] 
rev (Node v xs) = 
    let xs' = (rev'(snd (unzip xs))) 
    in Node v (zip (fst (unzip xs)) (map rev xs')) 


rev' :: [Tree v e] -> [Tree v e] 
rev' [] = [] 
rev' (x:xs) = (rev' xs) ++ [x] 

Ich bin nicht einmal sicher, ob dies zu 100% funktioniert. Gibt es eine Möglichkeit, es in nur einer Funktion rekursiv zu machen? Ich fühle mich wie mein Weg ist ineffizient. Ich habe versucht, eine Funktion zu schreiben, die wie folgt aussieht:

revRec :: Tree v e -> Tree v e 
revRec (Node v [])  = Node v [] 
revRec (Node v (x:xs)) = Node v (revRec xs ++ [x]) 

obviosuly kann ich nicht nennen revRec mit xs seit xs eine Liste. Ich kann mich nicht um dieses Problem kümmern, obwohl ich das Gefühl habe, dass es nicht so schwer sein könnte.

Answer 1

Zeroth, bereinigen Sie Ihren Code. Sie brauchen nicht so viele Parens, und Sie sollten doppelte Berechnungen vermeiden. und snd auf zweimal die gleiche Sache? Meh. Bessere Nutzung Mustervergleich:

rev :: Tree v e -> Tree v e 
rev (Node v xs) 
    = let (es, cs) = unzip xs 
     xs' = rev' cs 
    in Node v $ zip es (map rev xs') 

rev' :: [Tree v e] -> [Tree v e] 
rev' [] = [] 
rev' (x:xs) = rev' xs ++ [x] 

Erste beachten Sie, dass rev' nicht spezifisch für Listen von Bäumen ist, überhaupt nicht! Es ist nur ^{_{eine ineffiziente Implementierung von}} der Standard reverse Funktion, die auf jeder Liste funktioniert.

Sekunde, ist das Entpacken/Zippen ein bisschen ungeschickt. Sind Sie sicher, dass dies tatsächlich das Verhalten ist, das Sie wollen: Im Moment kehren Sie nur die Liste der Kinder um, aber die Reihenfolge Elemente bleibt gleich. Wenn nicht, dann sollten Sie besser tun es alle mit einem Rückwärts und eine Karte:

rev :: Tree v e -> Tree v e 
rev (Node v xs) = Node v . reverse $ map (\(e,c) -> (e, rev c)) xs 

oder, noch schöner,

import Control.Arrow 

rev (Node v xs) = Node v . reverse $ map (second rev) xs