SMLNJ插入排序操作和操作數不同意錯誤

林在SML使插入排序的代碼，這是SMLNJ插入排序操作和操作數不同意錯誤

fun compare(x:real, y:real, F) = F(x, y); 
fun isEqual(x:real, y:real) = ((x <= y) andalso (x >= y)); 

fun rinsert(x: real, [], F) = [x] 
    |rinsert(x, (y::ys), F) = 
    if isEqual(x, y) then rinsert (x, ys, F) 
    else if compare(x, y, F) then x::y::ys 
      else y::(rinsert (x, ys, F)); 

fun rinsort([], F) = [] 
    |rinsort(x::xs, F) = rinsert(x, (rinsort(xs, F), F));

但是，在運行它，我得到這個錯誤

val isEqual = fn : real * real -> bool                                        
val rinsert = fn : real * real list * (real * real -> bool) -> real list                                
stdIn:12.27-12.58 Error: operator and operand don't agree [tycon mismatch]                               
    operator domain: real * real list * (real * real -> bool)                                   
    operand:   'Z * ('Y list * 'X)                                        
    in expression:                                              
    rinsert (x,(rinsort (<exp>,<exp>),F))

我明白rinsort不正確地調用rinsert，但我不知道如何解決它。

來源

2017-07-07 small502

'rinsert'需要多少個參數？你打了幾個電話？ – melpomene

rinsert需要三個參數，一個實數，一個列表和一個運算符（如op <）。它應該只是叫三個 – small502

我不明白你的意思是「*它只應該叫三*」。看代碼。計算參數。那裏有多少？ – melpomene

如果它是有用的，這是如何您的代碼應與工作的例子的real list：

fun compare(x:real, y:real, F) = F x y; 
fun isEqual(x:real, y:real) = ((x <= y) andalso (x >= y)); 

fun rinsert(x: real, [], F) = [x] 
    |rinsert(x, (y::ys), F) = 
    if isEqual(x, y) then rinsert (x, ys, F) 
    else if compare(x, y, F) then x::y::ys 
      else y::(rinsert (x, ys, F)); 

fun rinsort([], F) = [] 
    |rinsort(x::xs, F) = rinsert(x, rinsort(xs, F), F); 

val funcComp = fn r1 : real => fn r2 : real => if r1 < r2 then true else false; 
val l : real list = [1.0, 3.8, 5.6, 3.8, 4.4, 5.6, 6.3, 5.5, 4.6, 8.1]; 
val b = rinsort(l, funcComp);

來源

2017-07-07 19:08:08

'如果r1> r2，那麼false否則true'最好表示爲'r1 <= r2'。 –

是的，但不完全是因爲'isEqual'已經檢查它們的等式。無論如何，你的版本肯定更好理解。 –

你不應該比較那樣的實物。您可能對[爲什麼我無法比較標準ML中的實數？]感興趣[（https://stackoverflow.com/questions/41394992/why-cant-i-compare-reals-in-standard-ml）考慮使用' Real。=='或者一個epsilon測試。 –

一些一般性的反饋：

功能compare的目的只是爲了給切換參數F的順序，所以你不妨直接參考F。
函數isEqual有點不好。由於reals are not equality types in SML出於某種原因，請儘量避免將它們比較。事實證明，爲了分類實物，你只需要<=而不是=。
功能rinsert有嚴格: real類型的註釋是不必要的，因爲你插入排序，採取比較運算F作爲參數，很可能會成爲通用（多態）。
您可能想要調用參數F一些更具描述性的東西，如cmp,leq或任何提醒您其目的。

這裏有一個如何我們也可以做一個插入排序函數的一個例子：

fun sort leq xs = 
    let fun insert (x, []) = [x] 
      | insert (x, y::ys) = 
       if leq (x, y) 
       then x::y::ys 
       else y::insert (x, ys) 
    in List.foldl insert [] xs 
    end

它的類型('a * 'a -> bool) -> 'a list -> 'a list。這與例如SML/NJ的內置ListMergeSort.sort。我選擇sort是curried因爲你可能想通過局部的功能應用，例如專攻它，

val realsort = sort (op <=) : real list -> real list 
val stringsort = sort (op >) : string list -> string list

，但我已經讓嵌入式輔助函數insert因爲List.foldl被uncurried需要一個函數('a * 'b -> 'b)類型，即(x, ys)的元組，並且返回修改後的ys和插入的x。

您可能想要考慮哪些屬性可以測試您的函數進行排序。一個屬性可能是排序列表中的所有列表元素都是由比較運算符leq指定的順序。

fun sorted_prop _ [] = true 
    | sorted_prop _ [_] = true 
    | sorted_prop leq (x::y::xs) = leq (x, y) andalso sorted_prop leq (y::xs)

另一個屬性可能是未排序列表中的每個元素都存在於排序列表中。如果您不假設x具有相等類型（''a），則後者屬性可能難以測試。但你可以在測試中專門做到這一點。

來源

2017-07-13 09:07:28

SMLNJ插入排序操作和操作數不同意錯誤

回答

相關問題