ZuriHac 2015 - Discrimination is Wrong: Improving Productivity

Google Tech Talk
May 30, 2015
("show more" for more information)
Presented by Edward Kmett

ABSTRACT

This talk is a case study in library design in Haskell.

Fritz Henglein has shown through a number of excellent papers how to use "discrimination" to do lots of things in O(n): Sorting many more data types than you'd expect, table joins, etc.

In the process of optimizing this approach and wrapping it up in a form that can be easily consumed, we'll take a lot of detours through the different ways you can think about code when optimizing Haskell.

We'll need some category theory, from a deeper understanding of monoids to Day convolution.
We'll need to consider final and initial encodings.
We'll need to drift down to low level system concerns from building a custom foreign prim to nesting unsafePerformIO within unsafePerformIO.
We'll need properties of laziness from productivity to IVars.
Along the way we'll find and fix a small problem with the initial discrimination paper, which opens the door to streaming results, rather than having to wait until all the input is ready.

[TheDickswab]

This might be the coolest thing I've seen all year. Cheers!

[teevorian]

Thank you for this great talk.

I would really like to fully understand every part of it, and I am currently working my way through it.

Thanks again for all the great work you put into Haskell.

[dfeuer]

Would it be possible to fix the captions so they say Haskell instead of Pascal? It's kind of funny, but more annoying.