(list (english_spanish (car english))))))Īs you can see, the final call is append, not translate_q, so this isn’t tail recursive. (BTW, don’t use a dict for an accumulator, for inserting 10,000 items, I measured it as 20x slower than a red-black tree.)īut for situations where you don’t need to check for duplicates, the difference-list approach (which requires logical variables to work) is a big win.īy comparison, in LISP, translate_q becomes something like the following: (defun translate_q (english) And if you use extended DCGs, you can make the form of the accumulator transparent. If performance is an issue, you can use something faster than a simple list, for example a red-black tree ( library(rbtrees)). I think you mean that one advantage of passing a complete accumulator (as opposed to a difference list) is that you can use it to filter out duplicates. Without tail recursion optimization, the stack grows with each “iteration”. The big advantage of tail recursion optimiation is that the stack doesn’t grow. My understanding of the advantage of tail recursion is for things like graph traversal where it’s important to filter out duplicates to avoid cycles. % Filter out duplicates from the output list The hitch is the last occurrence of an element is kept instead of the first: %% translate_nd(+EnglishList, -SpanishList) is det I was somehow under the impression this wouldn’t work for traditional, top-down iteration because the values are only filled in later on backtracking, but see I was wrong. Translate_nd(, SpanishList, SpanishList). Translate_nd(EnglishList, Acc, SpanishList). % Skip adding Spanish word because it's already in Acc list Translate_nd(EnglishList,, SpanishList). Translate_nd(EnglishList,, SpanishListR), translate_nd(EnglishList, SpanishList) :.
My second example, translate_acc, uses tail recursion. Maplist(english_spanish, EnglishList, SpanishList). Translate_maplist(EnglishList, SpanishList) :. % maplist falls under second order programming %% translate_maplist(?EnglishList, ?SpanishList) Translate_q(EnglishList, Acc1, SpanishList). % using append instead of a difference list is included to show why it's a bad idea %% translate_q(+EnglishList, -SpanishList) is det Phrase(spanish(SpanishList), EnglishList), !. Translate_dcg(EnglishList, SpanishList) :. % A simple definite clause grammar example %% translate_dcg(+EnglishList, -SpanishList) is det (thanks to cut)
Translate_dl(EnglishList, Acc1, SpanishList). Translate_dl(, SpanishList, SpanishList). Translate_dl(EnglishList, Q-Q, SpanishList1), Translate_dl(EnglishList, SpanishList) :.
%% translate_dl(+EnglishList, -SpanishList) is det Translate_acc(, SpanishList, SpanishList). Translate_acc(EnglishList,, SpanishList). Translate_acc(EnglishList, SpanishList) :.
% Traditional bottom-up method of iteration, reverses output and is not bidirectional %% translate_acc(+EnglishList, -SpanishList) is det % The traditional, top-down method of iteration in Prolog %% translate_td(?EnglishList, ?SpanishList) is det Here’s what I came up with for anyone interested. As a learning exercise and to create simple examples for myself, I worked through different ways to translate an input list into an output list, and to look at their efficiency using the time clause.
0 kommentar(er)
