"共享"或"缓存"仅由不明确的类型参数化的表达式？

Question

我有一个棘手的问题;

所以,我知道GHC将"缓存"(缺乏一个更好的术语)顶级定义,只计算一次,例如:

myList :: [Int]
myList = fmap (*10) [0..10]

即使我myList在几个地方使用,GHC注意到该值没有参数,因此它可以共享它并且不会"重建"列表.

我想这样做,但计算依赖于类型级上下文; 一个简单的例子是:

dependentList :: forall n. (KnownNat n) => [Nat]
dependentList = [0..natVal (Proxy @n)]

所以有趣的是,没有'单一'可缓存值dependentList; 但是一旦应用了一种类型,它就减少到一个常数,所以理论上一旦类型检查器运行,GHC就会认识到几个点都依赖于"相同" dependentList; 例如(使用TypeApplications)

main = do
  print (dependentList @5)
  print (dependentList @10)
  print (dependentList @5)

我的问题是,GHC会认识到它可以共享这两个5列表吗？或者它是分别计算每一个？从技术上讲,甚至可以在编译时而不是运行时计算这些值,是否有可能让GHC这样做？

我的情况稍微复杂一些,但是应该遵循与示例相同的约束,但是我的类似dependentList值是计算密集的.

如果能让事情成为可能,我完全不反对使用类型类来做这件事; GHC缓存并重用类型词典吗？也许我可以把它变成类型类词典中的常量来获取缓存？

想法有人吗？或者有人读过我看看这是如何工作的？

我更喜欢这样做,编译器可以解决它而不是使用手动memoization,但我愿意接受:)

谢谢你的时间!

Answer 1

按照@crockeea的建议，我做了一个实验；这里尝试使用带有多态模糊类型变量的顶级常量，并且也是一个只是为了好玩的实际常量，每个常量都包含一个“trace”

\n\n

dependant :: forall n . KnownNat n => Natural\ndependant = trace ("eval: " ++ show (natVal (Proxy @n))) (natVal (Proxy @n))\n\nconstantVal :: Natural\nconstantVal = trace "constant val: 1" 1\n\n\nmain :: IO ()\nmain = do\n  print (dependant @1)\n  print (dependant @1)\n  print constantVal\n  print constantVal\n

\n\n

结果很不幸：

\n\n

\xce\xbb> main\neval: 1\n1\neval: 1\n1\nconstant val: 1\n1\n1\n

\n\n

很明显，每次使用它时，它都会重新评估多态常量。

\n\n

但是，如果我们将常量写入类型类（仍然使用模糊类型），则每个实例似乎只会解析一次字典值，当您知道 GHC 为相同的类实例传递相同的字典时，这是有意义的。当然，它会为不同的实例重新运行代码：

\n\n

\xce\xbb> main\neval: 1\n1\neval: 1\n1\nconstant val: 1\n1\n1\n

\n\n

结果：

\n\n

\xce\xbb> main\ndependant class: 1\n1\n1\ndependant class: 2\n2\n

\n\n

至于让 GHC 在编译时执行这些操作，看起来您可以使用liftTemplateHaskell 使用此技术来执行此操作。

\n\n

不幸的是，您不能在类型类定义中使用它，因为 TH 会抱怨“@n”必须从不同的模块导入（是的 TH），并且在编译时具体未知。您可以在任何使用类型类值的地方执行此操作，但每次提升都会对其进行评估一次，并且您必须在使用它的所有地方进行提升才能获得好处；相当不切实际。

\n