tl;dr:Arbitraryデータ型で入れ子が多すぎる場合、爆発しないインスタンスをどのように記述しますか? そして、これらのインスタンスがデータ構造の真にランダムな標本を生成することをどのように保証しますか?
ランダムなツリー構造を生成し、ライブラリ コードで構造を壊した後、これらの構造の特定のプロパティをテストしたいと考えています。(NB: サブタイピング アルゴリズムの実装を書いています。つまり、型の階層が与えられた場合、型 A は型 B のサブタイプです。これは、複数の継承と初期化後の更新を階層に含めることで、任意に複雑にすることができます。これらのどちらもサポートしない古典的な方法は Schubert Numbering であり、私が知っている最新の結果は Alavi et al. 2008 です。)
次のバラの木の例を見てみましょうData.Tree。
data Tree a = Node a (Forest a)
type Forest a = [Tree a]
Arbitray の非常に単純な (そして自宅で試してはいけない) インスタンスは次のようになります。
instance (Arbitrary a) => Arbitrary (Tree a) where
arbitrary = Node <$> arbitrary <$> arbitrary
型制約に従ってa既にインスタンスがあり、これもインスタンスであるため、インスタンスがあるため、これは簡単に思えます。非常に明白な理由で (通常は) 終了しません: 生成するリストが任意に長いため、構造が大きくなりすぎて、メモリに収まらない可能性が高くなります。さらに保守的なアプローチ:ArbitraryForest[]
arbitrary = Node <$> arbitrary <*> oneof [arbitrary,return []]
同じ理由で、再び機能しません。リストの長さを抑えるために size パラメーターを微調整することもできますが、それでも終了を保証するものではありません。これは、まだ複数の連続したサイコロが振られているためです。子供。）
つまり、ツリー全体のサイズを制限する必要があります。それはそれほど簡単ではありません。unordered-containers簡単です: を使用するだけfromListです。これはここではそれほど簡単ではありません: どのようにしてリストをランダムにツリーに変換し、いずれにせよ偏りを招くことはありません (つまり、左枝や非常に左寄りのツリーを好まない)。
リストからある種の幅優先の構築 (によって提供される関数Data.Treeはすべて事前注文されています) は素晴らしいものであり、それを書くことはできると思いますが、それは自明ではありません。私は現在ツリーを使用していますが、後でさらに複雑なものを使用するため、より一般的で複雑でない解決策を見つけようとするかもしれないと考えました。それとも自明ではない独自のArbitraryジェネレーターを作成する必要がありますか? 後者の場合、これは手間がかかりすぎるように見えるので、実際には単体テストに頼るかもしれません。