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