0

だから私はバイナリツリーを受け入れ、すべてのサブツリーのリストを返す関数を Haskell に実装しようとしています。これが私のコードです：

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

subtrees :: BinTree a -> [BinTree a]
subtrees Empty = [Empty]
subtrees (Node tL x tR) = [Node tL x tR] ++ subtrees tL ++ subtrees tR

ここに私のデータセットがあります

(Node (Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty) 4 (Node Empty 2 Empty))

これが私の結果です

[Node (Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty) 4 (Node Empty 2 Empty),
Node (Node (Node Empty 1 Empty) 1 Empty) 3 Empty,Node (Node Empty 1 Empty) 1 Emp
ty,Node Empty 1 Empty,Node Empty 2 Empty]

何らかの理由で、私はこの実装にやや疑問を持っています。フィードバックをいただければ幸いです。ありがとう！

4

2 に答える 2

1

私の意見では、このようなものをテストする最良の方法は、関数が満たすと予想されるプロパティを考えてから、いくつかの QuickCheck テストを記述してそれらを試すことです。QuickCheck の最も優れた点は、問題が見つかった場合に、失敗する可能性のある最も単純なケースを教えようとすることです。それでは始めましょう...

{-# LANGUAGE FlexibleInstances #-}

import Test.QuickCheck
import Control.Applicative

テストするのに適したプロパティは何ですか? 2 つのツリー t1 と t2 があり、それらを新しいノードと結合すると、結合されたツリーを呼び出すと、 、、およびツリー全体subtreeを含むリストが得られます。ノードの種類はロジックに影響しないので、Char を選択しました。おそらく、このプロパティのより良い名前を考えることができます。subtree t1subtree t2

prop_combining_works :: BinTree Char -> Char -> BinTree Char -> Property
prop_combining_works t1 x t2 =
  property $ subtrees t == t : subtrees t1 ++ subtrees t2
  where t = Node t1 x t2

注: 何らかの方法で結果を並べ替えずにこれが機能するとは思っていませんでしsubtreeたが、幸いなことに、そうです。しかし、あなたがどのように戻ることにしたかによって、それは変わるかもしれませんsubtree Empty! また、式の右側の重複を排除する必要がある場合もあります==。

次に、テスト用のランダム ツリーを生成する方法が必要です。以下のコードは複雑に見えるかもしれませんが、それが言っているのは、BinTree型のテスト データがEmpty、またはNode任意に選択された 2 つのサブツリーと任意に選択された のいずれかである可能性があるということCharです。

instance Arbitrary (BinTree Char) where
  arbitrary = do
    oneof [return Empty, Node <$> arbitrary <*> arbitrary <*> arbitrary]

これをコードに追加して、QuickCheck を実行します。

λ> quickCheck prop_combining_works
Loading package QuickCheck-2.6 ... linking ... done.
+++ OK, passed 100 tests.

これで、テストする他のプロパティを考えることができます。

于 2013-09-02T17:26:07.117 に答える