Z6p8v1y6bhmjakou7wmb
SkillsCast

A Well-Typed Binomial Heap

11th October 2018 in London at CodeNode

There are 38 other SkillsCasts available from Haskell eXchange 2018

Please log in to watch this conference skillscast.

731489398 640

Most people are familiar with the hello world of dependently-typed Haskell: a vector that is annotated with the Peano number represenation of its size. This talk introduces a similar way to deal with binomial heaps.

Binomial heaps are used to implement, among other things, priority queues. They are a fan favourite among data structures because of their simple elegance and the fascinating way their structure corresponds to binary numbers.

Jasper will use this idea to lift binary numbers to the type level, which is great because you get log(n) size and time in places where you would see n for Peano numbers -- in addition to being insanely cool.

This talk will be an introductory explanation of a non-trivial (and again, awesome) example of dependent Haskell programming.

Thanks to our sponsors

A Well-Typed Binomial Heap

Jasper Van der Jeugt

Jasper Van der Jeugt was born in 1990, and spent most of his youth in Lokeren & Ghent, Belgium. He now lives in Zürich, Switzerland. Jasper has been coding and writing about Haskell since his time at Ghent University. He has been using the language professionally for the last three years, and in open source for much longer. He is currently a consultant for Luminal. In his spare time, he skateboards down mountains and takes pictures.

SkillsCast

Please log in to watch this conference skillscast.

731489398 640

Most people are familiar with the hello world of dependently-typed Haskell: a vector that is annotated with the Peano number represenation of its size. This talk introduces a similar way to deal with binomial heaps.

Binomial heaps are used to implement, among other things, priority queues. They are a fan favourite among data structures because of their simple elegance and the fascinating way their structure corresponds to binary numbers.

Jasper will use this idea to lift binary numbers to the type level, which is great because you get log(n) size and time in places where you would see n for Peano numbers -- in addition to being insanely cool.

This talk will be an introductory explanation of a non-trivial (and again, awesome) example of dependent Haskell programming.

Thanks to our sponsors

About the Speaker

A Well-Typed Binomial Heap

Jasper Van der Jeugt

Jasper Van der Jeugt was born in 1990, and spent most of his youth in Lokeren & Ghent, Belgium. He now lives in Zürich, Switzerland. Jasper has been coding and writing about Haskell since his time at Ghent University. He has been using the language professionally for the last three years, and in open source for much longer. He is currently a consultant for Luminal. In his spare time, he skateboards down mountains and takes pictures.

Photos