標準MLバイナリツリートラバーサル

Question

私はSMLを初めて使い、ツリートラバーサルに関する練習をしています。 これは質問の設定です。

datatype 'a bTree = nil | bt of 'a bTree * 'a * 'a bTree; 

私はバイナリツリーを受け入れ、inorder traversalでツリーのすべてのメンバーのリストを返す関数inorderを書く必要があります。

私はこの行を書いた：

fun inorder(nil) = nil 
    | inorder(bt(left,key,right)) = inorder(left) @ [key] @ inorder(right); 

しかし、いくつかのエラーを取得して修正する方法がわからない：

Error: operator and operand don't agree [tycon mismatch] 
operator domain: 'Z list * 'Z list 
operand:   'Z list * 'Y bTree 
in expression: 
    (key :: nil) @ inorder right 

Error: operator and operand don't agree [tycon mismatch] 
operator domain: 'Z list * 'Z list 
operand:   'Y bTree * _ 
in expression: 
    inorder left @ (key :: nil) @ inorder right 

Answer 1

あなたは不注意nilリストのコンストラクタを隠され、あなたとそれを交換してきました同じ名前のツリーコンストラクタです。

これはあなたの最初の場合、

inorder(nil) = nil 

がinorderの結果は木であると言うことを意味します。その種類は

'a bTree -> 'a bTree 

であり、あなたが'a bTreeに（@）リストを追加することはできません。

datatype 'a bTree = nilTree | bt of 'a bTree * 'a * 'a bTree; 

fun inorder nilTree = nil 
    | inorder (bt(left,key,right)) = inorder left @ [key] @ inorder right; 

または[]の代わりnilを使用する：あなたは空の木のコンストラクタの名前を変更する場合

あなたのコードは動作します。
しかし、nilを隠していない方が良い解決策です。