4

二分木で可能なすべてのサブツリーを見つける必要があります。

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

ツリーは次のとおりです。

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

whileHaskell は初めてで、Haskell には⁄forループがないことを知っています。Haskell は再帰がすべてです。私の質問は、無限再帰なしでツリーのすべての可能なサブツリーを取得する方法ですか?

4

5 に答える 5

3

ユニプレートのデモはすでにあるので、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]

基本ファンクターのボイラープレートは大きいですが、比較的驚くことではなく、タイプごとに 1 回であるため、長期的には労力を節約できます。

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アプローチは簡潔 (1 つのタイプに対して多くの異なるトラバーサルが必要な場合) であり、柔軟 (トラバーサルの順序、空のサブツリーを含めるかどうかなどを完全に制御できます) の両方であることに注意してください。欠点の 1 つは、 の型paraやその他のスキームが一般的すぎて型の推論ができないことです。

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 に答える