Hasochism: The pleasure and pain of dependently typed haskell programming

Haskell’s type system has outgrown its Hindley-Milner roots to the extent that it now stretches to the basics of dependently typed pro-gramming. In this paper, we collate and classify techniques for pro-gramming with dependent types in Haskell, and contribute some new ones. In particular, through extended examples—merge-sort and rectangular tilings—we show how to exploit Haskell’s con-straint solver as a theorem prover, delivering code which, as Agda programmers, we envy. We explore the compromises involved in simulating variations on the theme of the dependent function space in an attempt to help programmers put dependent types to work, and to inform the evolving language design both of Haskell and of dependently typed languages more broadly