arrays - Haskell 数据结构上的常量传播？

Question

我想知道 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 答案更改了源中数组的表示方式。我将程序加载到 GHCi 中，并立即调用

:printHeap simpleTableMults

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

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

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

Answer 1

让我们夸张一下:

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，然后就死掉了。

好吧，这对是急切计算的，但是这对的投影是惰性的，所以我们最终用大量的重击来计算 k ``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)

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