7

BST の定義が与えられ、BST のフォールドの一般化されたバージョンを使用している場合、BST が有効なものであるかどうかを確認するにはどうすればよいですか?

data(Ord a, Show a, Read  a) => BST a = Void | Node {
    val :: a,
    left, right :: BST a
} deriving (Eq,  Ord,  Read, Show)


fold :: (Read a, Show a, Ord a) => (a -> b -> b ->  b) -> b -> BST a -> b
fold _ z Void         = z
fold f z (Node x l r) = f x (fold f z l) (fold f z r)

ノード値が左サブツリーのすべての値よりも大きく、右サブツリーのすべての値よりも小さいことを確認するという考え方です。Trueこれは、ツリー内のすべてのノードに対して行う必要があります。関数bstListは、BST の (順序付けられた) 値のリストを単純に出力します。

もちろん、次のようなものは機能しません。

--isBST :: (Read a, Show a, Ord a) => BST a -> Bool
isBST t = fold (\x l r -> all (<x) (bstList l) && all (>x) (bstList r)) (True) t

たとえば、fold 関数をノードに適用すると19、all (<19) (bstList True) && all (>19) (bstList True).

BST

4

4 に答える 4

4

(型に型クラス制約を付けないでくださいdata。)

BST は、順序通りのトラバーサルが単調に増加する場合に有効です。

flatten tree = fold (\a l r -> l . (a:) . r) id tree []

ordered list@(_:rest) = and $ zipWith (<) list rest
ordered _ = True

isBST = ordered . flatten
于 2011-02-13T04:53:23.837 に答える
4

あなたの問題は、関数が左右のサブツリーを調べるときにブール値のみを返すため、情報が失われることです。したがって、サブツリーの最小値と最大値も返すように変更してください。bslist(すべての要素をチェックする必要がなくなったため、これはおそらくより効率的です)

もちろん、完了後にこれらの「補助」値を無視するラッパー関数を作成します。

于 2011-02-12T22:38:51.007 に答える
3

これをエンコードする良い方法は、Data.Foldable によって提供されるトラバーサルに頼ることです。

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
import Data.Foldable
import Data.Monoid

拡張機能を使用してそのインスタンスを自動的に派生させることができますが、Node コンストラクターのフィールドを並べ替えて、順序通りのトラバーサルを提供する必要があります。

その一方で、データ型自体の制約を排除する必要があります。それらは実際には何の利益ももたらさず、Haskell 2011 の時点で言語から削除されました (このような制約を使用する場合は、データ型ではなく、クラスのインスタンスに配置する必要があります)。

data BST a 
  = Void
  | Node
    { left :: BST a
    , val :: a
    , right :: BST a 
    } deriving (Eq, Ord, Read, Show, Foldable)

最初に、リストが厳密にソートされるとはどういう意味かを定義します。

sorted :: Ord a => [a] -> Bool
sorted [] = True
sorted [x] = True
sorted (x:xs) = x < head xs && sorted xs 
-- head is safe because of the preceeding match.

次に、上記のヘルパーがtoList提供するメソッドを使用できます。Data.Foldable

isBST :: Ord a => BST a -> Bool
isBST = sorted . toList

あなたが尋ねたように、これをより直接的に実装することもできます。データ型の誤った制約を削除したため、折り畳みの定義を簡素化できます。

cata :: (b -> a -> b -> b) -> b -> BST a -> b
cata _ z Void         = z
cata f z (Node l x r) = f (cata f z l) x (cata f z r)

ここで、カタモルフィズムの結果をモデル化するためのデータ型が必要です。これは、ノードがない ( Z)、厳密に増加するノードの範囲 ( )、またはT失敗した ( X)のいずれかです。

data T a = Z | T a a | X deriving Eq

そして、isBST直接実装できます

isBST' :: Ord a => BST a -> Bool
isBST' b = cata phi Z b /= X where
  phi X _ _ = X
  phi _ _ X = X
  phi Z a Z = T a a
  phi Z a (T b c) = if a < b then T a c else X
  phi (T a b) c Z = if b < c then T a c else X
  phi (T a b) c (T d e) = if b < c && c < d then T a e else X

これは少し面倒なので、暫定的な状態を構成する方法を少し分解した方がよいでしょう:

cons :: Ord a => a -> T a -> T a
cons _ X = X
cons a Z = T a a
cons a (T b c) = if a < b then T a c else X

instance Ord a => Monoid (T a) where
  mempty = Z
  Z `mappend` a = a
  a `mappend` Z = a
  X `mappend` _ = X
  _ `mappend` X = X
  T a b `mappend` T c d = if b < c then T a d else X

isBST'' :: Ord a => BST a -> Bool
isBST'' b = cata phi Z b /= X where
  phi l a r = l `mappend` cons a r

個人的には、おそらく Foldable インスタンスを使用するだけです。

于 2011-02-13T15:31:53.383 に答える
0

折り畳みを使用することを主張しない場合は、次のようにすることができます。

ord Void = True
ord (Node v l r) = every (< v) l && every (> v) r && ord l && ord r where
    every p Void = True
    every p (Node v l r) = p v && every p l && every p r
于 2011-02-13T06:45:03.697 に答える