Add a semi-memoized fibonacci with lists

1 files changed, 35 insertions, 0 deletions

diff --git a/examples/fastfib.sil b/examples/fastfib.sil
new file mode 100644
index 0000000..0c28ccd
--- /dev/null
+++ b/examples/fastfib.sil
@@ -0,0 +1,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
+}