標準MLにBST検索機能を書くには？

Question

必要なのは、与えられたデータ要素をnstで検索するタイプ''a tree -> (''a * ''a -> bool) -> ''a -> bool のsearchBSTを書くことです。また

datatype 'data tree = Empty 
        | Node of 'data tree * 'data * 'data tree 

が、私たちはツリー内のすべてのノードを検索することはできません、しかし、定義によれば、我々が探している要素が含まれている可能性があるノードのみ：使用。

私が書いた関数はタイプ(int * int tree -> bool)であり、私は必要な型

datatype 'data tree = Empty 
        | Node of 'data tree * 'data * 'data tree; 

fun searchBST (x, Empty) = false 
    | searchBST (x, Node(l, parent, r)) = 
     if x = parent then true 
     else 
     if x< parent then searchBST(x, l) 
     else searchBST(x,r) 

Answer 1

あなたは、あなたのコード内でこの部分が欠落している」（ 『』 * 『』に変換上の任意のヒントをいただければ幸いです - > bool） "これを考慮して、タプルを処理してからコードが機能します。 2つの 'a'は検索対象の要素であり、ノードからの要素です。

Answer 2

種類が''a * ''a -> boolの場合、述語関数は常に（99.9％）です。これは、引数タプル''a * ''aが等価型であることを強く示唆しています（したがって、ダブルマークであり、単一のマークは "通常"ではありません）。

検索関数を作成しているので、あなたの述語関数は、検索する要素を定義するために使用される可能性が高いです。 しかし、希望の要素がツリーの左または右の部分にあるかどうかを定義する場合もあります。通常、それはタイプ''a * ''a -> orderの注文機能でした。このような順序付け関数は、より実用的な場合には、より小さい値をハードコーディングするのではなく、等価性を含む要素の順序付けを抽象化できるため、関数が整数にのみ作用するようになります（ ''a（等価）の値の代わりに、実数などの他の数値型に注釈を入力する場合を除きます）。

は、このようにあなたが（目的のタイプを取得する）wan't何、フォームのものです：tが木である

fun searchBST t p x = 

、pは「あなたの述語関数とxはあなたがワン値であります見つけてください。基本的に欠けているのは、直接行うのではなく、テストで述語関数を使用することです。

fun searchBST Empty _ _ = false 
    | searchBST (Node(l, d, r)) p x = 
    case (p(x, d), x < d) of 
     (true, _) => true 
     | (_, true) => searchBST l p x 
     | (_, false) => searchBST r p x