:- module(list_utils, [ map_reversed/4, map/3, filter/4, foldl/4, unfold/5, combine/5, flatten/3, digits/5, count_sum/3, takeout/3, permute/2, take/3, drop/3, pop/3, prepend/3, equivalent_lists/2, extract_optional_info_arg/5, extract_optional_info/4 ]). % synopsis: standard functional programming list utilities % date: April 7, 2004 % author: Douglas M. Auclair (DMA) % modified: February 21, 2006, DMA % changed: Generalised extract_optional_info/4 so that it now % considers alternates for an ARGV switch. % modified: March 23, 2005, DMA % changed: By using difference lists, lists for some predicates % (the new map/3 and unfold/5) are returned in the expected % (as opposed to reversed) order. % modified: March 18, 2005, DMA % changed: Added convertability of terms to allow any phi-representable % substitute for the functional arguments % modified: February 17, 2005, DMA % changed: Permutated lists sometimes need to be flattened % ... flattened like Afghan bread, or like a bug on a % windshield, so I've added flatten/3 as one of the things % to do to a list. % modified: February 15, 2005, DMA % changed: Added list permutation as one of things to do to a list. % modified: January 26, 2005, DMA % changed: Incorporate the combine/5 predicate here; it's a predicate % that exhaustively pairs the elements of two lists using a % binary function (composite lambda term). % modified: January 25, 2005, DMA % changed: Exported pop/3 for DCG head argument extraction; added % predicates to extract optional values (and their possible % arguments from argument lists). % modified: January 5, 2005, HAPPY NEW YEAR, DMA % changed: Added equivalent_lists/2, as I'm doing that in various % places, and it's of general utility. Specified the % predicates used from the imported modules. % modified: July 8, 2004, DMA % changed: Imported the lambda module and created several % higher-order predicates that work on, or produce, lists. % modified: June 21, 2004, DMA % changed: Added prepend/3 to assist DCG builder predicates. :- use_module(library(lambda), [apply/3, test/2]). :- use_module(library(peano), [peano/2]). :- use_module(library(combinators), [phi_equivalent/2, compose/3]). :- use_module(library(syntax), [try/3]). :- ensure_loaded(library(lists)). :- op(200, fx, try). filter(Input, Test, True, False) :- % Converts a list into two lists, one that has elements that match % Test and the other with the elements that do not. (phi_equivalent(Test, Phi); Phi = phi(In, _, Test = In)), filter_aux(Input, Phi, [], True, [], False). map_reversed(Functor, List) --> % Applies Functor to each element of List to obtain the resulting % transformed list. { phi_equivalent(Functor, Phi) }, map_reversed_aux(Phi, List). map(Function, ListIn, ListOut) :- % Maps function over ListIn, giving ListOut with the same ordering % of ListIn. phi_equivalent(Function, Phi), map_aux(ListIn, Phi, L - L, ListOut - []). % foldl/4 folds a list using Seed and a binary curried lambda-term to % obtain the result. For example, summation can be expressed as % follows: % foldl(ListOfNumbers, Plus, 0, Sum) % where Plus = lambda(X, lambda(Y, X + Y)) foldl(List, BinaryFunctor) --> { phi_equivalent(BinaryFunctor, PartialPhi) }, !, foldl_aux(List, PartialPhi). % unfold/5 converts an atom into a list representation by repeatedly % applying F to the seed to form the head and (recursive) G to the % seed to form tail until Stop is true (exclusive). % % For example, to get the list of (lazy) numbers from 1 to N: % unfold(GTN, Id, Plus1, 1, List) % where GTN = predicate(X, X > N) % Id = lambda(X, X) % Plus1 = lambda(X, X + 1) % % ... but why do that when you could simply do X := 1..N instead? % % ... also, using combinators, the above reduces to: % unfold("```bw`c>10?", i, "`+1", 1, List). unfold(Stop, F, G, Seed, Ans) :- phi_equivalent(Stop, StopTest), phi_equivalent(F, Fn), phi_equivalent(G, Gn), unfold_aux(StopTest, Fn, Gn, Seed, L - L, Ans - []). % combine/5 takes two lists and exhaustively pairs them through % repeated application of the binary function (lambda term). So, for % example, given [a,b] and [1,2,3] the resulting list (unordered) % Pairs = [pair(a,1),pair(a,2),pair(a,3),pair(b,1),pair(b,2),pair(b,3)] % is obtained from the following goal: % combine([a,b], [1,2,3], lambda(X, lambda(Y, pair(X, Y))), [], Pairs) combine(ListA, ListB, BinaryFunction, Accum, Ans) :- phi_equivalent(BinaryFunction, PartialPhi), combine_aux(ListA, ListB, PartialPhi, Accum, Ans). % digits/5 converts a stringified number into its integral % representation (The peano numerals represent the string's length -- % using the Peano series gives this predicate a deterministic % modality). digits(zero, Number, Number) --> []. digits(s(Peano), Accum, Number) --> [Char], { Digit is Char - 48, % chr(48) = ord("0") Temp is Accum * 10 + Digit }, digits(Peano, Temp, Number). % count_sum/3 gives two values of a list of numbers: % its length and its sum (this saves us from iterating over a list % twice). count_sum(Numbers, Count, Sum) :- do_count_sum(Numbers, sum(0, 0), sum(Count, Sum)). do_count_sum([]) --> []. do_count_sum([Number|Nums], sum(C0, S0), sum(Count, Sum)) :- C1 is C0 + 1, S1 is Number + S0, do_count_sum(Nums, sum(C1, S1), sum(Count, Sum)). % takeout/3 removes X from List takeout(H, [H|T], T). takeout(X, [H|T], [H|R]) :- takeout(X, T, R). % permute/2 returns List in a randomized order permute([], []). permute([X|Y], Z) :- permute(Y, W), takeout(X, Z, W). flatten(Object) --> % Given any proper list, return a list than contains only the % elements (that are not list terms) of the first list, no matter % how deep within the nested list structure they are. { is_list(Object), [H|T] = Object } -> flatten_list([H|T]) ; prepend(Object). % flatten_list/3 is a helper predicate: we know we're working on an % element that is a list, so flatten it. flatten_list([]) --> []. flatten_list([H|T]) --> flatten(H), flatten_list(T). % take/[3,4] returns the first N elements of a list take(N, In, Out) :- peano(N, Peano), take(Peano, In, Out, []). take(s(Peano), [H|T]) --> [H], take(Peano, T). take(zero, _) --> []. % drop removes the first N elements ... its implementation is much % simpler as there's no need for accumulating the first N elements (as % in take/[3,4]). drop(N) --> { peano(N, Peano) }, drop_aux(Peano). drop_aux(zero) --> []. drop_aux(s(Peano)) --> pop(_), drop_aux(Peano). pop(H, [H|T], T). % Treating a list like a stack is just so Lispy! prepend(H, T, [H|T]). % Assists DCG functions by giving prepend functional to DCGs % manipulating implicit arguments. % equivalent_lists/2 ensures every member of list A is unifyable in % list B and vice versa (that's French). equivalent_lists([], []). equivalent_lists([H|T], List) :- takeout(H, List, SubList), equivalent_lists(T, SubList). extract_optional_info_arg([Option|Names], DefaultValue, Assignee, [Arg|List], ListSansOptionAndArg) :- extract_optional_info_arg_aux([Option|Names], DefaultValue, Assignee, [Arg|List], [], ListSansOptionAndArg). extract_optional_info_arg_aux(_Opts, Default, Default, []) --> reverse. extract_optional_info_arg_aux(Options, Default, Assignee, [Arg|List]) --> { takeout(Arg, Options, _) } -> { pop(Assignee, List, SubList) }, prepend_list(SubList), reverse ; prepend(Arg), extract_optional_info_arg_aux(Options, Default, Assignee, List). prepend_list([]) --> []. prepend_list([H|T]) --> prepend(H), prepend_list(T). % extract_optional_info/4 is a deterministic query is the Option % described by the various representations in Options exist in the % input (implied) argument list. If so, remove Option from the DCG; % sinon, return _|_ (as represented by the null-set or empty-list) and % leave the DCG undisturbed. extract_optional_info(Options, [Option]) --> { takeout(Option, Options, _) }, takeout(Option), !. extract_optional_info(_, []) --> []. % ---------------------------------------------------------------------- % INTERNAL IMPLEMENTATION PREDICATES % filter_aux/6 is the worker predicate for filter/4. filter_aux([], _, True, True, False, False). filter_aux([Element|Rest], Phi, T0, True, F0, False) :- compose(Phi, Element, Result) -> filter_aux(Rest, Phi, [Result|T0], True, F0, False) ; filter_aux(Rest, Phi, T0, True, [Element|F0], False). % map_reversed_aux/4 tries the combinator on each element of the list, % prepending each of the transformed elements to the result. map_reversed_aux(_Phi, []) --> []. map_reversed_aux(Phi, [H|T]) --> try ({ combinators:compose(Phi, H, Result) }, list_utils:prepend(Result)), map_reversed(Phi, T). % foldl_aux/4 applies the current element to the partially % phi-equivalent functional and then converts the result into a % phi-term to update the state with the binary transformation. foldl_aux([], _phi) --> []. foldl_aux([H|T], PartialPhi, Seed, Ans) :- compose(PartialPhi, H, Functional), phi_equivalent(Functional, Phi), compose(Phi, Seed, NewSeed), foldl_aux(T, PartialPhi, NewSeed, Ans). % unfold_aux/6 unfold_aux(Stop, F, G, Seed, Accum, Ans) :- compose(Stop, Seed, _) -> Ans = Accum ; compose(F, Seed, H), compose(G, Seed, NewSeed), concat(Accum, [H|Z] - Z, NewAccum), unfold_aux(Stop, F, G, NewSeed, NewAccum, Ans). map_aux([], _) --> []. map_aux([H|T], Function) --> try ({ combinators:compose(Function, H, Result) }, list_utils:dcg_concat_element(Result)), map_aux(T, Function). combine_aux([], _, _) --> []. combine_aux([H|T], List, PartialPhi) --> { compose(PartialPhi, H, Fn), phi_equivalent(Fn, Phi) }, combine1(List, Phi), combine_aux(T, List, PartialPhi). combine1([], _) --> []. combine1([H|T], UnaryFunctor) --> { compose(UnaryFunctor, H, Result) }, prepend(Result), combine1(T, UnaryFunctor). dcg_concat_element(Elt, Accum, Ans) :- concat(Accum, [Elt|Z2] - Z2, Ans). concat(A1 - Z1, Z1 - Z2, A1 - Z2). % And what makes ordering all possible: difference lists!