如何在標準ML中編寫BST搜索功能？

需要的是編寫''a tree -> (''a * ''a -> bool) -> ''a -> bool 類型的函數searchBST，該函數searchBST搜索給定數據元素的nst。使用：如何在標準ML中編寫BST搜索功能？

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)

來源

2012-04-01 Farah

大概，這是作業。你應該使用作業標籤。 – 2012-04-02 06:13:07

你缺少這部分代碼中的「（'A *‘’一個任何提示 - > bool）「考慮它，在元組上工作，然後你的代碼就可以工作。這兩個'a'是您搜索的元素和節點中的元素。

來源

2012-04-01 22:50:01

當某事有類型''a * ''a -> bool時，它總是（99.9％的時間）一個謂詞函數。這強烈暗示了參數元組''a * ''a是一個相等類型（因此是雙聯標記，而不是一個標記爲「正常」）。

由於您正在構建搜索功能，因此您的謂詞函數很可能是應該用於定義您要搜索的元素的函數。然而，它也可能是它定義了所需元素是在樹的左邊部分還是右邊部分。雖然通常情況下它會是''a * ''a -> order型的訂購功能。這樣的排序函數在任何實際情況下都會更好，因爲然後您可以抽象出元素的排序（包括相等）而不是硬編碼一個小於，然後強制您的函數只能處理整數除非您鍵入註釋到其他數字類型，例如reals），而不是''a（相等）值。

因此你wan't什麼（以獲得所需的類型），是形式的東西：

fun searchBST t p x =

其中t是樹，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

來源

2012-04-06 22:03:53

如何在標準ML中編寫BST搜索功能？

回答

相關問題