Discussion :

[gomisse]

le type liste defini par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

   type  'a liste= Vide|Cons of 'a*'a liste;;

Je souhaite faire un tri par fusion, selection et tri rapide:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let rec insert elt liste  = match liste with 
    |Vide-> [elt]
    |Cons(a,l) -> if elt<a then elt::a::l
                  else a::(insert_ala_pos elt  l );;

Error: This expression has type 'a liste
       but an expression was expected of type 'a list

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec tri_fusion l1 =match l1 with 
        |Vide -> Vide
        |Cons(a,l)-> insert a (tri_fusion l)
        and insert elt l2 = match l2 with 
        |Vide -> Vide
        |Cons(a1,l) ->if elt<a1 then elt::l2 else a1:: insert elt l;;

Erreur :

Error: The variant type liste has no constructor ::
# 

Je souhaite trier ma liste polymorphe , Merci d'y contribuer ?

[SpiceGuid]

D'une part :

• [] et :: sont des constructeurs pour le type prédéfini 'a list
• Vide et Cons sont des constructeurs pour le type utilisateur 'a liste

Ces deux types, bien que similaires, sont considérés comme totalement différents.

D'autre part tu n'es pas au bout de ta peine car :

• le premier extrait de code ressemble à une insertion mais ne fait pas de tri par insertion
• le second extrait de code ne ressemble en rien à un tri fusion

[gomisse]

Comment faire un tri par insertion et fusion en ocaml ? avec le type liste definie par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 type a' liste= Vide|Cons 'a*'a liste ;;

[SpiceGuid]

• Pour le tri par insertion il te faut d'abord une fonction d'insertion d'un élément dans une liste triée
• Pour le tri par fusion il te faut une fonction qui fusionne deux listes triées en une seule liste triée

[gomisse]

Merci pour ces reponses .
est il possible que tu me fasse une partie du code ( tri par insertion avec le type polymorphe)?

[gomisse]

type 'a liste= Vide|Cons of 'a*'a liste;;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let rec insert_ e l = match l with 
  |Vide -> Cons(e,Vide)
  |Cons(b,l)-> if e<b then Cons(e,Cons(b,l)) else Cons(b,(insert_ e l));;

Error: Syntax error