Prolog: My newly created list becomes empty on exiting recursion?

Question

I am new to prolog and I am on the edge of solving one problem, but I have issue when I am trying to exit the recursion and return the list back to the initial function. Can you please help me out ? I have being struggling with it all day. Thanks

Here is what happens in the end when I have build the list: enter image description here

Here are my predicates:

depth_first(N, ReturnList) :-
   df_real(2:1, N, [2:1], ReturnList).

df_real(_:NextRankC, Size, Q, ReturnList) :- 
   genInt(Size, Row), 
   Column is NextRankC + 1,
   Rank = Row:Column,
   not(list_attack(Rank, Q)),
   add(Rank, Q, NewList),
   df_real(1:Column, Size, NewList, NewList).
% Recursive Case: Exit when list is full.
df_real(_, N, Q, Newlist) :- length(Q, Length),
   N = Length.

Calling the Predicate: depth_first(4,Q). Note: Assume that genInt/2, add/3 and list_attack/2 are working perfectly, my issue is in the end when it just removes all of the elements I just build and returns some variables, instead of true, it must return the list.

UPDATE When I use

 df_real(_:NextRankC, Size, Q, NewList) :-
    ...
    df_real(1:Column, Size, NewList, NewList).

Tracing - Fails add because NewList is now a List and not a Variable to add to the list.

enter image description here

Your predicate, df_real(_:NextRankC, Size, Q, _) :- ... has an anonymous variable, _ (which remains uninstantiated) where I'm supposing you want to return your list. Make it, df_real(_:NextRankC, Size, Q, NewList) :- ... instead. Also, for brevity, your first predicate could be written, depth_first(N, ReturnList) :- df_real(2:1, N, [2:1], ReturnList). — lurker
What doesn't? Putting NewList as the last argument to df_real instead of _? I don't see how it could not make a difference in results. When you put it there, what results do you get? It must make some difference even if it's not correct yet. Judging from your partial trace, it should work, or at least get you a lot closer to what you want. — lurker
@lurker well It's the same It returns TRUE and when I trace it I get the same output that when the condition which checks the length returns True it pops out each element from the created list and returns Variables like in the picture :( — Unsparing
Please show the updated code that you ran, to be clear, and the updated trace. If you did as I suggested, there's no way for the trace to look just like the one you are showing in your problem statement. The other problem you have is the first argument uses _ as well (in the _:NextRankC term). I'm not sure what you intend to do with that argument, but it gets lost because you made it anonymous. Maybe it doesn't matter since you already pass the same thing in the 3rd argument anyway. — lurker

lurker lurker · Accepted Answer · 2015-03-11T13:45:15

The issue with the code, ultimately, is that you need to set up a proper pattern for returning the list. A common pattern in Prolog is to pass in a variable argument that is carried through all of the recursions and is finally instantiated in the terminal case. The variable is set up initially in the first clause.

depth_first(N, ReturnList) :-
    df_real(2:1, N, [2:1], ReturnList).

So here the first query is initiated with the 4th argument as the variable for returning the answer list, ReturnList. So far, so good.

df_real(_:NextRankC, Size, Q, ReturnList) :- 
    genInt(Size, Row), 
    Column is NextRankC + 1,
    Rank = Row:Column,
    not(list_attack(Rank, Q)),
    add(Rank, Q, NewList),
    df_real(1:Column, Size, NewList, NewList).

Initially, you had _ as the 4th argument, which was incorrect because you need the 4th argument as a variable in which you can return the answer. Having the 4th argument as ReturnList now, is good, but there's no call currently inside of this clause which instantiates it. So your trace shows _XXXX for its value (it's uninstantiated). The problem is with the last call:

    df_real(1:Column, Size, NewList, NewList).

For some reason, you have NewList as both the 3rd and 4th arguments. You probably want ReturnList as the 4th argument so that it is carried through the recursion and will finally be set:

    df_real(1:Column, Size, NewList, ReturnList).

Lastly, the terminal (or base) case:

% Recursive Case: Exit when list is full.
df_real(_, N, Q, Newlist) :-
    length(Q, Length),
    N = Length.

NewList as the 4th argument here does nothing. It's a singleton variable and doesn't get filled in with anything. So in a trace, it will show up as _XXXX and you'll have no answer in ReturnList. The clause is indicated that you're done when the Q list has reached length N. I'm supposing that, at that point, Q is your answer that you want. So you just need to say so, in Prolog:

% Recursive Case: When list is full, it's the answer
df_real(_, N, Q, Q) :-
    length(Q, N).

You can also tidy up a little by simplifying the first argument. It's a term of the form X:Y and you never use X, so why carry it around?

depth_first(N, ReturnList) :-
    df_real(1, N, [2:1], ReturnList).

df_real(_:NextRankC, Size, Q, ReturnList) :- 
    genInt(Size, Row), 
    Column is NextRankC + 1,
    Rank = Row:Column,
    \+ list_attack(Rank, Q),   % Note use of ISO negation predicate, \+
    add(Rank, Q, NewList),
    df_real(Column, Size, NewList, ReturnList).

% Recursive Case: When list is full, it's the answer
df_real(_, N, Q, Q) :-
    length(Q, N).

Prolog: My newly created list becomes empty on exiting recursion?

1 Answers