<div class="notebook"> <div class="nb-cell markdown" name="md1"> # Various ways to iterate in Prolog _Robert Laing_ This is a list of simple examples, mainly created for my own reference, on the numerous ways of list processing in Prolog. My original title was six ways to iterate in Prolog, but I'd forgotten about SWI Prolog's indexing predicates -- nth0/3 or nth1/3 -- which brought the ways to nine, and then Peter Ludemann provided an example using bagof/3, bringing it to 10, and I've added a setof/3 example to bring it to 11, which should do for now. Please make any suggestions for improvements at a discussion I started at <https://swi-prolog.discourse.group/t/six-ways-to-iterate-in-prolog/477>. All the examples use these as their transition clauses. </div> <div class="nb-cell program" data-background="true" name="p1"> english_spanish("One", "Uno"). english_spanish("Two", "Dos"). english_spanish("Three", "Tres"). english_spanish("Four", "Cuatro"). english_spanish("Five", "Cinco"). english_spanish("Six", "Seis"). english_spanish("Seven", "Siete"). english_spanish("Eight", "Ocho"). english_spanish("Nine", "Nueve"). english_spanish("Ten", "Diez"). </div> <div class="nb-cell markdown" name="md2"> ## Traditional top-down iteration One of the advantages of this is bidirectionality. We can either put in a list of English numbers and get Spanish numbers, or vice versa. </div> <div class="nb-cell program" name="p2"> %% translate_td(?EnglishList, ?SpanishList) is det translate_td([], []). translate_td([English|EnglishList], [Spanish|SpanishList]) :- english_spanish(English, Spanish), translate_td(EnglishList, SpanishList). </div> <div class="nb-cell query" name="q1"> time(translate_td(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell markdown" name="md3"> Or alternatively: </div> <div class="nb-cell query" name="q2"> time(translate_td(E, ["Uno", "Dos", "Tres", "Cuatro", "Cinco", "Seis", "Siete", "Ocho", "Nueve", "Diez"])). </div> <div class="nb-cell markdown" name="md4"> ## Traditional bottom-up, tail recursion using an accumulator It returns a reversed list, and is not bidirectional. A reason to use this method rather is when we want to exclude duplicates from the output list, described later with translate_nd. A stylistic change I've made to the example below is to rewrite the helper predicate with an underscore at the end. I don't need to do this since translate_acc is arity 2 and its helper is arity 3, but it's a nice convention which most SWI Prolog modules seem to follow. </div> <div class="nb-cell program" name="p3"> %% translate_acc(+EnglishList, -SpanishList) is det translate_acc(EnglishList, SpanishList) :- translate_acc_(EnglishList, [], SpanishList). translate_acc_([English|EnglishList], Acc, SpanishList) :- english_spanish(English, Spanish), translate_acc_(EnglishList, [Spanish|Acc], SpanishList). translate_acc_([], SpanishList, SpanishList). </div> <div class="nb-cell query" name="q3"> time(translate_acc(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell markdown" name="md5"> ## Difference List The next example uses a _difference list_, something I've found very tricky to get my head around in Prolog. These use _incomplete data structures_ to make queues as efficient as stacks in Prolog. The [a,b,c|Rest]-[Rest] syntax tends to be confusing, requiring that the [Rest] _hole_ left has to be removed by setting it to [] in the final result. Using Prolog's _definite clause grammar_ explained after this is generally a more elegant way of using difference lists. </div> <div class="nb-cell program" name="p4"> %% translate_dl(+EnglishList, -SpanishList) is det translate_dl(EnglishList, SpanishList) :- translate_dl_(EnglishList, Q-Q, SpanishDiflist), SpanishList-[] = SpanishDiflist. translate_dl_([], SpanishDiflist, SpanishDiflist). translate_dl_([English|EnglishList], Acc, SpanishDiflist) :- english_spanish(English, Spanish), enqueue(Spanish, Acc, Acc1), translate_dl_(EnglishList, Acc1, SpanishDiflist). enqueue(X, Qh-[X|Qt], Qh-Qt). </div> <div class="nb-cell query" name="q5"> time(translate_dl(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell markdown" name="md6"> ## Definite Clause Grammar (DCG) Definite Clause Grammar (DCG) notation makes Prolog an ideal language to implement the context free grammar theories of Noam Chomsky, along with Backus-Naur form and its extensions or augmentations that many data types and programming languages are defined in. It uses difference lists under the hood, hiding all the ugly dashes and holes. </div> <div class="nb-cell program" name="p5"> %% translate_dcg(?EnglishList, ?SpanishList) is det (thanks to cut) spanish([Spanish|SpanishList]) --> [English], { english_spanish(English, Spanish) }, spanish(SpanishList). spanish([]) --> []. translate_dcg(EnglishList, SpanishList) :- phrase(spanish(SpanishList), EnglishList), !. </div> <div class="nb-cell query" name="q4"> time(translate_dcg(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell markdown" name="md15"> Doing it this way also creates a bidirectional predicate, an extremely interesting property of DCGs which opens the way to write programs which are both compilers and decompilers. </div> <div class="nb-cell query" name="q15"> time(translate_dcg(E, ["Uno", "Dos", "Tres", "Cuatro", "Cinco", "Seis", "Siete", "Ocho", "Nueve", "Diez"])). </div> <div class="nb-cell markdown" name="md7"> ## Queue with append/3 (why it's bad) We often need queues for things like breadth first searches in Prolog. Whereas Prolog has the very nifty [Head|Tail] syntax to quickly stack elements, putting elements at the back of a queue requires the digressions into _difference lists_ and DCGs above. Novice programmers may wonder why not simply put things at the back of queues with append(Queue, [Element], NewQueue). Looking at the inferences and Lips of the code below indicates why that's inefficient. </div> <div class="nb-cell program" name="p6"> %% translate_q(+EnglishList, -SpanishList) is det translate_q(EnglishList, SpanishList) :- translate_q_(EnglishList, [], SpanishList). translate_q_([], SpanishList, SpanishList). translate_q_([English|EnglishList], Acc, SpanishList) :- english_spanish(English, Spanish), append(Acc, [Spanish], Acc1), translate_q_(EnglishList, Acc1, SpanishList). </div> <div class="nb-cell query" name="q6"> time(translate_q(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell markdown" name="md9"> ## maplist As someone who likes to break list processing problems down to map-reduce, using maplist/3 (classified as _second-order_ rather than logic programming), strikes me as the shortest and most elegant solution here. It is bidirectional, and nearly as quick as the top-down first example with just two lines of code. Note the english_spanish(English, Spanish) transition clause becomes a *closure* within maplist, with its input and output arguments ommitted where it is called. </div> <div class="nb-cell program" name="p8"> %% translate_maplist(?EnglishList, ?SpanishList) translate_maplist(EnglishList, SpanishList) :- maplist(english_spanish, EnglishList, SpanishList). </div> <div class="nb-cell query" name="q8"> time(translate_maplist(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell query" name="q9"> time(translate_maplist(E, ["Uno", "Dos", "Tres", "Cuatro", "Cinco", "Seis", "Siete", "Ocho", "Nueve", "Diez"])). </div> <div class="nb-cell markdown" name="md12"> ## Indexing SWI Prolog's nth0(?Index, ?List, ?Elem) and nth1(?Index, ?List, ?Elem) predicates offer a way of processing lists that Javascript and other C-family programmers will find familiar, addressing each element by its index, incrementing by one until reaching the end. There are also nth0/4 and nth1/4 predicates which allow you to add or remove elements from a list in any position, which I find very handy, but haven't included any examples of here. I'll use indexing from 1 here since that ties in with the example starting at "One", and also means the final index is the same as the list length. </div> <div class="nb-cell program" name="p11"> %% translate_idx(+EnglishList, -SpanishList) is det (thanks to cut) translate_idx(EnglishList, SpanishList) :- length(EnglishList, Length), translate_idx_(1, Length, EnglishList, SpanishList), !. % Base case, final list element translate_idx_(Length, Length, EnglishList, [Spanish]) :- nth1(Length, EnglishList, English), english_spanish(English, Spanish). translate_idx_(Idx, Length, EnglishList, [Spanish|SpanishList]) :- nth1(Idx, EnglishList, English), english_spanish(English, Spanish), IdxInc is Idx + 1, translate_idx_(IdxInc, Length, EnglishList, SpanishList). </div> <div class="nb-cell query" name="q12"> time(translate_idx(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell markdown" name="md10"> ## Removing duplicates The above examples assume we don't want to filter the output, something we commonly need to do for things like graph traversing to avoid cycles. Tail recursion tends to be the most popular approach to graph traversing in Prolog. </div> <div class="nb-cell program" name="p9"> %% translate_nd(+EnglishList, -SpanishList) is det translate_nd(EnglishList, SpanishList) :- translate_nd_(EnglishList, [], SpanishListR), reverse(SpanishListR, SpanishList). translate_nd_([English|EnglishList], Acc, SpanishList) :- english_spanish(English, Spanish), \+memberchk(Spanish, Acc), !, translate_nd_(EnglishList, [Spanish|Acc], SpanishList). translate_nd_([_English|EnglishList], Acc, SpanishList) :- translate_nd_(EnglishList, Acc, SpanishList). translate_nd_([], SpanishList, SpanishList). </div> <div class="nb-cell query" name="q10"> time(translate_nd(["One", "Two", "Two", "Three", "Three", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Two"], S)). </div> <div class="nb-cell markdown" name="md19"> ## Sorting Some readers may have noted the second example, translate_acc, cheated in that the returned list was not reversed. Assuming the input list is provided with a compound term providing numbers and words, rather than use reverse/2 we could use sort/4, which uses the notation @< to remove duplicates and @=< to keep duplicates. Besides removing duplicates, the input list could be shuffled into any order and the output would still be in numerical order. </div> <div class="nb-cell program" name="p15"> %% translate_acc_sort(+EnglishList, -SpanishList) is det translate_acc_sort(EnglishList, SpanishList) :- translate_acc_(EnglishList, [], SpanishListR), sort(1, @<, SpanishListR, SpanishList). translate_acc_([e(Idx, English)|EnglishList], Acc, SpanishList) :- english_spanish(English, Spanish), translate_acc_(EnglishList, [s(Idx, Spanish)|Acc], SpanishList). translate_acc_([], SpanishList, SpanishList). </div> <div class="nb-cell query" name="q19"> time(translate_acc_sort([e(1, "One"), e(2, "Two"), e(2, "Two"), e(3, "Three"), e(3, "Three"), e(3, "Three"), e(4, "Four"), e(5, "Five"), e(6, "Six"), e(7, "Seven"), e(8, "Eight"), e(9, "Nine"), e(10, "Ten"), e(2, "Two")], S)). </div> <div class="nb-cell markdown" name="md11"> A reason top-down recursion is not as popular is that backtracking causes the last rather than first occurrence of an element to remain in the output list, which in the example below results in Dos at the end rather than second position of the result. </div> <div class="nb-cell program" name="p10"> %% translate_nd2(?EnglishList, ?SpanishList) is det translate_nd2([], []). translate_nd2([English|EnglishList], [Spanish|SpanishList]) :- english_spanish(English, Spanish), translate_nd2(EnglishList, SpanishList), \+memberchk(Spanish, SpanishList), !. translate_nd2([_English|EnglishList], SpanishList) :- translate_nd2(EnglishList, SpanishList). </div> <div class="nb-cell query" name="q11"> time(translate_nd2(["One", "Two", "Two", "Three", "Three", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Two"], S)). </div> <div class="nb-cell markdown" name="md8"> ## findall When I first started using Prolog, I found myself over-using findall/3 as below. Although you can use member/2 as a way to iterate over a list, it's not very efficient and Prolog's three "all solutions" predicates findall/3, bagof/3 and setof/3 are not really the right tools for the job here. You would typically want to use them to produce a list from facts in the _clause store_. </div> <div class="nb-cell program" name="p7"> %% translate_findall(+EnglishList, -SpanishList) translate_findall(EnglishList, SpanishList) :- findall(Spanish, (member(English, EnglishList), english_spanish(English, Spanish)), SpanishList). </div> <div class="nb-cell query" name="q7"> time(translate_findall(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell markdown" name="md17"> In this example, what's in the _clause store_ are the ten english_spanish(English, Spanish) transition clauses ordered correctly. So if I wanted to query this database for just Spanish words, findall would be a good tool used like this: </div> <div class="nb-cell query" name="q17"> time(findall(Spanish, english_spanish(_, Spanish), SpanishList)). </div> <div class="nb-cell markdown" name="md20"> Something I've omitted in the above examples is how the predicates handle inputs they can't answer. I've only given translations for one to ten, so what happens if I ask for eleven (once in Spanish)? ```prolog ?- time(translate_td(["Six", "Seven", "Eight", "Nine", "Ten", "Eleven"], S)). % 22 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 1173521 Lips) false. ``` Whereas the previous examples will return false, translate_findall skips garbage intput (which may or may not be what I want). </div> <div class="nb-cell query" name="q20"> time(translate_findall(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven"], S)). </div> <div class="nb-cell markdown" name="md13"> ## bagof Thanks to Peter Ludemann for providing the example below, pointing out bagof/3 is not quite the same as findall/3. One important difference is findall returns an empty list whereas bagof returns false/0 if there are no results for the input, making bagof usually the better choice for logical programming. Assuming we want an empty list if the input is an empty list, the first clause below sees to that. Another thing to note about bagof/3 and setof/3 is the caret sign ^, known as the _existential quantifier_ in Prolog. </div> <div class="nb-cell program" name="p12"> translate_bag([], []) :- !. translate_bag(EnglishList, SpanishList) :- bagof(Spanish, English^(member(English, EnglishList), english_spanish(English, Spanish)), SpanishList). </div> <div class="nb-cell query" name="q13"> time(translate_bag(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"], S)). </div> <div class="nb-cell markdown" name="md18"> Here is how I could use bagof to query the _clausal store_. If I omit the caret, for some reason "Ocho" is the lucky sole selected output. English is the _existential variable_ here since I'm not asking for it to be used in the output. But bagof and its caret notation do not allow underscores, ie anonymous variables, in the :Goal second argument. </div> <div class="nb-cell query" name="q18"> time(bagof(Spanish, English^english_spanish(English, Spanish), SpanishList)). </div> <div class="nb-cell markdown" name="md14"> The caret sign is supposed to be akin to formal logic's ∃ exists sign, and the above would read something like ``` SpanishList = {english_spanish|(∃English)Spanish} ``` where SpanishList may not be the empty set ∅. translate_bag handles "Eleven" the same way translate_findall does (ie, it skips it instead of returning false). </div> <div class="nb-cell query" name="q21"> time(translate_bag(["One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven"], S)). </div> <div class="nb-cell markdown" name="md21"> ## setof Here are two examples of using setof/3, which sorts the result and removes duplicates. Using as with bagof/3 would result in the output list getting put in alphabetical order, which is not quite what I want. </div> <div class="nb-cell program" name="p13"> %% translate_setof(+EnglishList, -SpanishList) translate_setof(EnglishList, SpanishList) :- setof(Spanish, English^(member(English, EnglishList), english_spanish(English, Spanish)), SpanishList). </div> <div class="nb-cell query" name="q14"> time(translate_setof(["One", "Two", "Two", "Three", "Three", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Two"], S)). </div> <div class="nb-cell markdown" name="md16"> To illustrate how _existential quantifiers_ can be helpful, here is an another example with compound terms linking the word to a number to allow setof/3 to understand the order we want. Note that translate_acc_sort above does this far more efficiently. </div> <div class="nb-cell program" name="p14"> translate_setof2(EnglishList, SpanishList) :- setof(s(Idx, Spanish), English^(member(e(Idx, English), EnglishList), english_spanish(English, Spanish)), SpanishList). </div> <div class="nb-cell query" name="q16"> time(translate_setof2([e(1, "One"), e(2, "Two"), e(2, "Two"), e(3, "Three"), e(3, "Three"), e(3, "Three"), e(4, "Four"), e(5, "Five"), e(6, "Six"), e(7, "Seven"), e(8, "Eight"), e(9, "Nine"), e(10, "Ten"), e(2, "Two")], S)). </div> </div>