ML语言
注释和附录代码

↑  基于GNU Common Lisp的Cambridge LCF ML示例：
$ hol88


===============================================================================
         HOL88 Version 2.02 (GCL), built on 1/4/24
===============================================================================

#letrec fact n = if n=0 then 1 else n*fact(n-1);;
fact = - : (int -> int)

#fact 3;;
6 : int

#
↑  
子句集合是穷尽和不冗余的函数示例：
fun hasCorners (Circle _) = false
  | hasCorners _ = true

如果控制通过了第一个模式Circle，则这个值必定是要么Square要么Triangle。在任何这些情况下，这个形状都有角点，所以返回true而不用区分具体是那种情况。
↑  
不详尽的模式示例：
fun center (Circle (c, _)) = c
  | center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)

这里在center函数中没有给Triangle的模式。
编译器发起模式不详尽的一个警告，并且如果在运行时间，Triangle被传递给这个函数，则发起例外Match。
↑  
存在模式冗余的（无意义）函数示例：
fun f (Circle ((x, y), r)) = x+y
  | f (Circle _) = 1.0
  | f _ = 0.0

匹配第二个子句的模式的任何值都也匹配第一个子句的模式，所以第二个子句是不可到达的。因此这个定义整体上是冗余的。
↑  
映射函数的实际实现：
fun map f = let
    fun m [] = []
	  | m [a] = [f a]
	  | m [a, b] = [f a, f b]
	  | m [a, b, c] = [f a, f b, f c]
	  | m (a :: b :: c :: d :: r) = f a :: f b :: f c :: f d :: m r
    in
	    m
    end

折叠函数的实际实现：
fun foldl f b l = let
    fun f2 ([], b) = b
	  | f2 (a :: r, b) = f2 (r, f (a, b))
    in
	    f2 (l, b)
    end

fun foldr f b l = foldl f b (rev l)

过滤器函数的实际实现：
fun filter pred [] = []
  | filter pred (a :: rest) =
      if pred a
	  then a :: (filter pred rest)
	  else (filter pred rest)
↑  
对分数采取修约的有理数实现：
signature ARITH =
sig
    eqtype t
    val zero : t
    val one : t
    val fromInt: int -> t  
    val fromIntPair : int * int -> t
    val repr : t -> unit
    val succ : t -> t
    val pred : t -> t
    val ~ : t -> t
    val + : t * t -> t
    val - : t * t -> t
    val * : t * t -> t
    val / : t * t -> t
end

