CODEWITHSUNDEEP
sortingprolog
Jozef
Jozef

Reputation: 3

How do I sort a resultant list in Prolog?

So I've got these predicates, 

isSorted([]).
isSorted([_]).
isSorted([A,B|L]) :- A =< B, isSorted([B|L]).

toEven([], L2) :- isSorted(L2); sort(L2, OP), write(OP), toEven([], OP).
toEven([F|L1], [DUB|L2]) :- F mod 2 =\= 0, DUB is 2 * F, toEven(L1, L2).
toEven([F|L1], [F|L2]) :- F mod 2 =:= 0, toEven(L1, L2).

where toEven(L, X) doubles any odd numbers inputted in order to achieve a completely even list.

Currently, inputting toEven([1,2,3,4,5], X) returns a correct result of X = [2, 2, 6, 4, 10], but my attempt to sort the list seems to be having no effect. I would've thought in the base case it would check if L2 is sorted and if not sort and call toEven() with the sorted result instead.

Does anyone have any idea where I'm going wrong with this? I've been trying to figure it out with trace to no avail.

Upvotes: 0

Views: 141

Answers (1)

lurker
lurker

Reputation: 58234

The primary issue with your implementation is that it only outputs the result, via write, if the list is not sorted when it's created:

toEven([], L2) :- isSorted(L2) ; sort(L2, OP), write(OP), toEven([], OP).

If isSorted(L2) succeeds, then toEven([], L2) concludes successfully without any further action (no output via write).

In Prolog, it's best to generate results are arguments, not with write. It's also probably just as efficient to sort the list unconditionally, even if it's already sorted, since your check to see if it's already sorted costs something and has to recurse the entire list and do a comparison on each element. You also want to be careful with sort/2... it removes duplicates. Use msort/2 if you want to keep duplicates.

Wrapping all that up:

toEven(L, LEven) :-
    toEvenAux(L, LEvenUnsorted),
    msort(LEvenUnsorted, LEven).

toEvenAux([], []).
toEvenAux([F|L1], [DUB|L2]) :- F mod 2 =\= 0, DUB is 2 * F, toEvenAux(L1, L2).
toEvenAux([F|L1], [F|L2]) :- F mod 2 =:= 0, toEvenAux(L1, L2).

Upvotes: 2

Related Questions