Gesellschaft fr Informatik e.V.

Lecture Notes in Informatics

INFORMATIK 2009 - Im Focus das Leben P-154, 2875-2888 (2008).

Gesellschaft für Informatik, Bonn


Stefan Fischer, Erik Maehle, Rüdiger Reischuk (eds.)

Copyright © Gesellschaft für Informatik, Bonn


Reinventing Haskell Backtracking

Sebastian Fischer


Almost ten years ago, Ralf Hinze has written a functional pearl on how to derive backtracking functionality for the purely functional programming language Haskell. In these notes, we show how to arrive at the efficient, two-continuation based backtracking monad derived by Hinze starting from an intuitive inefficient implementation that we subsequently refine using well known program transformations. It turns out that the technique can be used to build monads for non-determinism from modular, independent parts which gives rise to various new implementations. Specifically, we show how the presented approach can be applied to obtain new implementations of breadth-first search and iterative deepening depth-first search.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-241-3

Last changed 24.01.2012 22:11:11