1
2(* Merge sort example in Moscow ML *)
3
4datatype num = O | S of num;
5
6fun inf_egal O n = true
7  | inf_egal (S k) O = false
8  | inf_egal (S k) (S l) = (inf_egal k l)
9;
10
11fun fusion (h1::t1) (h2::t2) =
12      if (inf_egal h1 h2) then h1::(fusion t1 (h2::t2))
13      else h2::(fusion (h1::t1) t2)
14  | fusion [] l2 = l2
15  | fusion l1 [] = l1
16;
17
18
19datatype arbin = Fe | Br of num * arbin * arbin;
20
21fun Tas2Ln Fe = []
22  | Tas2Ln (Br (n,a1,a2)) = n::(fusion (Tas2Ln a1) (Tas2Ln a2))
23;
24
25fun insTas Fe n = Br(n,Fe,Fe)
26  | insTas (Br(m,a1,a2)) n =
27      if (inf_egal n m) then Br(n,a2,insTas a1 m) else Br(m,a2,insTas a1 n)
28;
29
30fun Ln2Tas [] = Fe
31  | Ln2Tas (n::ns) = insTas (Ln2Tas ns) n
32;
33
34fun tri_heap l = Tas2Ln (Ln2Tas l);
35
36val n1 = S O;
37val n2 = S n1;
38val n3 = S n2;
39val n4 = S n3;
40
41fun app_l20 l =
42  [ n2,O,n1,O,n1,n3,n4,
43    n1,O,n1,n3,O,n1,n3,
44    n4,n2,O,n1,O,n1 ] @ l
45;
46
47fun double l () = let val ll = l() in ll@ll end;
48fun triple l () = let val ll = l() in ll@(ll@ll) end;
49
50
51val L20 = app_l20 [];
52val L100 = funpow 5 app_l20 [];
53val L200 = double (fn _ => L100);
54val L400 = double L200;
55val L1200 = triple L400;
56val L2400 = double L1200;
57val L4800 = double L2400;
58val L9600 = double L4800;
59val L19200 = double L9600;
60val L38400 = double L19200;
61
62
63time (funpow 100 (fn() => (tri_heap (L200()); ()))) (); (* ~ 0.36s *)
64time (funpow 100 (fn() => (tri_heap (L1200()); ()))) (); (* ~ 4.17s *)
65time (funpow 10 (fn() => (tri_heap (L19200()); ()))) (); (* ~ 15.7s *)
66time (funpow 10 (fn() => (tri_heap (L38400()); ()))) (); (* ~ 43.3s *)
67