Re: [Haskell-cafe] Existential types (Was: Type vs TypeClass duality)

Ryan Ingram wrote:

On 10/24/07, apfelmus wrote:

...

So, instead of storing a list [∃a. Show a => a], you may as well store a list of strings [String].

I've seen this before, and to some extent I agree with it, but it breaks down for bigger examples due to sharing.

In most cases, "x" has a more compact representation than the result of evaluating "show x". So if you keep a list of [show x, show y, show z] around for a long period of time, you're leaking space. Consider instead:

data StringFn where StringFn :: forall a. a -> (a -> String) -> StringFn

applyStringFn :: StringFn -> String applyStringFn (StringFn a f) = f a

[ StringFn x show, StringFn y show, StringFn z show ]

Now, you use more time every time you compute the result, but StringFn has a compact representation; you're not leaking the space used for the string throughout the execution of the program, but only allocating it while it's used.

Indeed. (Although the effect will be marginal in this particular example since the unevaluated thunk (show x) is represented as compactly as x . But the time-space trade-off would matter when strings from the list are used several times.) In a sense, that's also the reason why stream fusion à la Duncan + Roman + Don uses an existential type data Stream a where Stream :: ∀s. s -> (s -> Step a s) -> Stream a data Step a s = Done | Yield a s | Skip s I mean, every stream can be represented by the list of its results but the observation for fusion is that there is a much more compact representation for the state (like an integer for [1..] or the source list in map f . map g $ [x,y,...]) Regards, apfelmus