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

かなり技術的な理由から、それはかなり不可能です。型クラスはオープンであるため、ポリモーフィック定数は、コンパイル時に制約を満たす型の数を必ずしも「見る」ことができないため、多くのモノモーフィック サンクを割り当てることができません。一方、型クラスは、それが生成する可能性のあるすべての定数を見ることができないため、型クラス ディクショナリにモノモーフィック サンクを割り当てることはできません。

モノモーフィック サンクを割り当てるタイプを明示的に指定する必要があります。

于 2014-07-31T12:26:59.350 に答える
6

Typeable制約を追加しnて、グラウンド タイプごとに異なるメモ化テーブルを使用することができますn。おそらく、これには多くのことを利用する必要がありますがDynamic、castこれは最適ではありません。また、少しハックな感じもします。

もちろん、依存型付けされた言語では、from を(n : Num) -> [n]必要としないマップをモデル化できます。おそらく、そのようなものは、GADT とある種の具体化機構を利用してシミュレートできます。castsDynamic

于 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''ため、すぐにメモ化する 3 つの唯一の実装です。

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 に答える