diff options
Diffstat (limited to 'common.sml')
| -rw-r--r-- | common.sml | 26 |
1 files changed, 26 insertions, 0 deletions
@@ -4,6 +4,32 @@ fun $ (x, y) = x y infixr 0 $ fun id x = x +val compare = fn a => fn b => Int.compare (a, b) + +fun sort _ [] = [] + | sort _ [x] = [x] + | sort le l = + let + fun divide [] accp = accp + | divide [x] (acc1, acc2) = (x :: acc1, acc2) + | divide (x :: y :: tail) (acc1, acc2) = + divide tail (x :: acc1, y :: acc2) + val (part1, part2) = divide l ([], []) + val part1 = sort le part1 + val part2 = sort le part2 + + fun merge [] [] acc = acc + | merge [] ys acc = rev $ List.revAppend (ys, acc) + | merge xs [] acc = rev $ List.revAppend (xs, acc) + | merge (x :: xs) (y :: ys) acc = + if le (x, y) then + merge xs (y :: ys) (x :: acc) + else + merge (x :: xs) ys (y :: acc) + in + merge part1 part2 [] + end + fun assert truth = if not truth then raise Unreachable else () structure Fold = struct |