def fib(n): if n < 2: return 1 return fib(n-1) + fib(n-2)
can be sped up by memoization:
fib_memo = {} def fib(n): if n < 2: return 1 if not fib_memo.has_key(n): fib_memo[n] = fib(n-1) + fib(n-2) return fib_memo[n]
This implementation technique of memoization is used widely in many programming languages, but it can’t be applied directly to Haskell because Haskell is pure and we don’t want to introduce impurity just to memoize a function. Fortunately, it is possible to memoize a function without side effects thanks to Haskell’s nature of lazy evaluation.
The following
memoize
function takes a function of typeInt -> a
and returns a memoized version of the same function. The trick is to turn a function into a value because, in Haskell, functions are not memoized but values are.
问题:
- 在函数式编程中,函数和值不是同一个东西吗?
- 在纯函数的上下文中,为什么缓存不被视为副作用?
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
。 - user5536315fibMemo = fix (memoize . fib)
这个比较微妙的表达方式,依赖于fix
的定义。在我看来,理解记忆化的第一步是理解f = \x -> let y = expensive 42 in x+y
和f = let y = expensive 42 in \x -> x+y
在操作上的区别(在没有优化的情况下)。前者在每次调用时计算expensive 42
,后者仅计算一次。 - undefined