Is there a way to cache a function result in elm?

Question

I want to calculate nth Fibonacci number with O(1) complexity and O(n_max) preprocessing.

To do it, I need to store previously calculated value like in this C++ code:

#include<vector>
using namespace std;
vector<int> cache;
int fibonacci(int n)
{
    if(n<=0)
        return 0;
    if(cache.size()>n-1)
        return cache[n-1];
    int res;
    if(n<=2)
        res=1;
    else
        res=fibonacci(n-1)+fibonacci(n-2);
    cache.push_back(res);
    return res;
}

But it relies on side effects which are not allowed in Elm.

Answer 1

Fibonacci

A normal recursive definition of fibonacci in Elm would be:

fib1 n = if n <= 1 then n else fib1 (n-2) + fib1 (n-1)

Caching

If you want simple caching, the maxsnew/lazy library should work. It uses some side effects in the native JavaScript code to cache computation results. It went through a review to check that the native code doesn't expose side-effects to the Elm user, for memoisation it's easy to check that it preserves the semantics of the program.

You should be careful in how you use this library. When you create a Lazy value, the first time you force it it will take time, and from then on it's cached. But if you recreate the Lazy value multiple times, those won't share a cache. So for example, this DOESN'T work:

fib2 n = Lazy.lazy (\() ->
  if n <= 1
    then n
    else Lazy.force (fib2 (n-2)) + Lazy.force (fib2 (n-1)))

Working solution

What I usually see used for fibonacci is a lazy list. I'll just give the whole compiling piece of code:

import Lazy exposing (Lazy)
import Debug

-- slow
fib1 n = if n <= 1 then n else fib1 (n-2) + fib1 (n-1)
-- still just as slow
fib2 n = Lazy.lazy <| \() -> if n <= 1 then n else Lazy.force (fib2 (n-2)) + Lazy.force (fib2 (n-1))

type List a = Empty | Node a (Lazy (List a))

cons : a -> Lazy (List a) -> Lazy (List a)
cons first rest =
    Lazy.lazy <| \() -> Node first rest

unsafeTail : Lazy (List a) -> Lazy (List a)
unsafeTail ll = case Lazy.force ll of
  Empty    -> Debug.crash "unsafeTail: empty lazy list"
  Node _ t -> t

map2 : (a -> b -> c) -> Lazy (List a) -> Lazy (List b) -> Lazy (List c)
map2 f ll lr = Lazy.map2 (\l r -> case (l,r) of
    (Node lh lt, Node rh rt) -> Node (f lh rh) (map2 f lt rt)
  ) ll lr

-- lazy list you can index into, better speed
fib3 = cons 0 (cons 1 (map2 (+) fib3 (unsafeTail fib3)))

So fib3 is a lazy list that has all the fibonacci numbers. Because it uses fib3 itself internally, it'll use the same (cached) lazy values and not need to compute much.