Versuch Pfad Rekord für Haskell Suche Binärbaum

Question

Ich habe das Spiel mit binären Bäumen in Haskell zu implementieren, und ich bin versucht, eine dfs Variante zu implementieren, die den Weg zurück (bestehend aus einem linken und Rechten) vom Wurzelknoten zu der Knoten, der den gesuchten Wert enthält. Ich denke, es wäre am besten, einen Maybe Directions Typ zurückzugeben.

Hier ist, was bisher umgesetzt wurde.

aber ich habe keine Ahnung, wie man es den gesamten Baum durchlaufen lässt. Ich habe das Gefühl, dass ich zu zwingend denke.

Answer 1

Ihre Idee Maybe Direction zu verwenden ist gut. Ich würde umschreiben Ihre Funktion wie folgt:

inTree :: (Eq a) => a -> Tree a -> Maybe [Direction] 
inTree val Empty = Nothing 
inTree val (Node x l r) 
    | val == x = Just [] 
    | otherwise = (fmap (L:) (inTree val l)) <|> (fmap (R:) (inTree val r)) 

fmap ing eine Funktion f auf einem Maybe Ergebnisse in Nothing wenn der ursprüngliche Wert ist Nothing und Just (f v) wenn es Just v ist. In unserem Fall, wenn der rekursive Aufruf den Wert gefunden (es ist also zurückkehr einen Pfad Just [Direction]) wir fügen Sie die Direction wir am aktuellen Knoten nahmen.

Der <|> Betreiber kommt aus dem Alternative instance of Maybe. Es ist eine linke voreingenommene Wahl auf Mayben. Hier verwenden wir es, um den Teilbaum auszuwählen, der zurückgegeben hat (falls es welche gab).

Eine gute Übung ist, den Code so zu modifizieren, dass sie alle die Pfade zu den x s im Baum zurück.