有没有办法在榆树中缓存函数结果？

Question

我想计算具有 O(1) 复杂度和 O(n_max) 预处理的第 n 个斐波那契数。

为此，我需要存储之前计算的值，就像在这个 C++ 代码中一样：

#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;
}

但它依赖于 Elm 中不允许的副作用。

Answer 1

斐波那契

Elm 中斐波那契的正常递归定义是：

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

缓存

如果您想要简单的缓存，maxsnew/lazy library 应该可以。它使用本机 JavaScript 代码中的一些副作用来缓存计算结果。它经过审查以检查本机代码不会向 Elm 用户公开副作用，对于记忆，很容易检查它是否保留了程序的语义。

您应该小心使用这个库。当你创建一个 Lazy 值时，第一次强制它需要时间，从那时起它就会被缓存。但是，如果您多次重新创建 Lazy 值，它们将不会共享缓存。例如，这个不有效：

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

工作解决方案

我通常看到的用于斐波那契的是惰性列表。我将给出整个编译代码：

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)))

所以 fib3 是一个包含所有斐波那契数列的惰性列表。因为它在内部使用 fib3 本身，所以它将使用相同的（缓存的）惰性值并且不需要进行太多计算。

有没有办法在榆树中缓存函数结果？

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

purely-functional

elm

斐波那契

缓存

工作解决方案