structure Rational : ARITH =
struct
    type t = int * int
    val zero = (0, 1)
    val one = (1, 1)
    val maxInt = (let val SOME a = Int.maxInt in Int.toLarge a end)
    fun fromInt n = (n, 1)
    fun neg (a, b) = (~a, b)
    fun fromLargePair (a, b) = (Int.fromLarge a, Int.fromLarge b)
    fun fromIntPair (num, den) = let
        fun reduced_fraction (numerator, denominator) = let
            fun gcd (n, 0) = n
              | gcd (n, d) = gcd (d, n mod d)
            val d = gcd (numerator, denominator)
            in 
                if d > 1 then (numerator div d, denominator div d) 
                else (numerator, denominator)
            end
        in
            if num < 0 andalso den < 0
            then reduced_fraction (~num, ~den)
            else if num < 0 
            then neg (reduced_fraction (~num, den))
            else if den < 0
            then neg (reduced_fraction (num, ~den))
            else reduced_fraction (num, den)
        end
    fun repr (a, b) = let
        val m = if (b = 0) then 0 else if (a >= 0) then a div b else ~a div b
        val n = if (b = 0) then 1 else if (a >= 0) then a mod b else ~a mod b
        val ms = Int.toString m and ns = Int.toString n and bs = Int.toString b
        in 
            if n <> 0 andalso m <> 0 andalso a < 0
            then print ("~" ^ ms ^ " - " ^ ns ^ "/" ^ bs ^ "\n")
            else if n <> 0 andalso m <> 0  
            then print (ms ^ " + " ^ ns ^ "/" ^ bs ^ "\n")
            else if n <> 0 andalso m = 0 andalso a < 0
            then print ("~" ^ ns ^ "/" ^ bs ^ "\n")
            else if n <> 0 andalso m = 0 
            then print (ns ^ "/" ^ bs ^ "\n")
            else if a < 0 
            then print ("~" ^ ms ^ "\n")
            else print (ms ^ "\n")
        end
    fun convergent (i, n, d, h_1, k_1, h_2, k_2) = 
          if i <> 0 andalso ((h_1 > (maxInt - h_2) div i)
              orelse (k_1 > (maxInt - k_2) div i))
          then (h_1, k_1)  
          else if n = 0
          then (i * h_1 + h_2, i * k_1 + k_2) 
          else convergent (d div n, d mod n, n,
                           i * h_1 + h_2, i * k_1 + k_2, h_1, k_1) 
    fun add ((a, b), (c, d)) = let
        val la = Int.toLarge a and lb = Int.toLarge b
        val lc = Int.toLarge c and ld = Int.toLarge d 
        val m = la * ld + lb * lc and n = lb * ld 
        in 
            if b = d 
            then fromIntPair (a + c, b)
            else fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
        end 
    fun sub ((a, b), (c, d)) = let
        val la = Int.toLarge a and lb = Int.toLarge b
        val lc = Int.toLarge c and ld = Int.toLarge d  
        val m = la * ld - lb * lc and n = lb * ld
        in  
            if b = d
            then fromIntPair (a - c, b)
            else if m < 0 
            then neg (fromLargePair (convergent (~m div n, ~m mod n, n, 1, 0, 0, 1)))
            else if m > 0
            then fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
            else (0, 1)
        end
    fun mul ((a, b), (c, d)) = let
        val la = Int.toLarge a and lb = Int.toLarge b
        val lc = Int.toLarge c and ld = Int.toLarge d 
        val m = la * lc and n = lb * ld 
        in  
            fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
        end
    fun op + ((a, b), (c, d)) = 
          if a < 0 andalso c < 0 
          then neg (add ((~a, b), (~c, d)))
          else if a < 0
          then sub ((c, d), (~a, b))
          else if c < 0
          then sub ((a, b), (~c, d))
          else add ((a, b), (c, d))
    fun op - ((a, b), (c, d)) = 
          if a < 0 andalso c < 0 
          then sub ((~c, d), (~a, b))
          else if a < 0
          then neg (add ((~a, b), (c, d)))
          else if c < 0
          then add ((a, b), (~c, d))
          else sub ((a, b), (c, d))
    fun op * ((a, b), (c, d)) = 
          if a < 0 andalso c < 0  
          then mul ((~a, b), (~c, d))
          else if a < 0
          then neg (mul ((~a, b), (c, d)))
          else if c < 0
          then neg (mul ((a, b), (~c, d)))
          else mul ((a, b), (c, d))
    fun op / ((a, b), (c, d)) =
          if a < 0 andalso c < 0  
          then mul ((~a, b), (d, ~c))
          else if a < 0
          then neg (mul ((~a, b), (d, c)))
          else if c < 0
          then neg (mul ((a, b), (d, ~c)))
          else mul ((a, b), (d, c))
    fun succ a = add (a, one)
    fun pred a = sub (a, one)
    fun ~ a = neg a
end
↑  找出函数的实际实现：
fun find pred [] = NONE
  | find pred (a :: rest) =
      if pred a 
      then SOME a 
      else (find pred rest)

存在谓词函数的实际实现：
    
fun exists pred = let
    fun f [] = false
      | f (h :: t) = 
          pred h orelse f t
    in
        f
    end
↑  
筛法基于数组的实现：
fun prime n = let
    val sieve = Array.array (n + 1, true);
    fun markComposite (j, i) =
          if j > n then () 
          else (Array.update (sieve, j, false); 
                markComposite (j + i, i))
    fun iterate i =
          if i * i > n then ()
          else if Array.sub (sieve, i)
          then (markComposite (i * i, i);
                iterate (i + 1))
          else iterate (i + 1)
    fun generate (acc, i) = 
          if i < 2 then acc
          else if Array.sub (sieve, i) 
          then generate (i :: acc, i - 1)
          else generate (acc, i - 1) 
    in 
        if n < 2 then [] 
        else (iterate 2;
              generate ([], n))
    end
↑   汉明数进一步性质演示代码：
fun printIntList (l: int list) =
    print ((String.concatWith " " (map Int.toString l)) ^ "\n");
