-
Notifications
You must be signed in to change notification settings - Fork 0
/
13th_Sept_list_and_trees_4_CPS
86 lines (64 loc) · 1.78 KB
/
13th_Sept_list_and_trees_4_CPS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// converting any recursive function to iterative
function append1(xs, ys) {
return is_null(xs)
? ys
: pair(head(xs), append(tail(xs), ys));
}
// converting to iterative
// first attempt
function append_iter1(xs, ys) {
return is_null(xs)
? ys
: append_iter(tail(xs), pair(head(xs), ys));
}
// wrong cause first list is actually getting reversed
// second attempt: reverse the first list
function append_iter2(xs, ys) {
return is_null(xs)
? ys
: append_iter2(tail(xs), pair(head(xs), ys));
}
function append2(xs, ys) {
return append_iter2(reverse(xs), ys);
}
// now a bit more general - using Continuation-Passing Style (CPS)
function app(current_xs, ys, c) {
return is_null(current_xs)
? c(ys)
: app(tail(current_xs), ys, x => c(pair(head(current_xs), x)));
}
function append(xs, ys){
return app(xs, ys, x => x);
}
// function that has to be stored until the deferred operations are made
// additional paramenter c : continuations
function factorial(n) { // Recursive process
return n === 1
? 1
: n * factorial(n - 1);
}
function fac(n, c){ // Iterative process
return n === 1
? c(1)
: fac(n - 1, x => c(n * x));
}
function factorial_iter(n){
return fac(n, x => x);
}
// another example
import { beside, heart, show, stack } from "rune";
function fractal_5(rune, n) { // recursive
return n === 1
? rune
: beside(rune,
fractal_5(stack(rune, rune), n - 1));
}
function frac(rune, n, c) { // iterative
return n === 1
? c(rune)
: frac(stack(rune, rune), n - 1,
res => c(beside(rune, res)));
}
function fractal_5_iter(rune, n) {
return frac(rune, n, rune => rune);
}