构建树中所有分支的列表 [英] 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

现在我们将填补漏洞.(这种语法被称为typedholes":如果你通过 GHC 运行上面的程序，它会给你一条错误消息，其中包含应该在洞中的值的类型.)现在，我不确定第一种情况:根据您的需要，它可以是 [](没有分支)或 [[]](一个没有元素的分支)，所以我们会回来到这个以后.对于第二种情况，我们需要一种方法来构造给定 value 和 left 和 right 子树的分支列表.我们怎么做?我们将递归地找到 left 树中的每个分支，以及 right 树中的每个分支，然后我们将在 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屋！