Existential Haskell

https://blog.sumtypeofway.com/posts/existential-haskell.html

by runeks • 6 years ago

66 28 6 years ago

blog.sumtypeofway.com

axelerator• 6 years ago

The irony:

"I write this not because I expect to break any new ground—all the techniques I use here are long-documented in the literature, and Haskell veterans will probably find little new in this post"

Yet I can't get rid of the feeling the article is written in a way only "Haskell veterans" are able to follow it :-)

Cu3PO422• 6 years ago

I can't disagree with your feeling, but I think it's sometimes difficult to put yourself in the shoes of someone who doesn't have experience in a certain area.

While explaining something to first-semester CS students, I said "but it obviously doesn't matter if you accept a pair as a single argument or two arguments". They, of course, asked why it didn't matter and I started off with "You see, functions are exponentials" and I was going to say "and normal algebraic laws apply", but realised after the first part that this way of looking at it surely wasn't going to help them without any background in more advanced theoretical topics.

epsilonclose3• 6 years ago

What do you mean by "functions are exponentials"?

johnisgood2• 6 years ago

Yeah, I do not think it would have been too pragmatic. If the lesson is mathematics, sure, but for CS it is more of a trivia, IMO, or at least I cannot seem to find what changes by knowing that piece of information.

noelwelsh• 6 years ago

Leaving aside the technical content the post uses uncommon words and constructions that obscure its meaning. In other words it is overwritten. Taking the first paragraph as an example, you could make it much easier to read by: replacing "tenet" and "antithetical" with simpler words, removing the "of course", and breaking some of those run-on sentences into smaller sentences.

I'm reminded of patio11's writing. There's a man who never uses one word when three will do. I expect I will now be excommunicated from HN. :-)

arc02• 6 years ago

Not really, it definitely assumes some background with Haskell, but it's far from 'veteran' level. All of the code samples except for the very last section only use elementary concepts.

danidiaz3• 6 years 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• 6 years ago

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)

danidiaz3• 6 years ago

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.

rrobukef2• 6 years ago

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).

BestCatalonia• 6 years ago

such a long piece just to make one point..

augustk• 6 years ago

Are there any Haskell articles about solving actual problems?

arc02• 6 years ago

Yes. Haskell is used by many companies, from small startups to hundred billion dollar corporations.

Fighting spam with Haskell -- https://engineering.fb.com/2015/06/26/security/fighting-spam...

The Joy and Agony of Haskell in Production -- https://www.stephendiehl.com/posts/production.html

Haskell in Production: Riskbook -- https://serokell.io/blog/haskell-in-industry-riskbook

Haskell at Barclays (talk, not an article) -- https://www.infoq.com/presentations/haskell-barclays/

CyberDildonics2• 6 years ago

Whenever this is asked the first response is always the facebook spam filter from five years ago, which is should help you calibrate to the reality. People who have been down the rabbit hole of getting haskell to work seem to consistently say that it is very difficult to debug not only logic but consistent speed and memory usage. It seems like the reality is that if you want something fast, C++ is there with a great ecosystem, if you want to hack something together lots of scripting languages are available and if you want a balance LuaJIT and even go might work.

ImprobableTruth• 6 years ago

Because that's the most notable case of a large company using Haskell. If that's your qualifying criterion, recommending LuaJIT is just as if not even more ridiculous.

Most commercial Haskell is just boring CRUD, like with virtually any other language. There are some interesting projects like Hasura (a decently fast GraphQL engine), but something like Facebook is just a million times more prestigious, so that's what will always be brought up.

that it is very difficult to debug not only logic

Feel free to link any write up making an actual case for this.

Tainnor• 6 years ago

Why does it matter? Not everything needs to have immediate real world applications. Haskell is a good test bed for type theory and some of the things that it experiments with eventually find their way into other languages.

philzook• 6 years ago

A fun post. I liked seeing some things I knew summarized and some things I didn't know. It is fascinating to me that functional programming techniques and object oriented techniques become intersecting once you know enough about the two. The aversion some parts of the functional programming community have to object oriented is more about how it manifests in particular popular languages. People are dutifully intrigued by the CLOS or Smalltalk. Things that are function like should probably be modeled as functions and things that are object like should probably be modeled as objects.

Visitor patterns are a kind of fold, Functions as Closure objects, the various formulations of iterators and stream transformers. The relationship of existential types to objects was (is?) a hot research topic.

- Codata in Action https://www.microsoft.com/en-us/research/publication/codata-...

- Hasekll's Overlooked Object System https://arxiv.org/abs/cs/0509027

- Abadi, Martin; Luca Cardelli - A Theory of Objects.

- Type Theories and Object Oriented Programming http://users.csc.calpoly.edu/~gfisher/classes/530/handouts/r...

Existential Haskell

Related Stories