let def mk_list! () = let def cons! (x) | h(i) = elem(i+1,x) | h(i+1) | reply to cons or empty! () | h(i) = h(i) | reply i=0 to empty or head! () | h(i) = let h1 = head_aux (i) in h(i) | reply h1 to head or head_aux! (i) | elem(j,x) = if i=j then {elem(j,x) | reply x to head_aux} else { let h1 = head_aux (i) in elem(x,j) | reply h1 to head_aux} or tail! () | h(i) = tail_aux (i) ; {h(i-1) | reply to tail} or tail_aux! (i) | elem(j,x) = if i=j then {reply to tail_aux} else { tail_aux (i) ; {elem(j,x) | reply to tail_aux} } in h(0) | reply cons,empty,head,tail ;; let c,e,h,t = mk_list () ;; let def append! (e,h,t,c) = if e () then {reply} else { let elem = h () in t () ; append (e,h,t,c) ; c (elem) ; reply} ;; let def view_list! (e,h,t) = if e () then {reply} else { print_int (h ()); print_string(" "); t () ; view_list (e,h,t) ; reply } ;; (* let def init_random(c,n) = if n=0 then {reply} else { c(random.int(100)) ; init_random(c,n-1) ; reply } ;; *) let def init_sorted! (c,n) = if n=0 then {reply} else { c (n) ; init_sorted (c,n-1) ; reply } ;; let def partition! (e,h,t,p) = let c1,e1,h1,t1 = mk_list () and c2,e2,h2,t2 = mk_list () in let def partition_aux! (e,h,t,p) = if e () then {reply} else { let h1 = h () in (if h1 < p then c1 (h1) else c2 (h1)); t (); partition_aux (e,h,t,p); reply } in partition_aux (e,h,t,p) ; reply c1,e1,h1,t1,c2,e2,h2,t2 ;; let def quicksort! (c,e,h,t) = if e () then {reply} else { let p = h () in t (); let c1,e1,h1,t1,c2,e2,h2,t2 = partition (e,h,t,p) in quicksort (c1,e1,h1,t1); quicksort (c2,e2,h2,t2); c2 (p); append (e1,h1,t1,c2); append (e2,h2,t2,c); reply } ;; let _ = init_sorted (c,100) ; quicksort (c,e,h,t); view_list (e,h,t) ; print_newline () ;;