<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. </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. </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 and Backus-Naur form and 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="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 explains 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="md8"> When I first started using Prolog, I found myself over-using findall along with setof (bagof not so much). The performance of the next example shows why these should be used with caution. </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="md9"> As someone who likes to break list processing problems down to map-reduce, using maplist (classified as _second-order_ rather than logic programming), strikes me as the shortes and most elegant solution here. It is bidirectional, and nearly as quick as the top-down first example with just two lines of code. </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="md10"> The above examples assume we don't want to filter the output, something we comonly 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>