如何在Haskell中找到二叉树的所有可能子树？

Question

我需要在二叉树中找到所有可能的子树:

allSubtrees :: BinaryT a -> [BinaryT a]
allSubtrees = undefined

树是:

data BinaryT a =
    Empty
  | Node (BinaryT a) a (BinaryT a)
  deriving (Eq, Show)

我是Haskell的新手,我知道Haskell中没有while/ forloop.Haskell就是递归.我的问题是,如何在没有无限递归的情况下获得树的所有可能的子树？

Answer 1

bheklilr给出了对你的问题的一种解释的答案,但这就是我作为一个初学者会告诉你的,他自己会解决这个问题:

首先要确保你已经明确定义了你想要的功能.我假设你想要它的工作方式tails.

然后以声明的方式思考,你的=-sign意味着"是",写下两个陈述.首先应阅读" allSubtrees的的Empty树......"(这是你的基本情况):

allSubtrees Empty = ...

然后你的递归情况下,读" allSubtrees的Node是...":

allSubtrees (Node l a r) = ...something combining the subTrees of l and the subtrees of r

如果你不能围绕这个,请尝试编写一个正常工作的递归函数,Node Empty 1 Empty然后将其概括.