関数をよりきれいに書くための提案がいくつかありましたinsertが、これまでのところ、実装の何が問題だったのか誰も教えてくれませんでした。
data ArbolBinario a = Node a (ArbolBinario a) (ArbolBinario a) | EmptyNode
deriving(Show)
insert(x) EmptyNode= insert(tail x) (Node (head x) EmptyNode EmptyNode)
insert(x) (Node e izq der)
|x == [] = EmptyNode
|head x == e = (Node e izq der)
|head x < e = (Node e (insert x izq) der)
|head x > e = (Node e izq (insert x der))
簡潔にするために、短いリストを使用して に省略EmptyNodeしEます。
insert [1,2] E
~> insert [2] (Node 1 E E)
-- 2 > 1, so the last clause, head x > e, is used
~> Node 1 E (insert [2] E)
-- insertion in empty tree, first equation is used
~> Node 1 E (insert [] (Node 2 E E))
-- Now the first clause of the second equation is used
~> Node 1 E (E)
すべての要素が挿入され、リストの最後に到達したら、何もしないのではなく、ノードを削除します。これを修正するための最小限の変更は、2 番目の方程式の最初の節を に変更することですinsert。
|x == [] = Node e izq der
ただし、それでも1つの失敗ケースが残ります（すでに発生しています）。
insert [] EmptyNode = insert (tail []) (Node (head []) EmptyNode EmptyNode)
原因になり*** Exception: Prelude.tail: empty listます。
上記のエラーの原因であることに加えて、ここでのheadandの使用tailも非常に一義的です。このような関数を定義する通常の方法は、リストでパターン マッチを行うことです。また、空リストのチェックは一義的でありx == []、慣用的な方法はそのために使用null xすることです。この場合、他のガードは要素の型が のインスタンスである必要があるOrdため、セマンティックの変更はありませんが、一般に要素の型に制約をx == []課しますが、任意の型で機能します。Eqnull x
head x == e最後に、ガード、head x < e、がすべての可能性をカバーしていると思いますがhead x > e(有効なインスタンスの場合、それらはカバーします - aが任意の値と等しくも小さくも大きくもないOrd浮動小数点型を除きますが、これらのインスタンスが有効かどうかは問題です)議論)、コンパイラはそれを確信することができず、(そのようなことについて警告するように求められた場合、通常はそうあるべきですが、常に でコンパイルします) の定義の網羅的でないパターンについて警告します。すべてのケースがカバーされていることをコンパイラーが認識できるように、すべてのケースをカバーするには、最後のガードに条件が必要です。NaNOrd-Wallinsertotherwise
コードをより慣用的な形にする (そして未解決のinsert [] EmptyNodeバグを修正する) と、
insert :: Ord a => [a] -> ArbolBinario a -> ArbolBinario a
insert [] t = t -- if there's nothing to insert, don't change anything
insert (x:xs) EmptyNode = insert xs (Node x EmptyNode EmptyNode)
-- Using as-patterns, `l` is the entire list, `x` its head, `t` the entire tree
insert l@(x:_) t@(Node e izq der)
| x == e = t
| x < e = Node e (insert l izq) der
| otherwise = Node e izq (insert l der)
これで、さらに問題を探すことができます。のおそらく意図しない側面の 1 つinsertは、挿入される要素のリストの先頭が既にツリーにある場合、リスト全体が破棄され、ツリーが完全に変更されないことです。たとえば、
insert [1 .. 10] (Node 1 EmptyNode EmptyNode) = Node 1 EmptyNode EmptyNode
このようなことを処理する通常の方法は、リストの先頭のみを削除し、残りの要素を挿入することです。これは、定義の最後の式を次のように変更することによって達成されます。
insert l@(x:xs) t@(Node e izq der)
| x == e = insert xs t
| x < e = Node e (insert l izq) der
| otherwise = Node e izq (insert l der)
おそらく意図しない側面は
insert xs EmptyNodeは常に、すべてのノードが 1 つだけ (最下位の場合は 1 つもありません) の空でないサブツリーを持つツリーを生成します。つまり、構築されたツリーは基本的にリストです。定義の最後の方程式の節は、ツリーが二分探索ツリーであることを強く示唆していますが、そのプロパティは定義によって維持されていません。例えば
insert [1,10] (Node 3 (Node 2 E E) (Node 7 E E))
~> Node 3 (insert [1,10] (Node 2 E E)) (Node 7 E E)
~> Node 3 (Node 2 (insert [1,10] E) E) (Node 7 E E)
~> Node 3 (Node 2 (insert [10] (Node 1 E E)) E) (Node 7 E E)
~> Node 3 (Node 2 (Node 1 E (Node 10 E E)) E) (Node 7 E E)
3
/ \
/ \
2 7
/
/
1
\
\
10
これらの問題を解決する最善の方法は、OJとしてです。単一の要素をツリーに挿入する場合を区別するために、前に提案した
insertOne :: Ord a => a -> ArbolBinario a -> ArbolBinario a
insertOne x EmptyNode = Node x EmptyNode EmptyNode
insertOne x t@(Node e izq der)
| x == e = t
| x < e = Node e (insertOne x izq) der
| otherwise = Node e izq (insertOne x der)
それを使用して、リストから各要素を挿入し、上からその位置を見つけます。
insertList :: Ord a => [a] -> ArbolBinario a -> ArbolBinario a
insertList [] t = t
insertList (x:xs) t = insertList xs (insertOne x t)
-- Alternative way:
-- insertList (x:xs) t = insertOne x (insertList xs t)
これらの計算パターンは非常に一般的であるため、 で定義されている関数に取り込まれていますPrelude。
insertList xs t = foldl (flip insertOne) t xs
-- or, for the alternative way:
-- insertList xs t = foldr insertOne t xs
ご覧のとおり、自然な引数の順序がinsertOneである左の折りたたみでは、flipコンビネータを適用してその引数の順序を交換する必要があります。これは、リストの自然な折りたたみ操作が右の折りたたみであるという事実を示唆していますfoldr。
ただし、insertOne何かを行う前にツリー引数を知る必要があるため、右の折り畳みで使用するように調整された関数ではなく、左の折り畳みで使用する方が効率的です (ただし、実際に効率を上げるには、foldl'から入手可能な厳密な左折Data.Listりと、より厳密なバージョンのinsertOne) を使用する必要があります。