Scoring and choice: Evaluation algebra

Definition (Evaluation algebra):

Let Σ be a signature with a sort symbol Ans. An Σ-evaluation algebra is an Σ-algebra argumented with an objective function h: [Ans] -> [Ans], where [Ans] denotes lists over Ans.

In most DP applications, the purpose of the objective function is minimizing or maximizing over all answers. We take a slightly more general view here. The objective may be to calculate a sample of answers, or all answers within a certain threshold of optimality. It could even be a complete enumeration of answers. We may compute the size of the search space or evaluate it in some statistical fashion, say by averaging over all answers. This is why in general, the objective function will return a list of answers. If maximization was the objective, this list would hold the maximum answer as its only element.