smlnj insertion Trier l'opérateur et Opérande DonT accord erreur

Question

Im faire un code de tri d'insertion dans SML, ici il est

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)); 

Cependant, sur l'exécution de ce que je reçois cette erreur

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)) 

Je comprends que rinsort appelle incorrectement rinsert, mais je ne suis pas sûr de savoir comment le réparer.

Answer 1

S'il peut être utile, c'est un exemple de la façon dont votre code devrait fonctionner avec un 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); 

Answer 2

Quelques commentaires généraux: seulement

• La fonction compare sert le but de changer l'ordre des arguments de F, donc vous pourriez aussi bien se référer à F lui-même alors.

• La fonction isEqual est un peu mauvaise. Depuis reals are not equality types in SML pour une raison, essayez et évitez de les comparer comme ça. Il s'avère, afin de trier les réels, vous avez seulement besoin <=, pas =.

• La fonction rinsert a strictes annotations de type : real qui sont inutiles puisque votre type d'insertion, en prenant l'opérateur de comparaison F en tant que paramètre, pourrait aussi bien être générique (polymorphes).

• Vous pouvez appeler le paramètre F plus descriptif, comme cmp, leq, ou tout ce qui vous rappelle son but.

Voici un exemple de la façon dont on pourrait aussi faire une fonction de tri d'insertion:

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 

Il a le type ('a * 'a -> bool) -> 'a list -> 'a list. Ceci est comparable à par ex. SML/NJ intégré ListMergeSort.sort. J'ai choisi sort être curried puisque vous voudrez peut-être de se spécialiser par application de fonction partielle, par exemple,

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

mais j'ai laissé la fonction d'aide intégrée insert à uncurried depuis List.foldl prend une fonction de type ('a * 'b -> 'b) , c'est-à-dire un tuple de (x, ys) et renvoie un ys modifié avec x inséré.

Vous pouvez envisager les propriétés pouvant tester que votre fonction effectue un tri. Une propriété peut être que tous les éléments de liste de la liste triée sont dans l'ordre spécifié par l'opérateur de comparaison leq.

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

Une autre propriété peut être que chaque élément de la liste non triée existe dans la liste triée. Cette dernière propriété peut être difficile à tester si vous ne supposez pas x d'avoir un type d'égalité (''a). Mais vous pourriez le faire dans le test en particulier.