CAML: realiser la différence symétrique entre 2 listes sujet de l'X SPé INFO

[invitef1ec1449]

bonjours, je dois faire un programme en CAML qui a partir d'une fonction realise la différence symétrique entre 2 listes, le nombre d'opération ne dépassant pas O(m+p) où m et p st les cardinaux des 2 listes, j'ai essayer ca mais ca marche pas qq pourrait-il m'aider merci d'avance.....

let rec delta l1 l2 = match l1 l2 with
|[] []->[]
|t::q m: if t<m then t::delta(q,m:) else
if t=m then delta(q,p) else
m::delta(t::q,p)
;;
-----

[invite4ef352d8]

Salut !

il manque des informations la ^^

par différence symétrique, tu pense à l'opération A Delta B = A union B - A inter B ?

les listes mises en argument sont sencé etre triés ? (et si oui, dans qu'elle ordre)

[Eriko]

C'est ça que tu veux ?

let rec delta l1 l2 = match l1, l2 with
| [], l2 -> l2
| l1, [] -> l1
| t::q, m: -> if t<m then t:delta q l2) else
if t>m then m:delta l1 p) else (delta q p);;

Ca ne fonctionne que si tes listes sont triées ce truc...

Sinon je te laisse réfléchir


edit : y a pas un moyen de virer les smileys des messages ?

[Eriko]

Le même sans les smileys :

let rec delta l1 l2 = match l1, l2 with
| [], l2 -> l2
| l1, [] -> l1
| t::q, m::p -> if t<m then t::(delta q l2) else
if t>m then m::(delta l1 p) else (delta q p);;

[A voir en vidéo sur Futura]