怠惰や多型の値

Question

（以下の場合は、

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

にShowとReadを簡素化し、readが失敗したことがないことを前提としています。）

それは1フォームの実存種類を作ることができることはよく知られているのです

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

そして、このような

などの "異種のリスト" :: [ShowVal]を構築

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

また、代わりに、1は 直後のすべて（リスト:: [String]、正確に同型であるような

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

を構築することができるので、これは、唯一のものは比較的無用であることはよく知られています1つは、 ShowValはshowです）とすることができます。リスト内の各値に対して、showの 結果を自動的にメモ化されるので、何Stringが使用されない以上 回（及びString sはで計算されていない計算されないので

怠惰は、これは特にいいせるすべて）。

ShowVal関数がShow辞書実存タプルexists a. (a -> String, a)、 と等価です。

同様の構築物がReadのために行うことができます：readたちは本当にそれを必要としないことを意味している（ReadValが ユニバーサルいうより実存で、その戻り値で多型であるため、

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

なお、 で、ハスケルにはファーストクラスのユニバーサルがありますが、 にはShowと似ています。

我々はまた、リスト:: [ReadVal]行うことができます：ちょうどShowと同様

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

を、リスト:: [ReadVal]は（我々は常に取得することができ、そのよう

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

として リスト:: [String]と同型であります元String戻ると

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

Read

型クラスが開いているため。）

ReadValforall a. (String -> a) -> a （CPSスタイルの表現）ユニバーサル関数と等価です。ここで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制約を加えることで - ？もOKでしょう。 ）

Answer 1

もっと明示的なアプローチの実装です。が必要です。それ以外の場合は、メモテーブルをキーすることはありません。メモコードは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") 

Answer 2

リストの各値に対して、showの結果が自動的にメモされるので、Stringは何度も計算されません（使用されていないStringは計算されません）。すべて）。

この前提は正しくありません。フードの下に魔法のメモの表はありません。

怠惰は、必要でないものが計算されないことを意味します。すべての計算値が共有されているわけではありません。明示的な共有を導入する必要があります（独自の表を使用して）。