懒惰和多态的价值观

Question

(对于以下内容,简化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]

这是完全同构的(毕竟,唯一可以做的 ShowVal就是show它).

懒惰使得这个特别好,因为对于列表中的每个值,结果show都是自动记忆的,因此不会String多次计算(并且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 ReadVal等同于通用函数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约束？ - 也可以.)

Answer 1

懒惰使得这一点特别好,因为对于列表中的每个值,show的结果是自动memoized,因此不会多次计算String(并且根本不计算未使用的字符串).

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

懒惰意味着不需要的东西,不计算.这并不意味着所有计算值都是共享的.您仍然需要引入显式共享(通过您自己的表).

Answer 2

这是更明确方法的实现；它需要Typeable，因为否则就没有什么可以在备忘录表上键入。我的记忆代码基于uglymemo；可能有一种方法可以让它与纯粹的记忆一起工作，但我不确定。这很棘手，因为您必须在Any 创建的隐式函数之外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")