建立树中所有分支的列表 [英] Building a list of all branches in a tree

问题描述

我需要使函数从树中返回所有可能的分支 格式如下:

I need to make function returns all possible branches from a tree with this form:

data Tree a = EmptyT | NodeT a ( Tree a ) ( Tree a ) deriving (Show)

everyBranch :: Tree a -> [[a]]

我不确定该如何处理... xD 我仍然是Haskell的新手.

I'm not sure how to approach this... xD I'm still a newbie in Haskell.

让我说:

            1
           / \
          2   3
         /\  / \
        4  5 7  8

我想获得:[[1,2,4], [1,2,5], [1,3,8], [1,3,7]]

推荐答案

我们将使用递归方法.让我们从一个粗略的骨架开始:

We'll use a recursive approach. Let's start with a rough skeleton:

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v (Tree l) (Tree r)) = _somethingElse

现在，我们将填补漏洞. (此语法称为类型化的孔":如果您通过GHC运行上述程序，则会向您显示一条错误消息，其中应包含该孔中的值的类型.)现在，我不确定第一种情况:根据您的需要，它可能是[](无分支)或[[]](一个无元素的分支)，因此我们稍后再讲.对于第二种情况，我们需要一种方法来构造给定v alue以及l eft和r ight子树的分支列表.我们该怎么做?我们将递归地找到l eft树中的每个分支，以及r ight树中的每个分支，然后我们将v放在这两个前缀之前:

Now we'll fill in the holes. (This syntax is known as 'typed holes': if you run the above program through GHC, it will give you an error message with the type of the value which should be in the hole.) Now, I'm not sure about the first case: depending on your need, it could be [] (no branches) or [[]] (one branch with no elements), so we'll come back to this later. For the second case, we need a way to construct a list of branches given the value and the left and right subtrees. How do we do that? We'll recursively find every branch in the left tree, and every branch in the right tree, and then we'll prepend v to both:

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v l r) = map (v:) $ everyBranch l ++ everyBranch r

现在，让我们回到EmptyT.考虑一个非常简单的树:NodeT 1 EmptyT EmptyT.在这种情况下，everyBranch应该返回[[1]].让我们在此树上手动调用everyBranch:

Now, let's go back to EmptyT. Consider a very simple tree: NodeT 1 EmptyT EmptyT. In this case, everyBranch should return [[1]]. Let's invoke everyBranch 'by hand' on this tree:

(我用└→表示递归评估子表达式"，而=>表示表达式评估为")

(I use └→ to mean 'evaluate sub-expression recursively', and => meaning 'expression evaluates to')

everyBranch (NodeT 1 EmptyT EmptyT)
=> map (1:) $ everyBranch EmptyT ++ everyBranch EmptyT
   └→ everyBranch EmptyT
      => _something
=> map (1:) $ _something ++ _something

所以在这里，我们希望map (1:) $ _something ++ _something等于[[1]].什么是_something?好吧，事实证明，如果_something是[]，那么map (1:) $ [] ++ []是[]，这不是我们想要的.另一方面，如果_something是[[]]，则map (1:) $ [[]] ++ [[]]是[[1], [1]]-这也不是我们想要的.看来我们需要一种略有不同的方法.我们要做的是，我们将专门为此类树添加另一种情况:

So here, we want map (1:) $ _something ++ _something to be equal to [[1]]. What is _something? Well, it turns out that if _something is [], then map (1:) $ [] ++ [] is [], which isn't what we want. On the other hand, if _something is [[]], then map (1:) $ [[]] ++ [[]] is [[1], [1]] - which isn't what we want either. It looks like we need a slightly different approach. What we'll do is, we'll add another case specifically for these sort of trees:

everyBranch :: Tree a -> [[a]]
everyBranch EmptyT = _something
everyBranch (NodeT v EmptyT EmptyT) = [[v]]
everyBranch (NodeT v l r) = map (v:) $ everyBranch l ++ everyBranch r

现在，如果我们对此进行一点测试(尽管使用_something的一些随机值来阻止它给我们带来错误)，我们会发现它适用于所有二叉树.如前所述，我们仍然需要弄清楚_something的值.此值仅在两种情况下才有意义:空树(在这种情况下它将与EmptyT轻松匹配)和仅具有一个子树的树(在这种情况下l或r将与EmptyT匹配).我将把它作为练习，让您确定要放置在其中的值，它将如何影响结果以及为什么会以这种方式影响结果.

Now, if we test this a bit (albeit using some random value for _something to stop it from giving us errors), we find that it works for all binary trees. As mentioned though, we still need to figure out that _something value. This value will only matter in two cases: empty trees (in which case it will trivially match EmptyT), and trees with only one subtree (in which case either l or r will match EmptyT). I will leave it as an exercise for you to determine what value to put there, how it will affect the result, and why it affects it that way.

这篇关于建立树中所有分支的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！