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

Question

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

To do this, I need to save the previously calculated value, as 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 he relies on side effects that are not allowed in Elm.

Answer 1

Fibonacci

The normal recursive definition of fibonacci in Elm will be:

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

Caching

If you want simple caching, maxsnew / lazy library should work. It uses some side effects in native JavaScript code to cache the results of calculations. He looked through the review to verify that the native code does not provide side effects for the Elm user, since for memoisation it is easy to verify that it retains the semantics of the program.

You must be careful about how you use this library. When you create a Lazy value, the first time you force it, it takes time, and from that moment it is cached. But if you re-create the Lazy value several times, they will not use the cache. So, for example, this DOES NOT 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 for fibonacci is a lazy list. I will 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 (\lr -> 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 containing all the fibonacci numbers. Since he himself uses fib3 internally, he will use the same (cached) lazy values ​​and does not have to calculate much.