We have introduced incremental definitional trees, a data structure which is a refinement of the usual definitional trees and redeems them from unnecessarily sticking to the traditional Huet and Lévy's matching dags [HL79, HL91] or Strandh's index trees [Str89]. We have shown that, in CB systems, such a basic redefinition of definitional trees permits a more compact representation which can be used to substantially improve the evaluation of input expressions.
Inspired in the fact that inductively sequential TRSs are forward branching, we have developed an incremental description of needed narrowing which can be thought of as the functional logic counterpart of Strandh's algorithm for the incremental reduction of terms [Str89]. By this means, we have implicitly demonstrated that (incremental) Curry implementations fit the original (nonincremental) semantics of Curry. We have also proved that our incremental needed narrower preserves the optimality properties and is more efficiently implementable than the original procedure thanks to its intrinsic incremental nature. We have shown that the proposed refinements can significantly improve the execution of functional logic languages based on needed narrowing. In particular, we have shown that they can be advantageously applied to optimize the implementation of the basic Curry machinery.