Discrimination is Wrong: Improving Productivity

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.

 
 

Target Audience

All

schedule Submitted 11 months ago