如何定义严格的存在类型？

Question

我想在严格的上下文中使用Haskell的存在类型(http://www.haskell.org/haskellwiki/Existential_type).我从haskell-wiki中获取了示例,并尝试使用它创建一个严格的异构映射.需要对地图及其值进行全面评估.

我定义了3种类型来测试它.第一个只是一个简单的严格地图.第二种类型是使用存在类型的异构映射.第三种类型与第二种类型相似,但增加了NFData约束.

虽然第一个简单的例子是真正严格的并且得到了充分的评估,但其他的却不是.即使是使用deepseq的第三种类型,似乎也没有得到充分的评估.

我的问题是:

• 我如何严格定义这种异构类型？
• 如果不可能 - 为什么不呢？有办法解决这个问题吗？

示例来源

{-# LANGUAGE ExistentialQuantification #-}

import GHC.AssertNF
import Control.DeepSeq
import Data.Map.Strict

-- 1) simple container

data Obj a = Obj a

-- using a smart constructor here to ensure arbitrary values are strict
mkObj :: a -> Obj a
mkObj a = Obj $! a

-- using a special String constructor to ensure Strings are always 
-- fully evaluated in this example
mkString :: String -> String
mkString x = force x

xs :: Map Int (Obj String)
xs = fromList [ (1, mkObj . mkString $ "abc")
              , (2, mkObj . mkString $ "def")
              , (3, mkObj . mkString $ "hij")
              ]

-- 2) container using existential quantification

data Obj2 = forall a. (Show a) => Obj2 a

-- using the smart constructor here has no effect on strictness
mkObj2 :: Show a => a -> Obj2
mkObj2 a = Obj2 $! a

xs2 :: Map Int Obj2
xs2 = fromList [ (1, mkObj2 1)
               , (2, mkObj2 . mkString $ "test")
               , (3, mkObj2 'c')
               ]

-- 3) container using existential quantification and deepseq

data Obj3 = forall a. (NFData a, Show a) => Obj3 !a

instance NFData Obj3 where
  -- use default implementation

mkObj3 :: (NFData a, Show a) => a -> Obj3
mkObj3 a = Obj3 $!! a

xs3 :: Map Int Obj3
xs3 = fromList [ (1, mkObj3 (1::Int))
               , (2, mkObj3 . mkString $ "abc")
               , (3, mkObj3 ('c'::Char))
               ]

-- strictness tests
main :: IO ()
main = do
  putStr "test: simple container: "
  (isNF $! xs) >>= putStrLn . show
  assertNF $! xs
  putStr "test: heterogeneous container: "
  (isNF $! xs2) >>= putStrLn . show
  assertNF $! xs2
  putStr "test: heterogeneous container with NFData: " 
  (isNF $!! xs3) >>= putStrLn . show
  assertNF $!! xs3 
  return ()

GHCI输出

test: simple container: True
test: heterogeneous container: False
Parameter not in normal form: 1 thunks found:
let x1 = Tip()
in Bin (I# 2) (Obj2 (_sel (_bh (...,...))) (C# 't' : C# 'e' : ... : ...)) (Bin (I# 1) (Obj2 (D:Show _fun _fun _fun) (S# 1)) x1 x1 1) (Bin (I# 3) (Obj2 (D:Show _fun _fun _fun) (C# 'c')) x1 x1 1) 3
test: heterogeneous container with NFData: False
Parameter not in normal form: 1 thunks found:
let x1 = _ind ...
    x2 = Tip()
in _bh (Bin (I# 2) (Obj3 (_bh (_fun x1)) (_sel (_bh (...,...))) (C# 'a' : C# 'b' : ... : ...)) (Bin (I# 1) (Obj3 (_ind _fun) (D:Show _fun _fun _fun) (I# 1)) x2 x2 1) (Bin (I# 3) (Obj3 x1 (D:Show _fun _fun _fun) (C# 'c')) x2 x2 1) 3)

Answer 1

信不信由你,但你的三次测试都是严格的!从某种意义上讲,您存储的"异质对象"在放入容器对象之前会被评估.

什么不严格只是存在主义的实现.问题是,Haskell并没有真正存在,它们是由存储类型类dictonaries的记录类型模拟的.在你只是一个Show约束的情况下,这基本上意味着你不是存储对象而只是它的结果show,它是一个字符串.但GHC无法知道您希望严格评估该字符串; 事实上,这通常是一个坏主意,因为show通常比深度评估对象要昂贵得多.因此,show当你调用它时,它会被评估,这是非常好的IMO.

如果您确实想要show严格评估,唯一可以确保的方法是使记录转换显式化.在你的例子中,这是微不足道的:

newtype Obj2 = Obj2 { showObj2 :: String }
mkObj2 :: Show a => a -> Obj2
mkObj2 = (Obj2 $!) . show

Answer 2

请注意数据类型如

data Obj2 = forall a. (Show a) => Obj2 a
data Obj3 = forall a. (NFData a, Show a) => Obj3 !a

实际上存储类字典以及数据,例如,Obj2 实际上有两个字段.您的智能构造函数强制数据字段是严格的,但您无法直接控制字典.我怀疑强制或不强制字典会在实践中产生很大的不同,但你可能会欺骗编译器这样做.例如,以下变体似乎对我有用Obj2:

mkObj2 :: Show a => a -> Obj2
mkObj2 a = showsPrec 0 a `seq` (Obj2 $! a)

您还可以看到以下两个"工作":

data Obj2a = forall a. Obj2a a

mkObj2a a = Obj2a $! a

xs2a :: Map Int Obj2a
xs2a = fromList [ (1, mkObj2a 1)
                , (2, mkObj2a . mkString $ "test")
                , (3, mkObj2a 'c')
                ]

data Obj2b = forall a. Obj2b (a -> String) a

mkObj2b :: Show a => a -> Obj2b
mkObj2b a = (Obj2b $! show) $! a

xs2b :: Map Int Obj2b
xs2b = fromList [ (1, mkObj2b 1)
                , (2, mkObj2b . mkString $ "test")
                , (3, mkObj2b 'c')
                ]