在 Haskell 中共享数据

Question

我想了解 Haskell 中的内存共享机制是如何工作的。事实上，编写计算斐波那数列项的函数的方法是：

fibo' n = f n
  where 
    f 0 = 1
    f 1 = 1
    f n = fibs !! (n-1) + fibs !! (n-2)
    fibs = [f x | x <- [0..]]

这假设有一个改进，即小纤维列表不会多次评估，而是在调用之间共享，但我不确定这个假设或其工作原理。

Answer 1

作为第一个近似，您可以仅使用变量范围来预测将共享的内容。

所有使用的位置fibs都在同一范围内，因此该名称的每次出现都会解析为内存中的同一对象。这意味着每次f在一个顶级fibo'调用中调用时，都会有一个fibs列表。它在f呼叫之间共享。

然而，fibs是在一个where范围内定义的，附加到一个函数方程fibo' n =。这意味着范围是fibo'（在某些特定的n）的每次调用“内部”；每次调用时，子句中定义的所有名称都where引用内存中的不同对象。fibo'（这就像在函数内部定义的局部变量在任何主流编程语言中的工作方式一样）

这里有一个函数，它将使用预先计算的斐波那契数列表来保存一个顶级调用中的重新计算，但随后将其丢弃并在下一个顶级调用中从头开始。

这可能正是您想要的，所以这本身并没有错。如果在顶级应用程序之外的fibs范围中定义，那么它将在所有调用之间共享，但这也意味着它将永久占用内存以保持可用于下一次调用。由于 Haskell 中的对象可以在更深入地评估时在内存中扩展，因此这可以被视为内存泄漏。在每个顶级调用之后将其丢弃意味着多个调用会重复一些工作，但您仅使用加速每个调用所需的内存（而不是您曾经进行过的最大调用所需的内存），并且仅当它正在运行。因此哪种方式“更好”取决于程序的其余部分使用此函数执行的操作，而不是此函数本身。

请注意，子句中的任何定义where实际上都没有使用 的参数fibo'，并且fibo'它本身并没有真正“做任何事情”；它只是立即将呼叫转发至f。where因此，将代码放入这样的代码中唯一“有趣”的效果是创建一个范围，您可以在其中定义fibs顶级调用内部但内部f调用外部。（我认为访问控制效果并不有趣）。如果您不希望这样，并且确实希望fibs在调用之间共享，那么像这样定义代码会更简单：

fibo'' 0 = 1
fibo'' 1 = 1
fibo'' n = fibs !! (n-1) + fibs !! (n-2)

fibs = [fibo'' x | x <- [0..]]

现在fibs只是全局范围内的单个对象，并将在所有调用之间共享（但也会在所有调用之间占用内存）。

如果您确实关心访问控制（fibs如果它是在本地范围内定义的，则没有其他东西可以访问，但如果它是在全局范围内定义的，则可以），您可以这样做：

fibo''' = f
  where 
    f 0 = 1
    f 1 = 1
    f n = fibs !! (n-1) + fibs !! (n-2)
    fibs = [f x | x <- [0..]]

这里fibs( 和f) 是在本地范围内定义的。但 所附的方程where就是fibo''' = f。该本地作用域仍然位于顶级调用的“外部”，因为该作用域是在fibo'''接收其参数之前“进入”的。而原始版本fibo'附加where了一个方程，该方程已经将参数带入n范围，因此在每次进行顶级调用后where都会“进入”范围。

现在，我确实以“作为第一个近似值”开始这篇文章。编译器可以重新组织您的代码以尝试优化它。例如，理论上它可以注意到fibs不依赖于参数n，因此将其移到顶级调用之外，使您的fibo'行为像fibo'''. 或者（再次理论上）它可以决定内联，fibs这将删除所有共享并使您的fibo'行为像一个天真的递归斐波那契计算器。

然而，实际上，做这两件事中的任何一个都是极不可能的。它“允许”进行任何不会改变代码最终结果的转换，但 GHC 开发人员实际放入编译器中的转换旨在使您的代码更好。因此，他们非常努力地避免以导致大量内存泄漏或速度减慢的方式增加或减少共享。

因此，虽然编译和优化的代码经常与您实际编写的代码有很大不同，但在“如果您给某些内容命名，则同一范围内对该名称的所有使用都将被共享”的假设下推理您的代码是相当安全的。 。您只需要注意何时“输入”确切的本地范围，以便知道什么算作“在同一范围内”。