Functional programmers have learned to emulate logic programming using the effect of nondeterminism, usually implemented as backtracking. However, backtracking search is often inefficient; logic programmers have explored other useful strategies. Datalog takes an extreme approach, allowing only predicates with finite extent. This allows bottom-up evaluation, which easily handles queries (such as transitive closure) that are inefficient to solve by brute-force search.

Datafun shows that higher-order functional programs can emulate Datalog using a bottom-up nondeterminism effect (a finite set monad) combined with monotone fixed points. Here, we sketch the translation to Datafun of a classic Datalog optimisation, seminaïve evaluation, which avoids needlessly re-deducing facts when evaluating a recursive predicate.

Datalog folklore suggests seminaïve evaluation can be understood in terms of derivatives; we substantiate this by showing that its analogue in Datafun can be defined by applying recent work by Cai et al. on derivatives for incremental computation in a higher-order setting.