blob: 0c28ccd4765852cda7e4b93c9f160f6055042075 (
plain) (
blame)
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
|
Int length([Int] xs) {
if (xs.nil) {
return 0;
} else {
return 1 + length(xs.tl);
}
}
Int get([Int] xs, Int i) {
if (i == 0) {
return xs.hd;
} else {
return get(xs.tl, i-1);
}
}
// This is not really memoized, as this could be emulated by keeping the last
// two entries in memory. However, real memoization would only make sense with
// an array and sil does not have arrays (yet).
Int fib(Int n) {
[Int] fibs;
fibs := [1,1];
n := n - 2;
while (!(n == 0)) {
fibs := get(fibs,0) + get(fibs,1) : fibs;
n := n - 1;
}
return fibs.hd;
}
Int main() {
return fib(92); // Largest to fit in a 64-bit integer
}
|
