3 ms·
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
by danidiaz 6y ago
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)
- cousin_it 6y agoIt 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)
- danidiaz 6y agoIt'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.
- rrobukef 6y agoSince 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.
- danidiaz 6y agoWith [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.
- deleted 6y ago[deleted]
- rrobukef 6y agoBecause 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).