How to define a strict existential type?

Question

I want to use Haskell's existential types (http://www.haskell.org/haskellwiki/Existential_type) in a strict context. I took the example from the haskell-wiki and tried to create a strict heterogeneous map with it. It's required that the map and it's values get fully evaluated.

I defined 3 types to test this. The first one is just a simple strict map. The second type is a heterogeneous map using existential types. The third type is like the second, but adds NFData constraints.

While the first simple example is truly strict and gets fully evaluated, the other ones are not. Even the third type, using deepseq, seems not to be fully evaluated.

My questions are:

• How do i define such a heterogeneous type in a strict way?
• If it's not possible - Why not? Is there a way to work around this?

Example source

{-# 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 output

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

Believe it or not, but all three tests of yours are strict! In the sense of, the "heterogeneos objects" you're storing are evaluated before being put in the container objects.

What's not strict is just the implementation of the existential. The thing is, Haskell doesn't really have existentials, they're emulated by record types which store the type class dictonaries. In you case of just a Show constraint, that basically means you're not storing the object but only its result of show, which is a string. But GHC can't know you want that string to be evaluated strictly; in fact it would usually be a bad idea because show may typically be much more expensive than deep-evaluating an object. So the show is left to be evaluated when you call it, which is quite fine IMO.

If you do want to evaluate the show strictly, the only way to be sure is make the record transformation explicit. In your example, that's trivial:

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

Answer 2

Note that datatypes such as

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

actually store the class dictionaries as well as the data, so for example, Obj2 actually has two fields. Your smart constructor forces the data field to be strict, but you have no direct control over the dictionary. I doubt that forcing or not-forcing the dictionary will make much difference in practice, but you may be able to trick the compiler into doing so. For example, the following variant seems to work for me for Obj2:

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

You can also see that the following two will "work":

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')
                ]