Comment by danidiaz | Hacker News Reader

Comment by danidiaz | Hacker News Reader

Parent Full thread

One neat and practical application of existential types if for defining "collectors" for streaming sources. The internal state of the collector is hidden and it can be different form what the collector ultimately returns. For example, a collector that returns the average of its inputs can store sum and count separately as its internal state. This also makes it easier to combine collectors.

In Haskell, using GADTSyntax, it would be something like

    data Collector a b where
        MakeCollector :: (x -> a -> x) -> x -> (x -> b) -> Collector a b

That is: to construct a collector that ingests as and returns a single b, you need to supply a step function, the initial state of type x, and a "tally" function that calculates the result b from the final state. The type of the state ("x") is not present in the type "Collector a b"; it is an "existential".

In the Java Collectors framework, this is (roughly) analogous to

    Collector.of (Supplier<A> supplier, BiConsumer<A, T> accumulator, BinaryOperator<A> combiner, Function<A, R> finisher, Collector.Characteristics... characteristics)

And the type parameter that corresponds to the existential in Haskell is:

    A - the mutable accumulation type of the reduction operation (often hidden as an implementation detail)

It seems to me that Collector a b is isomorphic to [a] -> b, so not clear why you need existentials or GADTs.

    iso1 :: Collector a b -> ([a] -> b)
    iso1 (MakeCollector f x g) = g . foldl f x

    iso2 :: ([a] -> b) -> Collector a b
    iso2 f = MakeCollector (flip (:)) [] (f . reverse)

It's not isomorphic to [a] -> b, because you are not restricted to feed a Collector with a preexisting list, you can feed it with lines read incrementally from stdin for example.

Another difference is that you can combine a "Collector a b" and a "Collector a c" into a "Collector a (b,c)" that, like its components, only requires a single pass of the data. (This would be the Applicative instance for collectors.) Combining functions [a] -> b and [a] -> c doesn't necessarily "stream".

Also, I didn't use GADTs, only GADT "syntax" in which data constructors are provided as functions with signatures (MakeCollector :: ...)

Personally, I find this syntax much clearer for existential types. It amounts to having a type variable in a parameter which doesn't appear in the return type of the constructor.

Since Haskell is lazy you can feed final list to its construction (like the prime sieve examples). Combination in a single-pass is optimisable by loop-fusion. Though optimisations are famous for 'flaking out' at the worst moment.

With [a] -> b, when production of the input elements requires I/O and you don't want to read the entire list beforehand, you are forced to use lazy I/O, which is notoriously flaky and doesn't handle errors well.

Meanwhile, with a Collector, you can read the inputs with standard IO actions just fine, and feed them as they are produced.

Because of non-functional properties of programming code. Of course the archetype of a Collector can be used as a backing data structure. But maybe, if you want an accumulator you're better of calculating the sum without constructing a list (or relying on fusion).

Reply on news.ycombinator.com