2

我想知道 Haskell 在编译时评估数据结构的深度。

考虑以下列表：

simpleTableMultsList :: [Int]
simpleTableMultsList = [n*m | n <- [1 ..9],m <- [1 ..9]]

这个列表给出了从 1 到 9 的乘法表的表示。现在，假设我们想要改变它，以便我们将两个一位数的乘积表示为一对数字（第一位，第二位）。那么我们可以考虑

simpleTableMultsList :: [(Int,Int)]
simpleTableMultsList = [(k `div` 10, k `rem` 10) | n <- [1 ..9],m <- [1 ..9],let k = n*m]

现在我们可以将一位数的乘法实现为表格查找。耶！！但是，我们希望比这更有效率！所以我们想让这个结构成为一个未装箱的数组。Haskell 提供了一个非常好的方法来做到这一点

import qualified Data.Array.Unboxed as A

然后我们可以这样做：

simpleTableMults :: A.Array (Int,Int) (Int,Int)
simpleTableMults = A.listArray ((1,1),(9,9)) simpleTableMultsList

现在，如果我想要两个一位数 n 和 m 的常数时间乘法，我可以这样做：

simpleTableMults ! (n,m)

这很棒！现在假设我编译了我们一直在研究的这个模块。是否对 simpleTableMults 进行了全面评估，以便在我运行计算时 simpleTableMults ！（n，m），程序确实在内存中进行查找......或者它是否必须首先在内存中构建数据结构。由于它是一个未装箱的数组，我的理解是必须立即创建数组并且对其元素完全严格 - 以便对数组的所有元素进行全面评估。

所以我的问题是：这个评估什么时候发生，我可以强制它在编译时发生吗？

- - - - 编辑 - - - - - - - -

我试图进一步挖掘这个！我尝试编译和检查有关核心的信息。似乎 GHC 在编译时对代码进行了大量缩减。我希望我能更多地了解核心以便能够说出来。如果我们编译

ghc -O2 -ddump-simpl-stats Main.hs

我们可以看到执行了 98 次 beta 缩减，执行了一次 unpack-list 操作，展开了很多东西，执行了一堆内联（大约 150 次）。它甚至会告诉你 beta 减少发生在哪里，......因为 IxArray 这个词即将到来，我更好奇是否正在发生某种简化。现在从我的角度来看，有趣的是添加

simpleTableMults = D.deepseq t t
where t = A.listArray ((1,1),(9,9)) simpleTableMultsList

在编译时大大增加了 beta 缩减、内联和简化的数量。如果我可以将编译后的代码加载到某种调试器中并“查看”数据结构，那就太好了！就目前而言，我比以前更加迷茫。

------ 编辑 2 -------------

我仍然不知道正在执行哪些 beta 减少。但是，我确实根据 sassa-nf 的响应响应发现了一些有趣的事情。对于以下实验，我使用了 ghc-heap-view 包。我根据 Sassa-NF 的答案更改了 Array 在源代码中的表示方式。我将程序加载到 GHCi 中，然后立即调用

:printHeap simpleTableMults

正如预期的那样，索引太大异常。但是在建议的解包数据类型下，我得到了一个带有 toArray 和一堆 _thunk 以及一些 _fun 的 let 表达式。还不太清楚这些是什么意思……另一个有趣的事情是，通过在源代码中使用 seq 或其他一些严格的强制，我最终得到了 let 中的所有 _thunk。如果有帮助，我可以上传确切的排放量。

此外，如果我执行单个索引，则数组在所有情况下都会得到完全评估。

此外，无法通过优化调用 ghci，因此我可能无法获得与使用 GHC -O2 编译时相同的结果。

4

1 回答 1

2

我们夸大其词：

import qualified Data.Array.Unboxed as A

simpleTableMults :: A.Array (Int,Int) (Int,Int)
simpleTableMults = A.listArray ((1,1),(10000,2000))
    [(k `div` 10, k `rem` 10) | n <- [1 ..10000],m <- [1 ..2000],let k = n*m]

main = print $ simpleTableMults A.! (10000,1000)

然后

ghc -O2 -prof b.hs
b +RTS -hy
......Out of memory
hp2hs b.exe.hp

发生了什么？！你可以看到堆消耗图超过 1GB，然后它就死了。

好吧，这对是急切计算的，但是这对的预测是惰性的，所以我们最终需要计算大量的 thunkk ``div`` 10和k ``rem`` 10。

import qualified Data.Array.Unboxed as A

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Int deriving (Show)
simpleTableMults :: A.Array (Int,Int) P
simpleTableMults = A.listArray ((1,1),(10000,2000))
          [P (k `div` 10) (k `rem` 10) | 
             n <- [1 ..10000],m <- [1 ..2000],let k = n*m]

main = print $ simpleTableMults A.! (10000,1000)

这个很好，因为我们急切地计算了这对。

于 2013-09-13T08:53:16.973 回答