fun diff (p, q) = let
    fun revDiff (acc, p, q) =
          if not (null p) andalso not (null q) then
              if hd p < hd q
              then revDiff ((hd p) :: acc, tl p, q)
              else if hd p > hd q
              then revDiff (acc, p, tl q)
              else revDiff (acc, tl p, tl q)
          else if null q 
          then List.revAppend (p, acc)
          else acc
    in
        if (null p) then []
        else if (null q) then p
        else rev (revDiff ([], p, q))
    end;
fun Hamming_number n = let
    fun merge (p, q) = let
        fun revMerge (acc, p, q) =
              if not (null p) andalso not (null q) then
                  if hd p < hd q
                  then revMerge ((hd p) :: acc, tl p, q)
                  else if hd p > hd q
                  then revMerge ((hd q) :: acc, p, tl q)
                  else revMerge ((hd p) :: acc, tl p, tl q)
              else if null p 
              then List.revAppend (q, acc)
              else List.revAppend (p, acc)
        in
            if (null p) then q
            else if (null q) then p
            else rev (revMerge ([], p, q))
        end
    fun mergeWith f (m, i) = merge (f m, i)
    fun mul m x = (x * m)             
    fun generate l = let
        fun listMul m = map (mul m) l
        in
            printIntList (listMul 2);
            printIntList (diff (listMul 3, listMul 2));
            printIntList (diff (listMul 5, merge (listMul 2, listMul 3)));  
            foldl (mergeWith listMul) [] [2, 3, 5]
        end
    val count = ref 1;
    fun iterate (acc, l) =
          if (hd l) > (n div 2) then merge (l, acc)
          else (print ("round " ^ (Int.toString (!count)) ^ " for " ^
                       (Int.toString(length l)) ^ " number(s)\n");
                count := !count + 1;
                iterate (merge (l, acc), generate l))
    in
        if n > 0 then iterate ([], [1]) else []
    end;

val l = Hamming_number 400;
val h = List.filter (fn x => (x <= 400)) l;
val _ = print ((Int.toString (length h)) ^ " numbers from " ^ 
               (Int.toString (length l)) ^ " numbers\n");
↑  部份映射函数的实际实现：
fun mapPartial pred l = let
    fun mapp ([], l) = rev l
      | mapp (x :: r, l) =
         (case (pred x)
            of SOME y => mapp (r, y :: l)
             | NONE => mapp (r, l)
             (* end case *))
    in
        mapp (l, [])
    end
↑  
列表长度函数的实际实现：
fun length l = let
    (* fast add that avoids the overflow test *)
    val op + = Int.fast_add
    fun loop (n, []) = n
	  | loop (n, [_]) = n + 1
	  | loop (n, _ :: _ :: l) = loop (n + 2, l)
    in
	    loop (0, l)
    end
↑  变体的插入排序算法实现：
fun insertSort l = let
    fun insert pred (ins, l) = let
        fun loop (acc, []) =
              List.revAppend (acc, [ins])
          | loop (acc, l as x :: xs) =
              if pred (ins, x)
              then List.revAppend (acc, ins :: l)
              else loop (x :: acc, xs)
         in 
            loop ([], l)
        end
    val rec lt = fn (x, y) => (x < y)     
    in
        foldl (insert lt) [] l
    end
↑  下面是希尔排序算法的原型实现，当输入列表趋于正序的时候，scatter函数将其分解为一组趋于反序的子列表，经过在输入趋于反序情况下性能最佳的变体插入排序后，gather函数再将它们合成为一个列表：
fun shellSort l = let
    fun insert pred (ins, l) = let
        fun loop (acc, []) =
              List.revAppend (acc, [ins])
          | loop (acc, l as x :: xs) =
              if pred (ins, x)
              then List.revAppend (acc, ins :: l)
              else loop (x :: acc, xs)
        in 
            loop ([], l)
        end
    val rec lt = fn (x, y) => (x < y)
    fun insertSort l = foldl (insert lt) [] l 
    fun scatter (l, n) = let
        fun dup n = let
            fun loop (acc, i) =
                  if i <= 0 then acc
                  else loop ([] :: acc, i - 1)
            in
                loop ([], n)
            end
        fun loop ([], acc, lol) =
              List.revAppend (acc, lol)
          | loop (l, acc, []) =
              loop (l, [], rev acc)
          | loop (x :: xs, acc, l :: ls) =
              loop (xs, (x :: l) :: acc, ls)
        in
            loop (l, [], dup n)
        end
    fun gather lol = let
        fun loop ([], [], l) = rev l
          | loop (acc, [], l) =
              loop ([], rev acc, l)
          | loop (acc, [] :: ls, l) =
              loop (acc, ls, l)  
          | loop (acc, (x :: xs) :: ls, l) =    
              loop (xs :: acc, ls, x :: l)
        in
            loop ([], lol, [])
        end 
    val gap = let
        fun loop (acc, i) = let
        val h = (i * 5 - 1) div 11
            in
                if i < 5 then rev (1 :: acc) 
                else loop (h :: acc, h)
            end
        in 
            loop ([], length l)
        end
    fun sort (h, l) = gather (map insertSort (scatter (l, h)))
    in
        foldl sort l gap 
    end
