List Utilities Module Users' Manual

Recursively applies Functor to the elements of List, prepending the result onto DCGIn. In short, map_reversed/4 gives a reversed, tranformed, list.

Standard. N.B.: one cannot use the trick of having DCGIn free and DCGOut bound to the initial state in the hope of obtaining a transformed result in DCGIn in the element ordering of List: this predicate fails for that case. Use map/3 if element ordering should be preserved.

Here we demonstrate accumulating a set of similarly operating rules (specifically, a set of rules that take no parameters) onto a set of rules with parameters already assigned for testing by a unit test framework:

  map_reversed(lambda(RuleID, rule(RuleID, [], 180)),
	       ['1a', '1b', '1c', '9a', '9b', '9c', '9d', '17a',
	        '28a', '28b', '28c', '33a', '37a', '51a'],
	       [rule('24a', Param24ab, 42), rule('24b', Param24ab, 42),
	        rule('24c', Param24c, 42), rule('31a', Param31a, 180),
		rule('34a', Param34a, 180), rule('34b', Param34b, 180),
		rule('34c', Param34c, 180),
		rule('49a', Param49a, 180), rule('51b', Param51b, 180)],
               NoScoreConstructs)

map/3, reverse/2

Recursively applies Functor to the elements of ListIn, resulting in ListOut containing the tranformed elements with the same ordering as ListIn. The research from the functional programming language community has shown that all (list-)transformation functions are derivatives of foldl/4, but this predicate is so commonly used that the justification for its independent definition is self-evident.

If ListOut is free, deterministic; otherwise, semideterministic based on the unification of the map/3 result and the input, bound, ListOut.

In this example, we have a party (HiLo) that we pair with a each party in an input list:

map(lambda(Party, party([HiLo, Party])), Parties, Pairs)

This next example continues from the result of the map_reversed/4 example: we transform the rule/3 terms into a nominal/1 term that instructs the unit test framework that the correct result is no rule finding based on the input data:

map(lambda(rule(ID, Params, Period),
	   nominal(no_rule(ID, reason(zero_score_rule),
                           InnocuousData, Duration, Params,
			   Period, InitEnv))),
    NoScoreConstructs, NoScoreNoRules)

Incidentally, we see from this example that the input variable of a lambda-term can be destructured just as any other Prolog unification.

map_reversed/4, foldl/4

Converts List into two lists, one that has elements that match Match and the other with the elements that do not. filter/4 can be considered a generalization of map/3 in that filter/4 retains the elements that do not prove Match as well as the ones that do.

If Trues and Fails are free, deterministic; otherwise, semideterministic based on the unifications of the filter/4 results and the input, bound, output lists.

In this example, we create Match that is a unification term discriminator, filtering a set of rules into ones with at least one parameter and ones with none:

filter(Rules, rule(_, _, _, parameters([_|_]), _), ParamsRules, NoParamRules)

This next example uses a psi/2-term to filter a list based on a predicate:

X := 1..10, filter(X, psi(Y, Y < 5), Yes, No)

The result of the above call is that Yes = [1,2,3,4] and No = [5,6,7,8,9,10]

map/3

This is the fundamental (program) transformation function, given to us by research into functional programming.² This predicate takes the elements of a list and an initial value and recursively applies BinaryFunctor to the two obtaining a final result (which, only in the special case of the secondary function of the composition being concatenation does a list result, otherwise the result is a non-list term). foldl is also known as reduce;³ although not strictly correct, this name does capture the majority of this predicate's applicability.

