From 6b3075d90d945d5e7e8fd4d28284ffd99dbeb82e Mon Sep 17 00:00:00 2001 From: Shinya Sato Date: Fri, 24 Sep 2021 16:42:54 +0900 Subject: v0.4.1 --- sample/qsort.in | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 sample/qsort.in (limited to 'sample/qsort.in') diff --git a/sample/qsort.in b/sample/qsort.in new file mode 100644 index 0000000..35de8e4 --- /dev/null +++ b/sample/qsort.in @@ -0,0 +1,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 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; \ No newline at end of file -- cgit v1.2.3