试图为Haskell二叉树搜索实现路径记录 [英] Trying to implement path record for Haskell binary tree search

问题描述

我一直在Haskell中使用二叉树，我试图实现一个dfs变体，它从根节点返回包含搜索值的节点的路径（由左和权限组成）。我认为最好返回一个 Maybe Directions 类型。

这是迄今为止已经实现的功能。

 数据树a =空|节点a（树a）（树a）
导出（Show，Eq）
 
 data Direction = L | R 
 deriving（Show）
 type Directions = [Direction] 
 
 inTree ::（Eq a）=> a  - >树a  - > [方向] 
 inTree val（节点x l r）
 | val == x = [] 
 | l / =空= L：（inTree val l）
 | r / = Empty = R：（inTree val r）
 |否则= 
  

但我不知道如何遍历整个树。我感觉好像我可能在思考过于强制。 可能方向很好。我会重写你的函数，如下所示：

  inTree ::（Eq a）=> a  - >树a  - >可能[Direction] 
 inTree val Empty = Nothing 
 inTree val（Node x l r）
 | val == x = Just [] 
 |否则=（fmap（L :)（inTree val l））< |> （fmap（R :)（inTree val r））
  

fmap 一个函数 f 在可能结果 Nothing 没有和 Just（fv），如果它是 v 。在我们的例子中，如果递归调用找到值（所以它返回一个路径只是[方向] ），我们追加方向

$ b < |> 运算符来自 可选 可能 的实例。这是对maybes的左倾选择。这里我们用它来选择返回的子树。只需[方向] （如果有的话）。

A良好的练习是修改代码，以便它返回到树中的 x s的所有路径。

I've been playing around with binary trees in Haskell, and I am attempting to implement a dfs variant that returns the path (composed of left and rights) from the root node to the node containing the value searched for. I think it would be best to return a Maybe Directions type.

Here is what has been implemented so far.

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 = 

but I have no idea how to have it traverse the entire tree. I feel as though I might be thinking too imperatively.

解决方案

Your idea to use Maybe Direction is good. I would rewrite your function as follows:

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))

fmaping a function f on a Maybe results in Nothing if the original value is Nothing and Just (f v) if it's Just v. In our case if the recursive call found the value (so it's returning a path Just [Direction]) we append the Direction we took at the current node.

The <|> operator comes from the Alternative instance of Maybe. It's a left biased choice on maybes. Here we use it to pick the subtree which returned Just [Direction] (if there was any).

A good exercise is to modify the code so that it returns all the paths to the xs in the tree.

这篇关于试图为Haskell二叉树搜索实现路径记录的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！