foldl/4 captures the mechanics of (terminating, or eager, or applicative) recursion⁴ in predicate form. So, using this predicate in conjuction with an appropriate set of elements in List (such as a list of combinators) and an appropriate BinaryFunctor will allow one to build functions on-the-fly. Given the above, and given that most functional programs can be treated as data (i.e. Lisp programs are lists; and lists are Lisp's data structure), it is possible to feed programs to foldl to obtain new programs; therefore it is associated with being a '"program" transformation' function.

depends on the modality of Ans and BinaryFunctor (e.g. if Ans is free and BinaryFunctor is deterministic, then this instance of foldl is deterministic as well).

Here is a simple definition of sum_list/2:

foldl(List, "+", 0, Ans)

so, X := 1..10, foldl(X, "+", 0, 55) holds.

Here is a program that multiplies ratios, given a fixed denominator:

bayes_preference(List, Denominator, Result) :-
  compose("`c/", Denominator, Ratio),
  compose("`b*", Ratio, Multiplier),
  foldl(List, Multiplier, 1.0, Result).

So, for example, let's say a Bayesian system has collect counts over seven attribute for 595 occurrences of a class, if the counts of a new input matched the following:

Attributes = [412,485,564,363,75,15,420]

then bayes_preference(Attributes, 595.0, Result) would give the value that shows the preference toward that class (Result is approximately 7.3e-4).

The dual of foldl/4 is unfold/5

This predicate serves the need of obtaining a list from a starting value and a termination test. In essence, this is the mathematical, or functional, definition of a series.⁵ This predicate implicitly builds a list instead of requiring the programmer to explicitly enumerate the elements (by defining the list by hand or by creating and calling a recursive predicate).

Nondeterministic; choice-points are left at each inductive call in the construction of Ans.

The set_utils module defines the arithmetic sequence operator thusly:

'..'(Count, X, Y) :- unfold(psi(A, A > Y), i, "`+1", X, Count).

It may be a fruitful line of research, given monadic tranformations⁶ to allow unfold/5 to work with monads for CurrPred and NextPred, as monads facilitate dynamic programming, so that, for example, sequences that depend on the values of earlier elements (moreso than simply the most recent element) may be defined. Both the Fibonacci and prime sequences could be defined with unfold/5 using monads, whereas now, the simplest approach for defining these sequences is to use explicit (recursive) predicates.

'..'/2; The dual of unfold/5 is foldl/4

For example, The appendix with the prelude definition of Haskell in the appendix of [Dav1992], or the Haskell manual itself (in the Standard Prelude section), obtainable from http://haskell.org/onlinereport/standard-prelude.html, or, from the source we use, the Mercury library reference manual, particularly the list module section, available from http://cs.mu.oz.au/research/mercury.

Because foldl is a function, not a predicate the standard signature for it is...

foldl(BinaryFunctor, Seed, List) = Ans

... in the functional programming community. We have a different signature for this module. Deal with it.

The programming language Dylan names this function reduce, not foldl. The Gwydion Dylan Maintainers are the current and active developers of the Dylan programming language, their entry web-page is http://www.gwydiondylan.org.

I placed all the caveats to describe foldl's recursion, because it is trivial to capture the definition of normal-order, or lazy, recursion using combinators. In fact, there exists a recursion-defining combinator which is known in the literature as the 'y' or 'θ' combinator or the 'sage bird'. The "problem" with the combinator approach is that it defines recursion generally, with the result of it defining it infinitely, and allowing the user of the recursion to take the first 'N' iterations for the specific task. As Prolog, by default, evaluates arguments eagerly, a call using that combinator would never return. To be able to use combinatory recursion, a normal-order evaluation system must be developed for Prolog first. This task currently falls outside of the scope of this module.

Of course, series, and their construction, has been the study of mathematical philosophers since ancient times. The serious study of series have entered into the computer science field with the adoption of the series type into Common Lisp (see, e.g., [Wat89], or the Series appendix of [Ste84]), further refined by the list construction syntax in the Haskell programming language (see, particularly, §3.10 and §3.11 of [Jon2002]).

A good collection of essays on monads can be found at http://haskell.cs.yal.edu/bookshelf/#monads. Unfortunately, the link to the excellent, practical, introductory article: "What the hell are Monads?" no longer functions.