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

[apfelmus at quantentunnel.de]

Ryan Ingram wrote:
> On 10/24/07, apfelmus <apfelmus at quantentunnel.de> 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