4

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

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

树是：

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

我是 Haskell 的新手，我知道 Haskell 中没有while⁄for循环。Haskell 是关于递归的。我的问题是，如何在没有无限递归的情况下获得树的所有可能子树？

4

5 回答 5

6

bheklilr 为您提供了对您问题的一种解释的答案，但这就是我作为初学者将告诉您的内容，他们将从自己解决问题中受益：

首先确保你已经清楚地定义了你想要你的函数做什么。我假设你希望它像tails.

然后以声明的方式思考，您的=-sign 表示“是”，并编写两个语句。第一个应该阅读“allSubtrees树Empty的......”（这是你的基本情况）：

allSubtrees Empty = ...

然后你的递归案例，阅读“ allSubtreesa Nodeis ...”：

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

如果您对此无法理解，请尝试编写一个适用于 的递归函数，Node Empty 1 Empty然后对其进行泛化。

于 2013-08-29T21:09:01.647 回答
3

Uniplate 是你的朋友，在这里：

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Generics.Uniplate.Data (universe)
import Data.Data (Data)
import Data.Typeable (Typeable)

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


allSubtrees :: (Data a, Typeable a) => BinaryT a -> [BinaryT a]
allSubtrees = universe
于 2013-08-29T21:08:02.947 回答
3

由于 Uniplate 演示已经存在，recursion-schemes为了完整起见，这里是一个使用库的实现：

{-# LANGUAGE DeriveFunctor, TypeFamilies #-}
import Data.Functor.Foldable

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

data BinaryTBase a b 
    = BaseEmpty 
    | BaseNode b a b
    deriving (Functor)

type instance Base (BinaryT a) = BinaryTBase a

instance Foldable (BinaryT b) where
    project Empty = BaseEmpty
    project (Node a b c) = BaseNode a b c 

instance Unfoldable (BinaryT b) where
    embed BaseEmpty = Empty
    embed (BaseNode a b c) = Node a b c 

allSubtrees :: BinaryT a -> [BinaryT a]     
allSubtrees = para phi where
    phi BaseEmpty = []
    phi (BaseNode (l, ll) v (r, rr)) = ll ++ rr ++ [Node r v l]

基本仿函数样板很大，但相对不足为奇，并且从长远来看可能会节省您的精力，因为它是每种类型一次。

这是另一个使用geniplate库的实现：

{-# LANGUAGE TemplateHaskell #-}
import Data.Generics.Geniplate

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

allSubTrees :: BinaryT a -> [BinaryT a]
allSubTrees = $(genUniverseBi 'allSubTrees)

这是@bheklilr 显式递归方法的缩短版本，人们可能期望新手（我用于(++)对称）：

allSubTrees3 :: BinaryT a -> [BinaryT a]
allSubTrees3 Empty = []
allSubTrees3 this @ (Node left _ right) = [this] ++ leftSubs ++ rightSubs where
    leftSubs = allSubTrees3 left
    rightSubs = allSubTrees3 right

请注意，它列出了根但不列出空子树，但它很容易更改。

我想知道不同方法的优缺点是什么。与其他方法相比，在uniplate某种程度上或多或少是类型安全的吗？

请注意，该recursion-schemes方法既简洁（如果您需要对一种类型进行许多不同的遍历）又灵活（您可以完全控制遍历顺序，是否包含空子树等）。一个缺点是 type ofpara和其他方案过于笼统而无法进行类型推断，因此通常需要类型签名来消除歧义。

geniplate似乎比 更具侵入性uniplate，因为不需要放置deriving子句。

于 2013-08-29T23:02:27.193 回答
2

你可以很容易地使用递归来解决这个问题。可能比使用循环更容易。

allSubTrees :: BinaryT a -> [BinaryT a]
allSubTrees Empty = []
allSubTrees (Node Empty n Empty) = []
allSubTrees (Node Empty n right) = right : allSubTrees right
allSubTrees (Node left n Empty) = left : allSubTrees left
allSubTrees (Node left n right) = left : right : leftSubs ++ rightSubs
    where
        leftSubs = allSubTrees left
        rightSubs = allSubTrees right
于 2013-08-29T21:00:15.683 回答
1

除了 nponeccop 的解决方案之外，这里是树的广度优先遍历（对于拟态是不可能的；确实需要共同递归）：

{-# LANGUAGE DeriveFunctor, TypeFamilies #-}
import Data.Functor.Foldable

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

allSubtrees :: BinaryT a -> [BinaryT a]
allSubtrees t = ana phi [t] where
    phi [] = Nil
    phi (Empty:t) = Cons Empty t
    phi (n@(Node l v r):t) = Cons n (t++(l:[r]))

main = print $ allSubtrees $ 
       Node (Node Empty "a" Empty) "b" (Node (Node Empty "c" Empty) "d" Empty)
于 2013-08-30T07:40:15.347 回答