module AvanziniRaml;
data A = A;
// let rec append l1 l2 =
// match l1 with
// | [] -> l2
// | x::xs -> x::(append xs l2)
def List append(List l1, List l2) =
case l1 {
Nil => l2;
Cons(x,xs) => Cons(x,append(xs, l2));
};
// let rec partition f l =
// match l with
// | [] -> ([],[])
// | x::xs ->
// let (cs,bs) = partition f xs in
// if f x then
// (cs,x::bs)
// else
// (x::cs,bs)
def Pair,List> partition(f)(List l) =
case l {
Nil => Pair(Nil, Nil);
Cons(x,xs) => case partition(xs) { // For recursion inside the body of a partially defined
// function, omit the function parameter list.
Pair(cs,bs) => if (f(x)) then Pair(cs, Cons(x,bs)) else Pair(Cons(x,cs),bs);
};
};
// let rec quicksort gt = function
// | [] -> []
// | x::xs ->
// let ys, zs = partition (gt x) xs in
// append (quicksort gt ys) (x :: (quicksort gt zs))
def List quicksort(gt)(List l) =
case l {
Nil => Nil;
Cons(x,xs) =>
let (Pair, List> pair) = partition(gt(x), xs)
in
case pair {
Pair(ys,zs) => append(quicksort(ys), Cons(x,quicksort(zs)));
};
};
// let comp f x g = fun z -> f x (g z)
def List comp(f,g)(List x, A z) = f(x,g(z));
// let rec walk f xs =
// match xs with
// | [] -> (fun z -> z)
// | x::ys -> match x with
// | Left _ -> fun y -> comp (walk f) ys (fun z -> x::z) y
// | Right l ->
// let x' = Right (quicksort f l) in
// fun y -> comp (walk f) ys (fun z -> x'::z) y
def List id(List z) = z;
def List left(w,f)(List ys, A y) = comp(w,f,ys,y);
def List walk(f)(List xs) =
case xs {
Nil => id; // Anonymous functions seem not to work :-/
Cons(x,ys) => case x {
Left(unused) => ((A y) => left(walk(f), z => Cons(x,z), ys, y));
// Right(l) ->
};
};
// let rev_sort f l = walk f l []
// let _ = rev_sort (fun a b -> a <= b) [Right [3;2;1]; Right [2;1;0;-1]; Left 1; Left 2; Left 3; Right []]
{ // Main
}