↑  希尔排序还可以采用Ciura提出的间隔序列：
    val incs = [1750, 701, 301, 132, 57, 23, 10, 4, 1]
    val gap = let
        fun loop (acc, i) = let
            val h = (i * 4 - 1) div 9
            fun iter incs =
                  if i >= (hd incs) * 4 div 3 then incs
                  else iter (tl incs)
            in
                if i <= ((hd incs) * 3)
                then List.revAppend (acc, iter incs) 
                else loop (h :: acc, h)
            end
        in  
            if len = 0 then [1]
            else loop ([], len)
        end
↑  
划分函数的实际实现：
fun partition pred l = let
    fun loop ([], trueList, falseList) =
          (rev trueList, rev falseList)
      | loop (h :: t, trueList, falseList) =
          if pred h then loop (t, h :: trueList, falseList)
          else loop (t, trueList, h :: falseList)
    in
	    loop (l, [], [])
    end
↑  
归并排序算法的自顶向下实现：
fun mergeSort l = let
    fun sort ([], _) = []
      | sort ([x], _) = [x]
      | sort ([x, y], _) =
          if x <= y then [x, y] else [y, x]
      | sort ([x, y, z], _) =
          if x <= y then
              if y <= z then [x, y, z]
              else if x <= z then [x, z, y] 
              else [z, x, y]
          else 
              if x <= z then [y, x, z]
              else if y <= z then [y, z, x]
              else [z, y, x] 
      | sort (l, n) = let
        val m = n div 2
        fun split (l, acc, i) = 
              if i = 0 then (rev acc, l)
              else split (tl l, (hd l) :: acc, i - 1)
        fun merge (p, q) = let
            fun revMerge (acc, p, q) =
                  if not (null p) andalso not (null q) then
                      if (hd p) <= (hd q)
                      then revMerge ((hd p) :: acc, tl p, q)
                      else revMerge ((hd q) :: acc, p, tl q)
                  else if null p 
                  then List.revAppend (q, acc)
                  else List.revAppend (p, acc)
            in
                rev (revMerge ([], p, q))
            end
        val (ls, rs) = split (l, [], m)
        in
            merge (sort (ls, m), sort (rs, n - m))
        end
    in
        sort (l, length l)
    end
↑  堆排序算法的数组实现中，堆建造函数heapify也可以使用siftup函数的数组来完成，它将新节点自堆底向上插入到合适的位置，而不对途径节点左右子树顶点进行比较：
    fun siftup i = let
        val ins = get i
        fun loop i = let
            val j = (i - 1) div 2 
            in
                if i <= 0 orelse (get j) >= ins
                then set i ins
                else (set i (get j); loop j)
            end
        in
            loop i    
        end  
    fun heapify () = let
        fun loop i =
              if i > (len - 1) then ()
              else (siftup i; loop (i + 1))
        in
            loop 1
        end
