sample/qsort.in


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// Quick sort

// Rules
qsort(ret) >< [] => ret~[];
qsort(ret) >< (int x):xs =>
	part(x, left, right)~xs,
	qsort(cntl)~left, qsort(cntr)~right,
	Append(ret, x:cntl)~cntr;

// Note: `Append' is implemented as built-in.
// Append(ret, a)~b  -->  ret ~ b@a

part(int x, a, b) >< [] => a~[], b~[];
part(int x, a, b) >< (int y):ys
| y<x => b~(y:cnt), part(x, a, cnt)~ys
| _   => a~(y:cnt), part(x, cnt, b)~ys;


// Nets
qsort(ret)~[3,6,1,9,2];
ret;