'Share' 或 'cache' 仅由不明确类型参数化的表达式？

Question

我有一个棘手的问题；

所以，我知道 GHC 会“缓存”（因为缺少更好的术语）顶级定义并且只计算一次，例如:

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

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

我想这样做，但是计算依赖于类型级别的上下文；一个简化的例子是：

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

所以这里有趣的是，dependentList 没有一个“单一的”可缓存值；但是一旦应用了一个类型，它就会减少到一个常数，所以理论上一旦类型检查器运行s，GHC 就可以识别出几个点都依赖于“相同的”dependentList；例如（使用 TypeApplications）

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

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

我的情况有点复杂，但应该遵循与示例相同的约束，但是我的 dependentList 类值需要大量计算。

如果可能的话，我一点也不反对使用类型类来做这件事； GHC 缓存和重用类型类字典吗？也许我可以将它烘焙到类型类字典中的常量中以获得缓存？

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

我更愿意以编译器可以解决的方式来执行此操作，而不是使用手动记忆，但我对想法持开放态度:)

感谢您的宝贵时间！

Answer 1

根据@crockeea 的建议，我运行进行了一项实验；这是尝试使用带有多态模糊类型变量的顶级常量，以及一个实际常量只是为了好玩，每个都包含一个 'trace'

dependant :: forall n . KnownNat n => Natural
dependant = trace ("eval: " ++ show (natVal (Proxy @n))) (natVal (Proxy @n))

constantVal :: Natural
constantVal = trace "constant val: 1" 1


main :: IO ()
main = do
  print (dependant @1)
  print (dependant @1)
  print constantVal
  print constantVal

结果很不幸：

λ> main
eval: 1
1
eval: 1
1
constant val: 1
1
1

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

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

class DependantClass n where
  classNat :: Natural

instance (KnownNat n) => DependantClass (n :: Nat) where
  classNat = trace ("dependant class: " ++ show (natVal (Proxy @n))) (natVal (Proxy @n))

main :: IO ()
main = do
  print (classNat @1)
  print (classNat @1)
  print (classNat @2)

结果：

λ> main
dependant class: 1
1
1
dependant class: 2
2

就让 GHC 在编译时执行这些操作而言，看起来您可以使用 .

使用 TemplateHaskell 中的 lift 来执行此操作

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

'Share' 或 'cache' 仅由不明确类型参数化的表达式？

'Share' or 'cache' an expression parameterized by only ambiguous types?

optimization

performance

caching

haskell

ghc