我有以下代码:

memoize f = (map f [0 ..] !!)

fib' 0 = 1
fib' 1 = 1
fib' n = fib' (n - 1) + fib' (n - 2)

fibMemo n = memoize fib' n
fibMemo'  = memoize fib'

(我知道斐波纳契实现具有指数时间复杂度并且不使用缓存)

我第一次执行fibmemo' 30它需要3秒,第二次需要~0秒,因为结果是缓存的.但是第一个版本fibmemo没有得到缓存的结果,它总是需要3秒才能执行.唯一的区别是定义(据我所知,这是相同的).

所以我的问题是,在Haskell中缓存了哪些函数？

我已经阅读了https://wiki.haskell.org/Memoization并且没有解决我的问题.

我正在学习Haskell,我写了一个简单的Fibonacci函数:

fib :: Int -> Int

fib 1 = 1
fib 0 = 0
fib n = (fib (n-1)) + (fib (n-2))

它似乎编译好了,并将此脚本加载到GHCI REPL我可能会乱用一些数字.我试过了

fib 33

并且惊讶地发现结果需要大约4秒钟.(对不起,我不知道如何计算Haskell中的函数,所以自己算一算).

Fib 33并不特别重要.答案不到400万.所以我假设我的代码是不是写得很好,还是有一些问题与我也许做递归的方式(当然,它写得不好的,因为它没有考虑到负整数).问题是,为什么它变慢？任何帮助赞赏.

在 Haskell 中记住递归函数的最快方法是什么？

背景：最近我一直在用 Haskell 解决 Project Euler 问题。许多需要对递归定义的组合或数论函数进行多次计算，例如斐波那契数。如果这些函数被记忆，即函数的结果被缓存以备后用，性能会显着提高。

我见过很多解决这个问题的方法。最优雅的似乎是这个。一种使用 Data.IntMap（或哈希表）和 State monad。此答案中建议的基于树的解决方案，并且此类解决方案似乎相当普遍。再举一个例子，请参阅这篇博文。我见过使用内置函数的其他解决方案。还有一个在第2节在这里与fix，进一步似乎编译器有时可以按摩到memoizing无需额外的工作。还有几个预构建的解决方案。

我想知道对于 Project Euler 中使用的各种函数，哪种记忆方法在实践中最快。我的直觉是哈希表库，因为哈希表似乎是命令式语言中首选的字典结构。纯函数树解决方案很酷，但我的谷歌搜索告诉我，就渐近性能而言，它们比哈希表更糟糕。

编辑

一些评论说这个问题太宽泛而无法回答，经过反思，我同意。因此，让我举两个具体的函数示例进行记忆：一个函数递归计算第 n 个斐波那契数，一个函数递归计算加泰罗尼亚数。我想为大 n 多次计算这些函数。

我知道这些有明确的公式，但让我们忽略它，因为这里的真正重点是使用它们来对记忆技术进行基准测试。

这是Elm语法页面上的Fibonacci代码.好奇的是递归需要记忆还是懒惰的评估会照顾它？

fib n = case n of
  0 -> 1
  1 -> 1
  _ -> fib (n-1) + fib (n-2)

在其他语言(例如Python)中,函数调用的数量将呈指数级增长,n因此if f(30)将计算f(10)为4000次或某些.

• Haskell 这个斐波那契函数如何记忆？

• Python 什么是memoization以及如何在Python中使用它？

有人可以向我解释,为什么下面的代码是memoization:

fib_mem :: Int -> Integer
fib_mem = (map fib [0..] !!)
where fib 0 = 1
      fib 1 = 1
      fib n = fib_mem (n-2) + fib_mem (n-1) 

我想创建一个Fibonacci数列表.我想调用fib x,它应该给我一个列表,直到第x个元素.我如何实现这一目标.

我会像这样计算fib数:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

如何将结果放入列表中以调用列表直到我需要的元素？