  Memoisation, or tabling, is a well-known technique that yields large
improvements in the performance of some recursive computations. Tabled
resolution in Prologs such as XSB and B-Prolog can transform so called
left-recursive predicates from non-terminating computations into finite and
well-behaved ones. In the functional programming literature, memoisation has
usually been implemented in a way that does not handle left-recursion,
requiring supplementary mechanisms to prevent non-termination. A notable
exception is Johnson's (1995) continuation passing approach in Scheme. This,
however, relies on mutation of a memo table data structure and coding in
explicit continuation passing style. We show how Johnson's approach can be
implemented purely functionally in a modern, strongly typed functional language
(OCaml), presented via a monadic interface that hides the implementation
details, yet providing a way to return a compact represention of the memo
tables at the end of the computation.
