## sortedlist.pkg
# Compiled by:
# src/lib/compiler/back/low/lib/lib.lib### "Make everything as simple as possible, but no simpler."
### -- Albert Einstein
package sorted_list {
fun enter (new: Int, l)
=
f l
where
fun f (l as h ! t)
=>
if (new < h) new ! l;
elif (new > h) h ! f t;
else l;
fi;
f [] => [new];
end;
end;
fun merge (a, []) => a;
merge ([], a) => a;
merge ( l as (i: Int) ! a,
m as (j: Int) ! b
)
=>
if (j<i) j ! merge (l, b);
else i ! merge (a, i<j ?? m :: b);
fi;
end;
stipulate
fun loop (a ! b ! rest) => loop (merge (a, b) ! loop rest);
loop l => l;
end;
herein
fun foldmerge l
=
head (loop l)
except
head = [];
end;
fun uniq l
=
{ fun split([], l, r) => (l, r);
split (h ! t, l, r) => split (t, r, h ! l);
end;
fun sort [] => [];
sort (l as [_]) => l;
sort (l as [x: Int, y: Int])
=>
if (x == y) [x];
elif (x < y) l;
else [y, x];
fi;
sort l
=>
{ my (l, r) = split (l,[],[]);
merge (sort l, sort r);
};
end;
sort l;
};
fun remove ( x as (xl: Int) ! xr,
y as (yl: Int) ! yr
)
=>
if (xl > yl)
#
yl ! remove (x, yr);
else
remove (
xr,
xl < yl ?? y
:: yr
);
fi;
remove(_, y)
=>
y;
end;
fun rmv (x: Int, l)
=
loop l
where
fun loop NIL => NIL;
loop (a ! b)
=>
x == a ?? b
:: a ! loop b;
end;
end;
fun member l (e: Int)
=
f l
where
fun f [] => FALSE;
f (h ! t) => h < e ?? f t
:: e == h;
end;
end;
fun intersect (NIL, _) => NIL;
intersect (_, NIL) => NIL;
intersect (l as (a: Int) ! b, r as c ! d)
=>
if (a == c) a ! intersect (b, d);
elif (a < c) intersect (b, r);
else intersect (l, d);
fi;
end;
fun difference (NIL, _) => NIL;
difference (l, NIL) => l;
difference (l as (a: Int) ! b, r as c ! d)
=>
if (a== c) difference (b, d);
elif (a < c) a ! difference (b, r);
else difference (l, d);
fi;
end;
};