Consider this code to create a new list from an existing list:
distribute(S,Head,L) :- distribute(S,Head,[],L).
distribute([],_,L,L).
distribute([H|T],Head,L0,L) :-
Term =.. [Head, H],
distribute(T,Head,[Term | L0],L).
It works great for my purpose now because order is not important, but of course the generated list is in reverse order of the source list. I know this has been discussed many times. Is there a way to keep the original order while still keeping tail recursion?
Thanks,
John
distribute/4 uses the “accumulator” style of tail-recursion, which is common when programming in functional languages. Prolog can use tail recursion in more situations, with logical variables:
distribute2([], _Head, []).
distribute2([H|T], Head, [Term|L]) :-
Term =.. [Head, H],
distribute2(T, Head, L).
If you look at Term in the 2nd clause – its final value is unknown when the “output” parameter [Term|L] is created in the head of the clause; the value gets filled in by Term=..[Head,H]. (The “accumulator” style of recursion is still useful in Prolog; but it’s not needed as often as in functional languages.)
This is such a common pattern that there’s a predicate for it: maplist:
distribute3(S, Head, L) :- maplist(wrap(Head), S, L).
wrap(Head, H, Term) :- Term =.. [Head, H].
And here is a simple test:
?- distribute([a,b,c], f, Z).
Z = [f(c), f(b), f(a)].
?- distribute2([a,b,c], f, Z).
Z = [f(a), f(b), f(c)].
?- distribute3([a,b,c], f, Z).
Z = [f(a), f(b), f(c)].
If efficiency isn’t a concern, you can use append/3:
distribute4(S, Head, L) :- distribute4(S, Head, [], L).
distribute4([], _Head, L, L).
distribute4([H|T], Head, L0, L) :-
Term =.. [Head, H],
append(L0, [Term], L1),
distribute4(T, Head, L1, L).
BTW, I would have written your initial clause as:
distribute(S, Head, L) :-
distribute(S, Head, [], L0),
reverse(L0, L).
Thanks Peter.
I thought about something similar to your distribute2, but I didn’t think it was tail recursive since L isn’t bound until the first clause succeeds. Is my understanding correct? Is it tail recursive after all? My understanding of tail recursion is less than complete.
I like the idea of maplist/3. I’ll research that more.
Yes, it’s tail recursive in the sense that the stack doesn’t grow.
Using logical variables isn’t entirely cost-free … there can be an extra level of indirection, requiring dereferencing. For example: X=Y, Y=Z, Z=3 will end up with something like “X points-to Y”, “Y points-to Z”, “Z is 3”; so to get the value of X, the implementation must follow the chain. (This is an over-simplification; the actual implementation has some cleverness in it, for example to ensure that there are no dereference loops and that cells can be popped off the local stack as soon as possible.)
distribute4/4 is also tail-recursive (it won’t run out of stack space), but it’s less efficient because of the append/3, which turns an O(N) algorithm into O(N2). (append/3 in this situation is also tail-recursive.)
As @j4n_bur53 points out, difference lists can also make things tail-recursive. The last two arguments in the original distribute/4 are similar to a difference list. I won’t get into difference lists here because they’re covered in many texts (and also available online by searching for difference list prolog … there are many explanations, so if one doesn’t satisfy you, read another).
It should be noted that difference lists attain their efficiency by not checking for cycles in the resulting list; this is normally fine, but on occasion can result in head-scratching bugs. They’re also a bit tricky to write, which is why DCGs are a nice notation for hiding the details.
I use DCG for both processing lists and generating lists. I’m quite familiar. But I think in this case it just doesn’t simplify the problem enough to use it. A matter of personal preference, I guess. I like your first suggestion and have used that.
I tried to convert one of my list processing predicates to DCG. I have one that multiplies all of the numbers in a list together. I thought this way: the way to multiply all the members of list is to multiply the first two, put the result back on the list and keep doing that until there is only one number left. I tried this:
mult(I),[Prod] → [P0],[N],!,{ Prod is P0 * N },mult(I).
mult(I) → [I].
I tried:
phrase(mult(I),[2,3,4,5],R) and phrase(mult(I),[2,3,4,5],).
It always fails. I took the mult(I) off the first line and just did:
phrase((mult(A),mult(B),mult(C0),mult(D)),[2,3,4,5],R).
This works fine! So I’m confused why it fails when it calls itself.
Any ideas? I had to change some variable names to keep this site from changing them to silly characters. Hopefully, I changed them all. Ps and Cs inside () cause a problem. If anyone could tell me how to keep this from happening that would be appreciated too.
Thanks,
John
I know now why it doesn’t work. Again DCG that does work isn’t going to be any better than what I have now. Oh well.