Get the output value from a Prolog recursive function

Question

I am learning Prolog these days and need to combine two list into one that follows this rule:

ListA: [], ListB: [] => ResultList: []
ListA: [], ListB:[a,b,c] => ResultList: [[a],[b],[c]]
ListA: [1,2], ListB:[a,b,c] => ResultList: [[1,2,a],[1,2,b],[1,2,c]]

I am stuck with a recursive function output value problem and here is my coding:

extend_my_path([],_,_,_).
extend_my_path([H|T],OriginalPath,OrignailMewPaths,NewPaths) :-
    append(OriginalPath,[H],NewPath),
    append(OrignailMewPaths,[NewPath],NewPaths1),
    print("NewPaths1:"),print(NewPaths1), nl,
    extend_my_path(T,OriginalPath,NewPaths1,NewPaths1).

Running it gives the following output without the value of Result varable:

?- extend_my_path([a,b,c],[1,2],[],Result).
"NewPaths1:"[[1,2,a]]
"NewPaths1:"[[1,2,a],[1,2,b]]
"NewPaths1:"[[1,2,a],[1,2,b],[1,2,c]]
true.

I wish to get its value like:

Result=[[1,2,a],[1,2,b],[1,2,c]]

It is highly appreciated if anyone can point out the reason. Thanks.

Daniel Lyons Daniel Lyons · Accepted Answer · 2018-09-19T04:31:52

I see quite a bit of confusion in these six lines of code. Here are some clues that something is amiss:

Your problem is defined in terms of three things, but your predicate has four arguments. What are the last two supposed to be?
You have a singleton variable NewPaths which is a disaster
Your base case relates an empty list to any three other things! Try it: extend_my_path([], lightning, [the,sound,of,rain], "fresh coffee") is true! This seems unlikely to be what you intended.
One wonders what an "Orignail Mew Paths" is, or what "paths" have to do with anything here. Typos matter, fix them!
The inductive case ends with two copies of NewPaths1, which seems suspicious because we had two very different variables at the start, and as you see in the base case it doesn't matter what they are. Odd!

I think what happened here is that you figured the only and right way to add things to a list is with append/3, which isn't true. I think further Prolog's single-assignment semantics convinced you that you needed another argument to create the empty list for you to append to. You missed the base case for your recursion so you never got a sensible return; making it wide open at least got you to true but didn't give you a binding. And the fundamental problem here is that there isn't a sensible relation in your code. Let's try again.

You're trying to write a predicate whose name and arguments are something more like this:

% extend_path(Path, Possibilities, NewPaths)

There's no need for a fourth argument here, because you don't need to know what you've done so far in creating NewPaths, you can just build the paths for the current possibility and know that recursion is taking care of the rest.

Your base case would then be the case where you have no more possibilities, and thus, no new paths:

extend_path(_, [], []).

This doesn't say anything-relates-to-anything, it says "the path extensions of any prefix, when I'm out of possibilities, is empty."

Your inductive case then takes your first argument and appends it onto the next item from your list of possibilities. This goes on your list of new paths.

extend_path(Prefix, [Ext1|ExtRest], [Next1|NextRest]) :-
    append(Prefix, [Ext1], Next1),
    extend_path(Prefix, ExtRest, NextRest).

This literally says "given some Prefix, and that I have an Ext left in my list of extensions, will produce a new path extension Next1, such that: Prefix + [Ext1] is Next1." Actually, it says a little more than that with the recursive step. But the idea here is bite off one piece, Ext1, and match it up with one piece of the result, Next1, and then match up the rest of the input with the rest of the output.

Lastly, please do not treat a singleton variable "warning" as a warning. This is not like Python being mad that you don't have enough newlines between functions. Singleton variables are almost always CRITICAL ERRORS, especially for new users of Prolog! Pay attention to them!

Hope this helps!

Get the output value from a Prolog recursive function

2 Answers