“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 134 — #144
i
i
i
i
i
i
i
i
134
3
• Techniques de programmation déclarative
et linéaires en temps. Nous définissons d’abord les opérations de fusion (Merge) et
de découpe (Split) et ensuite le tri (Mergesort) :
fun {Merge Xs Ys}
case Xs # Ys of nil # Ys then Ys
[] Xs # nil then Xs
[] (X|Xr) # (Y|Yr) then
if X else Y|{Merge Xs Yr} end
end
end
Liste L
L1
L2
S1
S2
S
L11
L12
L21
L22
S22
S21
S12
S11
Découpe
Découpe
d’entrée
Fusion
Fusion
Liste
triée
Découpe
Fusion
Figure 3.9 Le tri par fusion.
Le type est fun {$ List T List T}: List T, où T est Int, Float ou Atom.
Nous définissons la découpe comme une procédure parce qu’elle a deux sorties. Elle
aurait pu être définie comme une fonction qui renvoie une paire comme seule sortie.
proc {Split Xs ?Ys ?Zs}
case Xs of nil then Ys=nil Zs=nil
[] [X] then Ys=[X] Zs=nil
[] X1|X2|Xr then Yr Zr in
Ys=X1|Yr
Zs=X2|Zr
{Split Xr Yr Zr}
end
end
Le type est proc {$ List T List T List T}. Voici la définition du tri :