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
|
effect store<k,v> {
fun put(key: k, value: v): ()
fun get(key: k): maybe<v>
}
fun no-store(body: () -> <store<k,v>,div|e> t): <div|e> t {
with handler {
fun get(key) Nothing
fun put(key, value) {}
} in {
body()
}
}
fun list-store(eq: (k,k) -> total bool, body: () -> <store<k,v>,div|e> t): <div|e> t {
var data := Nil
with handler {
fun get(key) {
data.lookup fn(candidate-key) key.eq(candidate-key)
}
fun put(key, value) {
data := Cons((key, value), data.filter(fn((kk, _)) !kk.eq(key)))
}
} in {
body()
}
}
fun pair-store(body: () -> <store<int,int>,div|e> t): <console,div|e> t {
var first := 0
var second := 1
var idx := 1
with handler {
fun get(key) {
if idx == key then Just(second)
else if idx - 1 == key then Just(first)
else Nothing
}
fun put(key, value) {
if key == idx + 1 then {
idx := idx + 1
first := second
second := value
} else {
println("error: " ++ key.show ++ " := " ++ value.show ++ "; " ++ first.show ++ ", " ++ second.show ++ ", " ++ idx.show)
}
}
} in {
mask<console>(body)
}
}
fun fib(n: int): <div,store<int,int>> int {
match get(n) {
Just(result) -> result
Nothing ->
match n {
0 -> 0
1 -> 1
_ ->
val result = fib(n - 2) + fib(n - 1)
put(n, result)
result
}
}
}
pub fun fib-naive(n: int): div int {
with no-store
fib(n)
}
pub fun fib-list(n: int): div int {
with list-store(fn(a: int, b: int) a == b)
fib(n)
}
pub fun fib-pair(n: int): <div,console> int {
with pair-store
fib(n)
}
|
