尝试实现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的所有路径。