<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. </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"> 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 better 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, SpanishList1), SpanishList-[] = SpanishList1. translate_dl_([], SpanishList, SpanishList). translate_dl_([English|EnglishList], Acc, SpanishList) :- english_spanish(English, Spanish), enqueue(Spanish, Acc, Acc1), translate_dl_(EnglishList, Acc1, SpanishList). 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) 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"> 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 whey 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"> 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"> 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. 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 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"> 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="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"> When I first started using Prolog, I found myself over-using findall/3, along with setof/3 when I wanted duplicates removed and the result sorted alphabetically. </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="md13"> 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 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. </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="md14"> For the sake of completeness, here is an example using setof/3 to filter and sort the result, removing duplicates but putting remaining entries 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>