7

(以下では、 と を単純化ShowしReadます。

class Show a where show :: a -> String
class Read a where read :: String -> a

readそして、決して失敗しないと仮定してください。)

フォームの存在型を作成できることはよく知られています

data ShowVal where
    ShowVal :: forall a. Show a => a -> ShowVal

そして、次の:: [ShowVal]ような「異種リスト」を作成します

l = [ShowVal 4, ShowVal 'Q', ShowVal True]

これは比較的役に立たないこともよく知られています:: [String].

l = [show 4, show 'Q', show True]

これはまさに同形です (結局のところ、a でできること ShowValはshowそれだけです)。

リスト内の各値に対して、 の結果がshow自動的にメモ化されるため、遅延性が特に優れています。したがって、 noStringは複数回計算されます (String使用されていない s はまったく計算されません)。

Aは、関数が辞書でShowValある存在タプルと同等です。exists a. (a -> String, a)Show

についても同様の構成を作成できますRead。

data ReadVal where
    ReadVal :: (forall a. Read a => a) -> ReadVal

readは戻り値がポリモーフィックであるため、存在的ではなく普遍的であることに注意してくださいReadVal(つまり、Haskell にはファーストクラスの普遍性があるため、実際にはまったく必要ないということです。ただし、ここではそれを使用して、Show）。

リストを作成することもできます:: [ReadVal]:

l = [ReadVal (read "4"), ReadVal (read "'Q'"), ReadVal (read "True")]

と同様にShow、リストは次のよう:: [ReadVal]にリストに同形です。:: [String]

l = ["4", "'Q'", "True"]

(いつでもオリジナルStringを取り戻すことができます

newtype Foo = Foo String
instance Read Foo where read = Foo

Read型クラスが開いているためです。)

Aはユニバーサル関数 (CPS スタイルの表現)ReadValと同等です。forall a. (String -> a) -> aここでは、戻り値は引数ではなく多態的であるため、ReadディクショナリはReadValプロデューサーではなくユーザーによって提供されます。

Stringただし、これらの表現のどちらでも、 を使用した表現で得られる自動メモ化は得られませんShow。私たちの型は高価な操作なので、同じ型に対して同じものを複数回read計算したくないとしましょう 。String

閉じた型があれば、次のようなことができます。

data ReadVal = ReadVal { asInt :: Int, asChar :: Char, asBool :: Bool }

そして、値を使用します

ReadVal { asInt = read s, asChar = read s, asBool = read s }

または、それらの線に沿った何か。

しかし、この場合、ReadValを 1 つの型として のみ使用したとしてStringも、値が使用されるたびに が解析されます。多態性を保ちながらメモ化する簡単な方法はありReadValますか?

(この場合と同様に、GHC に自動的に実行させるのShowが理想的です。何らかの方法で可能であれば、より明示的なメモ化アプローチ (おそらくTypeable制約を追加することによるものでしょうか?) も問題ありません。)

4

2 に答える 2

5

リスト内の各値に対して、 show の結果が自動的にメモ化されるため、遅延が特に便利です。そのため、文字列は 2 回以上計算されません (使用されていない文字列はまったく計算されません)。

この前提は正しくありません。ボンネットの下に魔法のメモテーブルはありません。

怠惰とは、必要のないもの、計算されていないものを意味します。すべての計算値が共有されるわけではありません。(独自のテーブルを介して) 明示的な共有を導入する必要があります。

于 2012-04-16T13:06:07.090 に答える
2

これは、より明示的なアプローチの実装です。が必要Typeableです。そうしないと、メモ テーブルにキーを設定するものが何もないからです。私はメモ化コードをuglymemoに基づいていました。これを純粋なメモ化で機能させる方法があるかもしれませんが、よくわかりません。作成する暗黙的な関数の外でテーブルを構築する必要があるため、forall a. (Read a, Typeable a) => ...注意が必要です。そうしないと、呼び出しごとに 1 つのテーブルを構築することになり、役に立たなくなります。

{-# LANGUAGE GADTs, RankNTypes #-}

import Data.Dynamic
import Control.Concurrent.MVar
import Data.HashMap.Strict (HashMap)
import qualified Data.HashMap.Strict as HM
import System.IO.Unsafe

data ReadVal where
    ReadVal :: { useReadVal :: forall a. (Read a, Typeable a) => a } -> ReadVal

mkReadVal :: String -> ReadVal
mkReadVal s = unsafePerformIO $ do
    v <- newMVar HM.empty
    return $ ReadVal (readVal v)
  where
    readVal :: (Read a, Typeable a) => MVar (HashMap TypeRep Dynamic) -> a
    readVal v = unsafePerformIO $ do
        m <- readMVar v
        let r = read s  -- not evaluated
        let typeRep = typeOf r
        case HM.lookup typeRep m of
            Nothing -> do
                modifyMVar_ v (return . HM.insert typeRep (toDyn r))
                return r
            Just r' -> return $ fromDyn r' (error "impossible")
于 2012-04-16T21:17:10.737 に答える