嘗試實現Haskell二叉樹搜索的路徑記錄

Question

我一直在玩Haskell中的二叉樹，我試圖實現一個dfs變體，它從根節點返回路徑（由左和右）組成包含搜索值的節點。我認爲最好是返回Maybe Directions類型。

這是迄今爲止已實施的內容。

data Tree a = Empty | Node a (Tree a) (Tree a) 
    deriving (Show, Eq) 

data Direction = L | R 
    deriving (Show) 
type Directions = [Direction] 

inTree :: (Eq a) => a -> Tree a -> [Direction] 
inTree val (Node x l r) 
    | val == x = [] 
    | l /= Empty = L:(inTree val l) 
    | r /= Empty = R:(inTree val r) 
    | otherwise = 

但我不知道如何讓它遍歷整個樹。我感覺好像我可能在思考過於強制。

Answer 1

您的想法使用Maybe Direction是好的。我想如下重寫你的函數：

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上Maybe結果荷蘭國際集團功能f在Nothing如果原始值是Nothing和Just (f v)如果是Just v。在我們的情況下，如果遞歸調用找到該值（因此它返回路徑Just [Direction]），我們附加我們在當前節點處獲得的Direction。

<|>運營商來自Alternative instance of Maybe。這是對maybes的左傾選擇。在這裏，我們用它來選擇返回Just [Direction]（如果有的話）的子樹。

一個很好的練習是修改代碼，使其返回到樹中的x s的所有路徑。