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]

这也是众所周知的，这是相对无用的，因为相反，可以只构造一个 list :: [String]，例如

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

这完全是同构的（毕竟，唯一可以用 a 做的 ShowVal就是show它）。

懒惰使这特别好，因为对于列表中的每个值，结果show都会自动记忆，因此 noString被计算多次（并且String根本不计算未使用的 s ）。

AShowVal等价于存在元组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类型类是开放的。）

AReadVal等价于通用函数forall 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作为一种类型—— String每次使用值时都会解析 。有没有一种简单的方法可以在保持ReadVal多态性的同时获得记忆？

（如果可能的话，让 GHC 自动完成它，类似于这种Show情况，将是理想的。更明确的记忆方法 - 也许通过添加Typeable约束？ - 也可以。）

4

2 回答 2

5

懒惰使这特别好，因为对于列表中的每个值，显示的结果都会自动记忆，因此不会多次计算字符串（并且根本不会计算未使用的字符串）。

这个前提是不正确的。引擎盖下没有神奇的备忘录表。

懒惰意味着不需要的东西，不计算。这并不意味着所有计算值都是共享的。您仍然必须引入显式共享（通过您自己的表）。

于 2012-04-16T13:06:07.090 回答
2

这是更明确方法的实现；它需要Typeable，因为否则将没有任何东西可以键入备忘录表。我将记忆代码基于丑陋的备忘录；可能有一种方法可以让它与纯记忆一起工作，但我不确定。这很棘手，因为您必须在任何创建的隐式函数之外forall a. (Read a, Typeable a) => ...构建表，否则您最终每次调用都构建一个表，这是无用的。

{-# 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 回答