haskell - 创建一个新表达式，不包含前一个表达式的指针

Question

我正在看书https://www.packtpub.com/application-development/haskell-high-performance-programming并试图弄清楚这两个函数之间有什么区别:

这个函数确实会记住中间数字:

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) 

这不是:

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

作者试图解释如下:

Running fib_mem_arg with anything but very small arguments, one can confirm it does no memoization. Even though we can see that map fib [0..] does not depend on the argument number and could be memorized, it will not be, because applying an argument to a function will create a new expression that cannot implicitly have pointers to expressions from previous function applications.

他用粗体标记的句子是什么意思？有人可以给我一个简单的例子吗？

为什么fib_mem是一个常量应用形式？

Answer 1

Why fib_mem is a constant applicative form?

不是fib_mem，而是(map fib [0..] !!)。这是一个CAF因为它是一个部分应用的函数(!!)。因此，它会受到内存保留的影响。

(另请参阅:What are super combinators and constant applicative forms?)

由于该类型是单态的，因此即使在调用 fib_mem 之间，它也会保留在内存中，实际上就像将 map fib [0..]“ float ”到顶层，就像定义为

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

如果类型是多态的，则不可能 float 到顶层，但它仍会在每次调用 fib_mem 期间保留，就像定义为

fib_mem_p :: Num a => Int -> a
fib_mem_p = (the_list !!)
            where fib 0 = 1
                  fib 1 = 1
                  fib n = (the_list !! (n-2)) + (the_list !! (n-1))
                  the_list = map fib [0..]

要查看差异，请在 GHCi 属性处计算 fib_mem_m 10000 两次。第二次尝试将花费 0 秒。但是fib_mem_p 10000每次调用都会花费相同的时间。它仍然会像第一个一样快，因此仍然会进行内存，只是在调用之间不会保留它。

通过这种定义风格，fib_mem_arg 中的完整应用程序也将被内存 - 就像上面的那样，不是在对 fib_mem_arg 的调用之间，而是仅在每次通话期间。

fib_mem_arg :: Num a => Int -> Integer  -- or polymorphic, makes no difference
fib_mem_arg x = the_list !! x
            where fib 0 = 1
                  fib 1 = 1
                  fib n = (the_list !! (n-2)) + (the_list !! (n-1))
                  the_list = map fib [0..]