↑  在堆排序算法的二叉树实现中，树插入和提取函数也可以写为等价的尾递归形式代码：
    exception Err;   
    fun revLink ([], t) = t
      | revLink (Nil :: xs, t) = revLink (xs, t)   
      | revLink ((Leaf k) :: xs, t) = 
          revLink (xs, Node (k, (count t) + 1, t, Nil))
      | revLink (Node (k, c, Nil, r) :: xs, t) = 
          revLink (xs, Node (k, c, t, r)) 
      | revLink (Node (k, c, l, Nil) :: xs, t) = 
          revLink (xs, Node (k, c, l, t))
      | revLink (_ :: xs, t) = raise Err        
    fun insert (t, x) = let    
        fun loop (acc, Nil, x) = revLink (acc, Leaf x)
          | loop (acc, Leaf k, l) = 
              if l >= k
              then revLink (acc, Node (l, 2, Leaf k, Nil))
              else revLink (acc, Node (k, 2, Leaf l, Nil))
          | loop (acc, Node (k, _, Leaf l, Nil), r) = 
              if r >= k 
              then revLink (acc, Node (r, 3, Leaf k, Leaf l))
              else if r >= l
              then revLink (acc, Node (k, 3, Leaf r, Leaf l))
              else revLink (acc, Node (k, 3, Leaf l, Leaf r))
          | loop (acc, Node (k, c, l, r), x) = let
            val (k, x) = 
                  if k >= x then (k, x) else (x, k) 
            in      
                if (count l) <= (count r)
                then loop (Node (k, c + 1, Nil, r) :: acc, l, x) 
                else if x >= (key l)
                then loop (Node (k, c + 1, Nil, l) :: acc, r, x)
                else loop (Node (k, c + 1, l, Nil) :: acc, r, x)
            end
        in 
            loop ([], t, x)
        end
    fun extract t = let
        fun loop (acc, Nil) = revLink (acc, Nil)
          | loop (acc, Leaf _) = revLink (acc, Nil)
          | loop (acc, Node (_, _, l, Nil)) = revLink (acc, l)
          | loop (acc, Node (_, c, l, r)) = let
            val k = key l
            val n = left l 
            in
                if n = Nil
                then revLink (acc, Node (k, c - 1, r, Nil))
                else if (key n) >= (key r)
                then loop (Node (k, c - 1, Nil, r) :: acc, l)
                else loop (Node (k, c - 1, r, Nil) :: acc, l)
            end
        in 
            loop ([], t)    
        end
↑  堆排序算法的二叉树实现中，堆建造函数也可以主要采用siftdown函数来完成，这里不需要在节点中保存关于树状态的统计信息：
fun heapSort l = let
    datatype 'a heap
      = Nil 
      | Node of 'a * 'a heap * 'a heap
    fun key Nil = 
          let val SOME a = Int.minInt in a end
      | key (Node (k, _, _)) = k
    fun left Nil = Nil
      | left (Node (_, l, _)) = l
    fun right Nil = Nil
      | right (Node (_, _, r)) = r
    fun leaf k = Node (k, Nil, Nil)     
    fun sift (l, r) =
          if l <> Nil andalso r <> Nil then
              if (key l) >= (key r) then l else r
          else if l <> Nil then l
          else if r <> Nil then r
          else Nil
    fun siftdown (x, l, r) = let
        val superior = sift (l, r)
        in
            if superior = Nil then Node (x, Nil, Nil)
            else if x >= (key superior) then Node (x, l, r) 
            else if superior = l
            then Node (key l, siftdown (x, left l, right l), r)
            else Node (key r, l, siftdown (x, left r, right r))
        end
    fun insert (Nil, x) = Node (x, Nil, Nil)
      | insert (Node (k, l, r), x) = let
        val superior = sift (l, r)
        in
           if x >= k andalso superior = l
           then Node (x, l, insert (r, k))
           else if x >= k
           then Node (x, insert (l, k), r)
           else if superior = l
           then Node (k, l, insert (r, x))
           else Node (k, insert (l, x), r)
        end
    fun extract Nil = Nil
      | extract (Node (_, l, r)) = let
        val superior = sift (l, r)
        in
            if superior = Nil then Nil
            else if superior = l
            then Node (key l, extract l, r)
            else Node (key r, l, extract r)
        end
    fun join (l, r) = extract (Node (key Nil, l, r))
    fun heapify () = let
        fun init (hs, ls, [], _) = (hs, ls)
          | init (hs, ls, x :: xs, flag) =
              if flag 
              then init ((leaf x) :: hs, ls, xs, false)
              else init (hs, x :: ls, xs, true)
        val (hs, ls) = init ([], [], l, true)
        fun loop ([], [], []) = Nil
          | loop ([], [h], []) = h
          | loop ([], [], x :: xs) = 
              loop ([], [leaf x], xs)
          | loop ([], [h], x :: xs) = 
              loop ([], [insert (h, x)], xs)    
          | loop (acc, [], l) =
              loop ([], acc, l)
          | loop (acc, [h], l) = 
              loop ([], h :: acc, l)
          | loop (acc, l :: r :: hs, []) =
              loop (join (l, r) :: acc, hs, [])
          | loop (acc, l :: r :: hs, x :: xs) =
              loop (siftdown (x, l, r) :: acc, hs, xs)  
        in  
            loop ([], hs, ls)
        end
    fun generate h = let
        fun loop (acc, Nil) = acc
          | loop (acc, h) =
              loop ((key h) :: acc, extract h)
        in
            loop ([], h)
        end           
    in
        generate (heapify ())
    end

