(*** CPS ***)
fun id x = x
(************)
fun dup e 0 = []
| dup e n = e :: (dup e (n-1))
fun dupcps e 0 k = k []
| dupcps e n k = dupcps e (n-1) (fn es => k (e :: es))
val t1 = dup 3 5
val t1cps = dupcps 3 5 id
(************)
fun index 0 (x::xs) = x
| index n (x::xs) = index (n-1) xs
fun indexcps 0 (x::xs) k = k x
| indexcps n (x::xs) k = indexcps (n-1) xs k
val t2 = index 4 [1,2,3,4,5,6]
val t2cps = indexcps 4 [1,2,3,4,5,6] id
(************)
fun remove 0 (x::xs) = xs
| remove n (x::xs) = x :: (remove (n-1) xs)
fun removecps 0 (x::xs) k = k xs
| removecps n (x::xs) k = removecps (n-1) xs (fn xs => k (x::xs))
val t3 = remove 3 [1,2,3,4,5,6]
val t3cps = removecps 3 [1,2,3,4,5,6] id
(************)
fun insert y 0 xs = y::xs
| insert y n (x::xs) = x :: (insert y (n-1) xs)
fun insertcps y 0 xs k = k (y::xs)
| insertcps y n (x::xs) k = insertcps y (n-1) xs (fn xs => k (x::xs))
val t4 = insert 5 2 [1,1,1,1,1,1,1]
val t4cps = insertcps 5 2 [1,1,1,1,1,1,1] id
(************)
fun fib 0 = 0
| fib 1 = 1
| fib n = fib(n-1) + fib(n-2)
fun fibcps 0 k = k 0
| fibcps 1 k = k 1
| fibcps n k = fibcps (n-1) (fn v1 => fibcps (n-2) (fn v2 => k (v1+v2)))
val t5 = fib 7
val t5cps = fibcps 7 id
(************)
fun filter pred [] = []
| filter pred (x::xs) = if pred x
then x :: (filter pred xs)
else filter pred xs
fun filtercps predcps [] k = k []
| filtercps predcps (x::xs) k =
predcps x (fn b => if b
then filtercps predcps xs (fn xs => k (x::xs))
else filtercps predcps xs k)
fun pred1 n = if (n < 10)
then true
else if (n > fib (n-10))
then true
else false
fun pred1cps n k = if (n < 10)
then k true
else fibcps (n-10) (fn v => if (n > v)
then k true
else k false)
val t6 = filter pred1 [1,5,10,15,20,15,10,5,1]
val t6cps = filtercps pred1cps [1,5,10,15,20,15,10,5,1] id
(************)
fun map f [] = []
| map f (x::xs) = f x :: (map f xs)
fun mapcps fcps [] k = k []
| mapcps fcps (x::xs) k =
fcps x (fn y => mapcps fcps xs (fn ys => k (y::ys)))
val t7 = map (fn x => x + 3) [1,2,3,4,5]
val t7cps = mapcps (fn x => fn k => k (x + 3)) [1,2,3,4,5] id
(************)
fun powerset [] = [[]]
| powerset (x::xs) =
let val prl = powerset xs
val hpl = map (fn subset => x :: subset) prl
in prl @ hpl
end
fun powersetcps [] k = k [[]]
| powersetcps (x::xs) k =
powersetcps xs (fn prl =>
mapcps (fn subset => fn k => k (x::subset)) prl (fn hpl =>
k (prl @ hpl)))
val t8 = powerset [1,2,3]
val t8cps = powersetcps [1,2,3]
(************)
fun merge [] ys = ys
| merge xs [] = xs
| merge (x::xs) (y::ys) =
if (x < y)
then x :: (merge xs (y::ys))
else y :: (merge (x::xs) ys)
fun mergecps [] ys k = k ys
| mergecps xs [] k = k xs
| mergecps (x::xs) (y::ys) k =
if (x < y)
then mergecps xs (y::ys) (fn ms => k (x::ms))
else mergecps (x::xs) ys (fn ms => k (y::ms))
val t9 = merge [1,3,4] [2]
val t9cps = mergecps [1,3,4] [2] id
(************)
fun split [] = ([],[])
| split [x] = ([x],[])
| split (x1::x2::xs) = let val (l1,l2) = split xs
in (x1::l1, x2::l2)
end
fun splitcps [] k = k ([],[])
| splitcps [x] k = k ([x],[])
| splitcps (x1::x2::xs) k =
splitcps xs (fn (l1,l2) => k (x1::l1, x2::l2))
val t10 = split [1,5,3,7,9,2]
val t10cps = splitcps [1,5,3,7,9,2] id
(************)
fun mergesort [] = []
| mergesort [x] = [x]
| mergesort xs = let val (l1,l2) = split xs
in merge (mergesort l1) (mergesort l2)
end
fun mergesortcps [] k = k []
| mergesortcps [x] k = k [x]
| mergesortcps xs k =
splitcps xs (fn (l1,l2) =>
mergesortcps l1 (fn sl1 =>
mergesortcps l2 (fn sl2 =>
mergecps sl1 sl2 k)))
val t11 = mergesort [5,8,9,2,4,1,3,7,6]
val t11cps = mergesortcps [5,8,9,2,4,1,3,7,6] id