10

多态“常量”，例如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

......这在优雅方面并不好。

有没有更好的方法来实现这样的记忆？

4

3 回答 3

9

由于相当技术原因，这是相当不可能的。类型类是开放的，所以多态常量在编译时不一定“看到”有多少类型满足约束，因此它不能分配那么多单态 thunk。另一方面，类型类当然看不到它可能生成的所有可能常量，因此单态 thunk 不能在类型类字典中分配。

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

于 2014-07-31T12:26:59.350 回答
6

可以为每种地面类型添加Typeable约束n并使用不同的记忆表n。您可能需要为此进行大量利用Dynamic，cast这是次优的。它也感觉有点骇人听闻。

(n : Num) -> [n]当然，在依赖类型语言中，可以对不需要castss from的映射建模Dynamic。也许可以利用 GADT 和某种具体化机制来模拟类似的事情。

于 2014-07-31T14:38:05.957 回答
3

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

{-# LANGUAGE ConstraintKinds, ExistentialQuantification #-}

data Dict a = a => Dict

如果我们试试这个

fibs :: Num n => [n]
fibs = 1 : 1 : zipWith (+) fibs (drop 1 fibs)

fibs' :: [Integer]
fibs' = fibs


fibsWithDict :: Dict (Num n) -> [n]
fibsWithDict Dict = fs
  where
    fs = 1 : 1 : zipWith (+) fs (drop 1 fs)

fibs'' :: [Integer]
fibs'' = fibsWithDict Dict

在 GHCi 中，我们看到

λ> :set +s
λ> 
λ> fibs !! 29
832040
(2.66 secs, 721235304 bytes)
λ> 
λ> fibs !! 29
832040
(2.52 secs, 714054736 bytes)
λ> 
λ> 
λ> fibs' !! 29
832040
(2.67 secs, 713510568 bytes)
λ> 
λ> fibs' !! 29
832040
(0.00 secs, 1034296 bytes)
λ> 
λ> 
λ> fibs'' !! 29
832040
(0.00 secs, 1032624 bytes)

这fibs''三个立即记忆的唯一实现也是如此。

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

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

λ> (fibsWithDict Dict !! 29) :: Double
832040.0
(0.00 secs, 1028384 bytes)

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

{-# LANGUAGE ScopedTypeVariables #-}

fibsImplicitDict :: forall a. Num a => [a]
fibsImplicitDict
  = let fs :: [a]
        fs = 1 : 1 : zipWith (+) fs (drop 1 fs)
    in
    fs

（感谢 bennofs 提供的见解！）

于 2014-08-26T05:07:46.470 回答