[cosmicappuccino]

I would appreciate insight/clarification on why the first two examples give stack overflow when I try "perm([1,2,3],X)." to generate all solutions, whereas the third works fine.

% Example 1
perm([], []).
perm([H|T], List) :- take(List, H, L), perm(T, R).

% Example 2
perm([], []).
perm(List, [H|T]) :- take(List, H, L), perm(T, R).

% Example 3
perm([], []).
perm(List, [H|T]) :- take(List, H, L), perm(R, T).

Note: take/3 is defined by the following:

take([H|T], H, T).
take([H|T], A, [H|U]) :- take(T, A, U).

Thanks a lot for your time!

This post has been edited by cosmicappuccino: 25 December 2011 - 11:49 AM

[sepp2k]

In the first example you're calling take with unbound variables as its first and third arguments. Clearly that can't do anything useful.

In the second version neither R nor T are bound when you give them as arguments to perm, so I can't see how that could possibly have a useful result. Also you never use R except in the call to perm.

In the third version the same is true. So frankly, I don't believe you that that version works.

[cosmicappuccino]

Thanks for your feedback.

I made a very stupid mistake in transcribing the predicates to this thread, and you're absolutely right that of course, the above predicates wouldn't work. The intended code was as follows:

% Example 1
perm([], []).
perm([H|T], List) :- take(List, H, R), perm(T, R).

% Example 2
perm([], []).
perm(List, [H|T]) :- take(List, H, R), perm(T, R).

% Example 3
perm([], []).
perm(List, [H|T]) :- take(List, H, R), perm(R, T).

I also think I have a slightly better intuition now about how this works, with the bound and unbound arguments...

Apologies for the ridiculous error in my first post.

[sepp2k]

Okay, this makes more sense. The first version still doesn't work for the reason I mentioned: Since List is the second argument to perm, which is the one that is unknown, both the first and the third argument to take are unknown. You can use take to determine the second and the third argument from the first or you can use it to determine the first argument from the second and the third. But you can't use it if both the first and the third argument are unknown.

The second version doesn't work because when you call perm recursively you give T as the first argument and R as the second. Since T is unknown this means that you're calling it with the unknown variable as the first argument and the known variable as the second argument. But the way perm is defined, it needs to be the other way around (otherwise you get the same problem as in the first version because now T is the new value for List and therefor List is unknown again and you again call take with two unknown values).

The third version works because take determines possible values for H and R and thus when you call perm its first argument is known and its second argument is unknown which is how its meant to be used.