稍加处理，堆建造函数也可以只用siftdown函数来完成：
    fun heapify () = let
        exception Err;
        fun split () = let
            val (rs, ts) = let
                  fun loop (acci, accj, [], i, n) =
                        if i = n 
                        then (List.revAppend (accj, acci), [])
                        else (acci, accj)
                    | loop (acci, accj, x :: xs, i, n) =  
                        if i = n
                        then loop (List.revAppend (accj, acci),
                                   [x], xs, i + 1, n * 2 + 1)
                        else loop (acci, x :: accj, xs, i + 1, n)
                  in
                      loop ([], [], l, 0, 1)
                  end
            fun loop (hs, ls, [], _) = (hs, ls, ts)
              | loop (hs, ls, x :: xs, flag) =
                  if flag 
                  then loop (x :: hs, ls, xs, false)
                  else loop (hs, x :: ls, xs, true)
            in
                loop ([], [], rs, true)
            end
        fun init () = let 
            val (hs, ls, ts) = split ()
            fun loop (acc, [], []) = (acc, ls)
              | loop (acc, [], ts) =
                  (acc, List.revAppend (ts, ls))
              | loop (acc, k :: hs, []) =
                  loop ((leaf k) :: acc, hs, []) 
              | loop (acc, k :: hs, [x]) = let
                val (k, x) = 
                      if k >= x then (k, x) else (x, k)  
                in
                   loop (Node (k, leaf x, Nil) :: acc, hs, [])
                end
              | loop (acc, k :: hs, l :: r :: rs) = let
                val (k, l, r) = 
                      if k >= l then
                          if l >= r then (k, l, r)
                          else if k >= r then (k, r, l)
                          else (r, k, l)
                      else
                          if k >= r then (l, k, r)
                          else if l >= r then (l, r, k)
                          else (r, l, k)
                in 
                    loop (Node (k, leaf l, leaf r) :: acc, hs, rs)
                end                   
            in  
                loop ([], hs, ts)                
            end
        val (hs, ls) = init ()
        fun loop ([], [], []) = Nil
          | loop ([], [h], []) = h
          | loop ([], [], _) = raise Err
          | loop ([], [h], _) = raise Err
          | loop (acc, [], l) = 
              loop ([], acc, l)
          | loop (acc, [h], l) =
              loop ([], h :: acc, l)
          | loop (acc, l :: r :: hs, []) = raise Err
          | loop (acc, l :: r :: hs, x :: xs) =
              loop (siftdown (x, l, r) :: acc, hs, xs)   
        in  
            loop ([], hs, ls)
        end
↑  排序算法的简单测试代码：
fun printIntList (l: int list) =
      print ((String.concatWith " " (map Int.toString l)) ^ "\n")
fun shuffle (l, n) = let
    fun split (l, acc, i) = 
          if i = 0 then (acc, l)
          else split (tl l, (hd l) :: acc, i - 1)
    fun zip (acc, p, q, flag) =
          if null p then List.revAppend (q, acc)
          else if null q then List.revAppend (p, acc)
          else if flag then zip ((hd p) :: acc, tl p, q, false)
          else zip ((hd q) :: acc, p, tl q, true)
    val (p, q) = split (l, [], n div 2)
    in
        if (null l) then tl [0]
        else zip ([], p, q, true)
    end
fun testsort f n = let
    fun loop (acc, i) =
          if (i <= 0) then acc
          else loop (i :: acc, i - 1)
    val sl = shuffle (loop ([], n), n)
    val ssl = shuffle (sl, n) 
    in
        print ("source list is: ");
        printIntList ssl; 
        print ("result list is: ");
        printIntList (f ssl)
    end