Matthew Brecknell

Share

matthew.brecknell.net/
@mbrcknl

Matthew had his functional programming epiphany surrounded by the Angle Brackets of Doom (C++ template metaprogramming). He learned some Haskell, and began to appreciate the simple things: composition, meaningful types, and the assurance that what you see is what you get. At some point, he heard about dependent types, and taught himself some Coq. He still occasionally enjoys some C++, for old times sake.

YOW! Lambda Jam 2013 Brisbane

Getting Data Structures Right with GADTs and nested types

TALK –  VIEW SLIDES WATCH VIDEO

Learn about GADTs and nested data types, and how you can use them to encode structural invariants in your Haskell types. You’ll also gain some insight into the inner workings of efficient functional data structures.

In the talk, I’ll show a B-tree, using a GADT to maintain balance. We’ll see that types not only guard against errors, but help us find the right implementation.


Getting Data Structures Right with GADTs and Nested Types

JAM

Learn about GADTs and nested data types, and how you can use them to encode structural invariants in your Haskell types. You’ll also gain some insight into the inner workings of efficient functional data structures.

In the jam, you’ll dive into some code. You may continue work on the B-tree, implementing insertion and deletion. Or you may choose to learn about nested types, using them to implement a random-access list, or a finger-tree. There will be opportunities for questions, discussion and collaboration, and I’ll be giving plenty of hints to get you through the tricky parts.

Jam Prerequisites

To get the most out of the jam, you’ll need to be comfortable with Haskell fundamentals, especially recursive data types and higher-order functions. Some experience with phantom types and continuation-passing style would be useful, but not essential.

Bring a fully charged laptop with the Haskell Platform installed, minimum version 2012.4.0.0 (with GHC 7.4.2), available at haskell.org/platform. Also bring your favourite text editor, and a shell with GHCi on the PATH.

Some additional materials, including data structure crib sheets, will be made available before the conference.