Free Structures – including Free Monoids and Free Monads – are a great example of a tool from mathematics that have been shown to be very useful as concepts in Haskell. Free structures of all sorts give you powerful tools in program composition, implementation, and safety guarantees. This talk shows how the implementation of a ubiquitous tool in programming, the Regular Expression, becomes almost trivial to implement when using an often-overlooked free structure, the Free Alternative. Through this accessible example, we explore the specific benefits of choosing to use a free structure for our implementation over other potential methods, and take a look into the philosophy of what makes free structures (of all types) such a powerful tool for programming.
Talk given at C◦mp◦se Conference 2019, in New York City.