@ARTICLE{HanusProttTeegen26TPLP,
author    = "Hanus, M. and Prott, K.-O. and Teegen, F.",
title     = "A Monadic Implementation of Functional Logic Programs",
year      = "2026",
journal   = {Theory and Practice of Logic Programming},
publisher = {Cambridge University Press},
doi       = {10.1017/S1471068426100453},
abstract = {
Functional logic languages are a high-level approach
to programming by combining the most important declarative features.
They abstract from small-step operational details
so that programmers can concentrate on the logical aspects of an
application.
This is supported by appropriate evaluation strategies.
Demand-driven evaluation from functional programming is amalgamated
with non-determinism from logic programming
so that solutions or values are computed whenever they exist.
This frees the programmer from considering the influence
of an operational strategy on the success of a computation,
but it is a challenge to the language implementer.
A non-deterministic demand-driven strategy might duplicate
unevaluated choices of an expression, which could duplicate
the computational effort.
In recent implementations, this problem has been tackled
by adding a kind of memoization of non-deterministic choices
to the expression under evaluation.
Since this has been implemented in imperative target languages,
it was unclear whether this could also be supported in
a functional programming environment like Haskell.
This paper presents a solution to this challenge
by transforming functional logic programs into a monadic representation.
Although this transformation is not new,
we present an implementation of the monadic interface
which supports memoization in non-deterministic branches.
Additionally, we include more advanced features of functional logic languages,
namely functional patterns and encapsulated search, in our approach.
By optimizing our implementation for purely functional computations
with both a static and dynamic approach,
we are able to achieve a promising performance that outperforms
current compilers for Curry.
}
}