是否有自动方法在Haskell中记忆全局多态值？

Question

多态"常量",5 :: Num a => a不是真正的常量,而是字典参数的功能.因此,如果你定义

primes :: Num n => [n]
primes = ...

^{当然不好的例子,这里没有充分的理由让它具有多态性...我真正感兴趣的是如果你尝试全局记忆一个非平凡的多态函数,例如memo-tries.}
那么这个序列将不会在来自不同站点的呼叫之间共享,这在性能方面并不好.(这不是Haskell标准用可怕的单态限制祝福我们的主要原因吗？)

我能看到如何强制共享的唯一方法是为约束类的每个实例设置一个单形"标记".例如

erastothenes :: Num n => [n]
erastothenes = ...

class (Num n) => HasPrimes n where
  -- | @'primes' ? 'erastothenes'@
  primes :: [n]

integerPrimes :: [Integer]
integerPrimes = erastothenes

instance HasPrimes Integer where
  primes = integerPrimes

......在优雅方面不是很好.

有没有更好的方法来实现这样的备忘录？

Answer 1

出于相当技术原因,这是不可能的.类型类是开放的,多态常量不能在编译时必然"看到"有多少类型满足约束,因此它不能分配那么多单态thunk.另一方面,类型类当然无法看到它可能生成的所有可能的常量,因此无法在类型类字典中分配单态thunk.

您必须明确提及您希望分配单态thunk的任何类型.

Answer 2

可以为每种地面类型添加Typeable约束n并使用不同的记忆表n.你可能会需要利用Dynamic和cast很多关于这一点,这是最理想的.它也感觉有点hackish.

当然,在依赖类型的语言中,人们可以(n : Num) -> [n]对不需要castss 的地图进行建模Dynamic.也许这样的东西可以模拟利用GADT和某种物化机制.

Answer 3

如果启用ConstraintKinds和ExistentialQuantification（或GADTs），您可以具体化类型类字典：

\n\n

{-# LANGUAGE ConstraintKinds, ExistentialQuantification #-}\n\ndata Dict a = a => Dict\n

\n\n

如果我们尝试一下

\n\n

fibs :: Num n => [n]\nfibs = 1 : 1 : zipWith (+) fibs (drop 1 fibs)\n\nfibs' :: [Integer]\nfibs' = fibs\n\n\nfibsWithDict :: Dict (Num n) -> [n]\nfibsWithDict Dict = fs\n  where\n    fs = 1 : 1 : zipWith (+) fs (drop 1 fs)\n\nfibs'' :: [Integer]\nfibs'' = fibsWithDict Dict\n

\n\n

在 GHCi 中我们看到

\n\n

\xce\xbb> :set +s\n\xce\xbb> \n\xce\xbb> fibs !! 29\n832040\n(2.66 secs, 721235304 bytes)\n\xce\xbb> \n\xce\xbb> fibs !! 29\n832040\n(2.52 secs, 714054736 bytes)\n\xce\xbb> \n\xce\xbb> \n\xce\xbb> fibs' !! 29\n832040\n(2.67 secs, 713510568 bytes)\n\xce\xbb> \n\xce\xbb> fibs' !! 29\n832040\n(0.00 secs, 1034296 bytes)\n\xce\xbb> \n\xce\xbb> \n\xce\xbb> fibs'' !! 29\n832040\n(0.00 secs, 1032624 bytes)\n

\n\n

这fibs''也是这三个方法中唯一可以立即记住的实现。

\n\n

请注意，我们必须在Dict构造函数上进行模式匹配。否则，我们将收到一个关于n不被限制拥有Num实例的错误（就像您期望的那样，如果我们的签名只是fibsWithDict :: a -> [n]）。

\n\n

这是一个完整的解决方案，因为您可以将其视为fibsWithDict Dict一个立即记忆您向其抛出的任何类型的表达式（只要它是 的实例Num）。例如：

\n\n

\xce\xbb> (fibsWithDict Dict !! 29) :: Double\n832040.0\n(0.00 secs, 1028384 bytes)\n

\n\n

编辑：看起来这里不需要显式字典传递，可以通过使用ScopedTypeVariables本地绑定来隐式完成：

\n\n

{-# LANGUAGE ScopedTypeVariables #-}\n\nfibsImplicitDict :: forall a. Num a => [a]\nfibsImplicitDict\n  = let fs :: [a]\n        fs = 1 : 1 : zipWith (+) fs (drop 1 fs)\n    in\n    fs\n

\n\n

（感谢 Bennofs 的见解！）

\n