MuniHac 2022 - Friday, October 7 - Joachim Breitner: Getting recursive definitions off their bottoms

Haskell claims to be a declarative language, where you just write down some equations, and suddenly the variables contain the solution to these equations. This works even with recursive equations, but only in some cases: defining recursive functions, of course, but also cyclic data structures. One can even apply so-called knot-tying tricks, where a lazy data structure is filled with values that refer to that data structure! For example, one can very elegantly calculate the reachable nodes in a graph.

… until the graph is cyclic, and suddenly our nice elegant Haskell program silently runs in circles and will not produce an answer.

This is unfortunate: The involved equations, although recursive, do nicely declaratively describe the solution we want! So let’s make it happen!

We’ll see types (Booleans, Sets) that seem to behave just like the normal ones, but recursive definition somehow magically produce the expected result. And all that in pure code, no monads anywhere! We’ll see a few use cases that can suddenly be solved much more elegantly.

Then we’ll look under the hood of this (arguably) safe API, won’t be deterred by unsafePerformIO, and find some very imperative, monad-infested, concurrency-worried code that implements a form of “propagator”. We’ll notice that there is plenty we can do to improve their performance, but won’t actually go there. Instead, we’ll turn back to the “pure” interface and discuss together if that is still really “pure”, and what does that mean anyways.

Видео MuniHac 2022 - Friday, October 7 - Joachim Breitner: Getting recursive definitions off their bottoms канала TNG Technology Consulting GmbH