CODEWITHSUNDEEP
prolog
am3decoy
am3decoy

Reputation: 73

Prolog's built-in reverse function acting odd

Given the following code:

fun(a, [b]).
fun(b, [c]).
fun(c, [d]).
fun(d, [e]).
fun(e, []).

xyz(X, Y):-
    fun(X,Z) -> findall([A|B], (member(A,Z), xyz(A,B)), L),
    flatten(L,F), sort(F,J), reverse(J,Y); Y = [].

With the query xyz(a,X) I get the expected output X = [e,d,c,b]..

What could possibly be throwing this off? Does this have to do with the sort function? If so, according to the documents in the links below, alpha or numeric order of precedence could be throwing this off, but it still doesn't explain by cs40 is going before cs30. I am having a hard time finding a correlation. How can I fix this issue?

http://www.swi-prolog.org/pldoc/doc_for?object=sort/2 http://www.swi-prolog.org/pldoc/man?section=compare

By the way, the fun function could have multi-element lists such as fun(a, [b,c], where a has multiple dependencies b and c. This aspect shouldn't matter too much regarding the current issue that I have, but just getting this fact out there.

UPDATE

Thanks to @lurker, I've made some great progress.

Given the following code:

final_xyz(X, Y):- xyz(X, R), reverse(R, Y).
xyz(X, Y) :-
    fun(X,Z) -> findall([A|B], (member(A,Z), xyz(A,B)), L),
    flatten(L,Y); Y = [].

In an attempt to fix this, I updated the code to:

xyz-final(X,Y):-
  fun(X,Z),
  Z\=0,
  ( length(Z,1) -> xyz(X,J), reverse(J,Y)
  ;
      xyz2(X,B), sort(B,C), reverse(C,Y)
  ).

xyz(K, [X|Y]):- fun(K, [X]), !, xyz(X, Y).
xyz(_, []).

xyz2(X, Y) :-
    fun(X,Z) -> findall([A|B], (member(A,Z), xyz2(A,B)), L),
    flatten(L,Y); Y = [].

Very clumsy approach, but this seems to work for me now. I'll work on making it more efficient.

Upvotes: 0

Views: 79

Answers (1)

lurker
lurker

Reputation: 58244

The issue is that you are wanting to reverse the final result, but your reverse is being done in each recursive call to xyz/2. If you do a trace on your xyz(cs140a, X) call, you'll see it's being called a few times on different recursions.

If you want it once at the end, then you can write it this way:

final_xyz(X, Y) :-
    xyz(X, R),
    reverse(R, Y).
xyz(X, Y) :-
    fun(X,Z) -> findall([A|B], (member(A,Z), xyz(A,B)), L),
    flatten(L,Y); Y = [].

And then calling final_xyz(cs140a, X) yields, X = [m16a,cs30,cs40,cs110].

Here's an alternative approach to your xyz predicate which avoids the findall and the flatten. This version should avoid cyclical paths and doesn't show duplicates:

xyz(X, Y) :-
    fun(X, L),
    xyz(L, [], R),
    reverse(R, Y).

xyz([H|T], A, R) :-
    (   memberchk(H, A)
    ->  xyz(T, A, R)
    ;   fun(H, L)
    ->  xyz(L, [H|A], R1),
        xyz(T, R1, R)
    ;   xyz(T, [H|A], R)
    ).
xyz([], A, A).

Upvotes: 1

Related Questions