haskell - 用二叉树中的数据记录所有路径

Question

我正在尝试编写一个函数，在该函数中记录所有通向数据 N 的路径。

任何人都可以在我感到困惑时给我一些指示，我什么时候记录路径？就好像我从头开始一样，我最终可能会找到通向何处的路径。 (记录路径为 L | R)

谁能给我一些逻辑!

谢谢

我已经在给定路径的树上工作过，但我无法弄清楚

data Tree = N | F Tree Tree deriving Show
data Dir = L | R deriving Show
type Path = [Dir]       

所以一棵树可能是 F N (F (F N N) (F N (F N N)))路径是 [L,L,L,R]
我已经做了一些函数来插入有 N 个节点的地方或给定的路径。

但我无法理解记录路径的逻辑。

Answer 1

main = print . findAllLeaves $ F N (F (F N N) (F N (F N N)))

data Tree = N | F Tree Tree deriving Show
data Dir = L | R deriving Show
type Path = [Dir]    

descend :: Tree -> Dir -> Tree
descend (F l _) L = l
descend (F _ r) R = r
descend _ _ = undefined

findAllLeaves :: Tree -> [Path]
findAllLeaves N = [[]]
findAllLeaves tree = do dir <- [L, R]
                        map (dir:) $ findAllLeaves (descend tree dir)

结果

[[L],[R,L,L],[R,L,R],[R,R,L],[R,R,R,L],[R,R,R,R]]

我使用 list monad 来“同时”选择 L 和 R，并下降两个分支。必须喜欢不确定性!

解释:

我希望 descend 足够清楚。你给它一棵树和一个方向，它就会沿着那个方向从树上下来。
findAllLeaves 很有趣。它是如何工作的？

我们将在一分钟内讨论基本情况 findAllLeaves N = [[]] 。

递归情况写在列表 monad 中，使用 do 表示法。第一行很简单:选择 L 或 R 并将其分配给 dir 。 列表 monad 实际上会同时选择两者，并获取每个的结果并将它们连接在一起。 这是他们理解的关键。这正是您所要求的:以 L 开头的所有路径是什么，以 R 开头的所有路径是什么？将它们放在一起，您就拥有了从当前节点到其后代叶节点的所有路径。

从上一段的描述中，第二行应该相当清楚。沿给定方向 ( descend tree dir ) 下降树，找到该点 ( findAllLeaves ) 的所有叶子，然后将选择的方向添加到每个子路径 ( map (dir:) )。

那么为什么基本情况是 [[]] 呢？好吧，考虑一下基本案例上方的案例。因此，例如， findAllLeaves (F N N) 。当我们选择 dir = L 时，我们评估第二行:

map (L:) $ findAllLeaves (descend (F N N) L)

向左下降只给我们 N

map (L:) $ findAllLeaves N

然后我们找到了基本情况:

map (L:) $ [[]]

现在你明白为什么我们有那个奇怪的基本情况了吗？一个里面有一个空列表的列表？因为我们要将 (L:) 映射到它上面，换句话说，将 L 添加到外部列表中的每个列表。这导致:

[[L]]

当 dir = R 时，我们得到类似的结果。

[[R]]

那么列表 monad 将它们连接在一起

[[L]] ++ [[R]]

我们最终得到

[[L], [R]]

如果其中任何一个仍然不清楚，请在评论中告诉我，我会尽力澄清。