Haskell - 找到节点值的路径

Question

这道题的题目是:

Tree holds data of type a. Function findpath which given a function f, some data x and a tree t, returns the lists of paths (possibly empty) in t to the nodes of the form Node d where f d is equal to x.

此问题中使用的数据类型的声明结构:

data Btree a = ND | Data a |  Branch (Btree a) (Btree a)
           deriving (Show,Eq)

data Dir = L | R 
       deriving (Show,Eq)

type Path =  [Dir]

我尝试解决这个功能:

findpath :: Eq b => (a -> b) -> b -> Btree a -> [Path]
findpath f x (Data d)                = [[]]
findpath f x ND                      = [[]]
findpath f x (Branch (Data d) right) = [[L]] ++ (findpath f x right)
findpath f x (Branch left (Data d))  = [[R]] ++ (findpath f x left)

用于测试的数据:

tree1 = Branch ND ND
tree2 = Branch ND (Data 3)
tree3 = Branch tree1 tree2

测试函数的函数调用:

1. findpath (2*) 3 tree2
2. findpath (2*) 2 tree2
3. findpath (2*) 3 tree1

它给出的输出是:

1. [[R],[]]
2. [[R],[]] - incorrect
3. Throws exception

如果您对 findpath 函数有任何帮助，我们将不胜感激。

Answer 1

让我们一次只看一个案例，完全使用 Btree 的数据定义中的案例.也就是说，由于

data Btree a = ND | Data a | Branch (Btree a) (Btree a)

那么我们将准确地考虑以下形状的树，而不考虑其他形状:

1. ND
2. Data d
3. Branch l r

让我们开始吧。

findpath f x ND = {- TODO -}

记忆规范:

Function findpath which given a function f, some data x and a tree t, returns the list of paths (possibly empty) in t to the nodes of the form Data d where f d is equal to x.

(我假设你在哪里写了“节点 d”，你的意思是“数据 d”，以符合你对树的定义，并将“列表”更改为“列表”。)

在当前情况下，我们有 f和 x如上所述，和t = ND .在我们应该返回的描述中替换这些，我们得到:

the list of paths in ND to the nodes of the form Data d where ...

自 ND不包含 Data d 形式的任何节点, 没有这样的路径。所以:

findpath f x ND = []

下一个案例:

findpath f x (Data d) = {- TODO -}

现在我们有 t = Data d .再次修改规范，必须返回

the list of paths in Data d to the nodes of the form Data d where f d is equal to x.

好吧，那么我们必须检查是否f d等于x还是不是，嘿？

findpath f x (Data d) = if f d == x
    then {- TODO -}
    else {- TODO -}

如果f d == x ，那么只有一条路径到达 Data d 形式的节点，其中 f d 等于 x —— 即空路径。如果不是f d == x ，那么就没有这样的路径。所以:

findpath f x (Data d) = if f d == x
    then [[]]
    else []

最后一个案例:

findpath f x (Branch l r) = {- TODO -}

再次修订规范，现在使用 t = Branch l r , 我们必须返回

the list of paths in Branch l r to the nodes of the form Data d where f d is equal to x.

现在你可能觉得有点卡住了。毕竟，l和 r如此普遍，以至于很难知道是否有路径进入它们到 Data d 形式的节点，对吗？那么你怎么能发现是否有通往Branch l r的路径呢？最终在 Data d 节点结束？当然，如果只有一种方法可以找到这两个子问题的答案，也许我们可以扩充这些路径，嘿？

幸运的是，我们有一个函数可以回答子问题:findpath本身。因此，让我们回答子问题，然后考虑该怎么做。

findpath f x (Branch l r) = {- TODO -} where
    pathsInL = findpath f x l
    pathsInR = findpath f x r

好的，所以我们在树中有一些路径 l导致形式为 Data d 的节点其中 f x等于d (分别是树中的一些路径 r )。我们如何将这些路径转换为树中的路径 Branch l r ？简单:通过添加 L (分别为 R )到每个路径。然后我们可以将这两个路径集合组合在一起。

在这一点上，我将停止提供代码:我认为你缺少的关键洞察力应该已经在上面提供的递归框架中。但是，我会建议一些您可能会在充实骨架的最后一点点时发现有用的功能:

1. (:)可用于添加一个新的 Dir到 Path .
2. map可用于升级修改单个 Path 的函数变成一个修改整个列表的 Path s.
3. (++)可用于连接 Path 的两个列表s，生成一个列表，其中包含其两个参数中每个参数的所有元素。

试一试，让我们知道您接下来会遇到什么困难!