praeorden, erstat, sorter

gistfile1.sml

(* Opgave 5 *)
datatype 'a trae = K of 'a * ('a trae list)

(* a *)
local
  val v7 = K (7, [])
  val v6 = K (6, [])
  val v5 = K (5, [v6, v7])
  val v1 = K (1, [])
  val v4 = K (4, [v7, v1, v5])
in
  val t7 = K (3, [v4])
end

(* b *)
fun praeorden (K (x, ks)) = x :: concatMap praeorden ks

(* c *)
fun erstat (_, []) = raise Empty
  | erstat (K (x, ks), (y::ys)) =
    let
      val (ks', ys') = foldl (fn (k, (ks', ys)) =>
                                 let val (k', ys') = erstat (k, ys)
                                 in (k'::ks', ys') end) ([], ys) ks
    in
      (K (y, rev ks'), ys')
    end

(* d *)
;load "Listsort";
fun sorter t = #1 (erstat (t, Listsort.sort Int.compare (praeorden t)))