14

How do I do an operation for each element of a list, in order?

Based on these two resources:

  1. http://www.swi-prolog.org/pldoc/doc/swi/library/lists.pl
  2. http://www.swi-prolog.org/pldoc/doc_for?object=foreach/2

I imagine I can always rely on:

  • foreach(member(X, [1,2]), write(X)).

Is that deterministic and can I wrap the member/2 predicate as I please in my own predicates and still always iterate in order?

false
  • 10,264
  • 13
  • 101
  • 209
codeshot
  • 1,183
  • 1
  • 9
  • 20

1 Answers1

20

Yes, but you have to worry about your predicate failing. If it can, the remaining elements in the list will not be processed because it produces a conjunction rather than a failure-driven loop.

I would be more keen to use maplist/2 since I think it is more widely used than foreach/2 but I also hadn't seen this option before. :)

Edit: Let's discuss what I mean about failure-driven loops.

There are two primitive iteration methods in Prolog: recursion and failure-driven loops. Say I want to print out every item in a list. The recursive method is going to look like this:

print_all([]).
print_all([X|Rest]) :- write(X), nl, print_all(Rest).

So given a list like [1,2,3], this is going to expand like so:

print_all([1,2,3])
  write(1), nl, print_all([2,3])
    write(1), nl, write(2), nl, print_all([3])
      write(1), nl, write(2), nl, write(3), nl, print_all([])
        write(1), nl, write(2), nl, write(3), nl.

This is how member/2 is usually implemented:

member(X, [X|_]).
member(X, [_|Xs]) :- member(X, Xs).

So you can see the recursive method is pretty simple and general.

Another simple but somewhat frowned-upon method is to simulate a failure to engage the backtracking mechanism. This is called a failure-driven loop and looks like this:

print_all(List) :- member(X, List), write(X), nl, fail.
print_all(_).

When you run this version of print_all/1, what happens is a little more complex than simple expansion. 

print_all([1,2,3])
  member([1,2,3], 1)
    write(1), nl
      fail
  retry member([1,2,3], 2)
    write(2), nl
      fail
  retry member([1,2,3], 3)
    write(3), nl
      fail
retry print_all(_)
  true

Verbally, the fail forces Prolog to back up to the last choice point it made and try using the next solution. Well, write/1 and nl/0 don't produce choice points because they only have one solution, but member/2 does have multiple solutions—one for each item in the list. So Prolog takes each item out of the list and prints it. Finally when member/2 runs out of solutions, Prolog backs up to the previous choice point, which is the second body of the print_all/1 predicate, which always succeeds. So the output looks the same. I think people nowadays generally prefer not to use failure-driven loops, but I don't understand the arguments well enough to parrot them usefully.

One thing that may help you to see what's going on is use the trace predicate and step through the expansion of both versions, and see if you can make sense of the differences. My notation above is completely made up for this answer and may not be as clear.

Looking back over what I originally wrote and your actual question:

  • foreach is going to be deterministic
  • member will always iterate in order, because lists are defined in such a way that you must access each item in turn

Moreover, these days at least on S.O. you will get a lot of people telling you to use maplist and its ilk, so it's probably not just going to work, but also a good idea.

Daniel Lyons
  • 22,421
  • 2
  • 50
  • 77
  • I see so build a list with a failure driven loop of the predicate where I want all the solutions, then maplist over the loop to print them.I think will need a failure-driven loop in there somewhere because my program is very much proof-based rather than computation-based. – codeshot Mar 10 '12 at 01:16
  • It should always be possible to do it either way. I'd recommend avoiding the failure driven loop if you can, but if it makes more sense, use it. – Daniel Lyons Mar 10 '12 at 01:44
  • My reading of the documentation of maplist/2 is that the list can be re-ordered which means actions would be executed in arbitrary order. That's means it doesn't solve the problem. Recursion has the added complexity of not describing my intentions but I think foldl/4 implements what I need in a reasonably descriptive way if I just provide a shim around apply that accepts two extra parameters to accumulate nothing: act(A, _, _): call(A) – codeshot Mar 12 '17 at 13:52
  • @codeshot I don't think actions can be executed in arbitrary order. After all, the lists have to be built and traversed front-to-back—that's how linked lists work. Where do you see this in the documentation? Also, five years later...? – Daniel Lyons Mar 13 '17 at 14:50
  • http://www.swi-prolog.org/pldoc/man?predicate=maplist/2 "True if Goal can successfully be applied on all elements of List. Arguments are reordered to gain performance as well as to make the predicate deterministic under normal circumstances." I though it meant that there was an optimisation that takes metadata about the lists contents or how it was constructed and forms a plan as if the list were sorted into some other order. It doesn't promise to execute the goals in list order. – codeshot Mar 17 '17 at 09:11
  • @codeshot I would be pretty amazed if that were the case. And again, linked lists can't be traversed in any other order. I've certainly never heard of anyone having a problem because `maplist/2` did something parallel behind the scenes. – Daniel Lyons Mar 19 '17 at 05:50
  • what alternative meaning is there in the documentation I quoted? – codeshot Mar 19 '17 at 14:14
  • @codeshot "arguments" may mean arguments to maplist (which comes in several different arities) rather than elements of the list. Again, it would be weird for it to mean what you think it means because of the nature of the machine. Also "deterministic under normal circumstances" is exactly how I would _not_ describe reordering the list, since there could be side effects of evaluation. Also, there is no implicit parallelism in ISO Prolog and, to my knowledge, none in SWI specifically either. To be blunt, I think you're crazy, and I want to see proof. Conversation over. – Daniel Lyons Mar 20 '17 at 17:21
  • 1
    Crazy? That's an incredibly rude way to approach somebody checking their work carefully. – codeshot Mar 24 '17 at 22:34
  • @codeshot I apologize for being rude. I understand your desire to cover all the bases. But I think it would not take much more familiarity with Prolog to see that the scenario you're concerned about is based on a very optimistic misunderstanding. I'm not interested in continuing to debate against something you can see is wrong for yourself with five minutes of experimentation or source code reading. At some point, you're spending more of both our time talking than it would take to acquire certainty yourself by working. – Daniel Lyons Mar 27 '17 at 14:13