How to write predicate convert/2 in prolog?

Question

I want to write a predicate convert/2. It should work like this

? - convert([a,[a,a],[a,b],[b,a],[[a,b]],[d],c],X).
X = [a,c,[a],[d],[a,b],[[a,b]]]
yes

? - convert([[a,[a,b]],[a,[c,b]],[[a,b],a]], X).
X = [[a,[a,b]],[a,[b,c]]]
yes

? - convert([[a,b],[a,[a]],[a,b,c]],X).
X = [[a,b],[a,[a]],[a,b,c]]
yes

I know ,that i have to find length of list first. Then i have to sort it and finally i have to merge duplicating elements.

The examples are good; the attempt at defining an algorithm is fine too; it would still help to explicitly define what your convert/2 is actually doing. — user1812457
I want to write a predicate convert/2 which reduces any list (with possibly duplicated elements) to a list in which each distinct element appears only once and a specific order is used. — Eryk Hubert Siejka
I have difficulty understanding one detail in particular: why does [a, b] come before [[a, b]]. What would be the result of querying convert([[a, [b, c]], [a, b, c]], X)? — user1812457
To explain a bit: in your first example, [a,b] sorts before [[a, b]], presumably because the second one is "deeper". However, in the last example, [a, [a]] sorts before [a, b, c], presumably because it is "shorter". So how do you sort two things, when the one is "deeper", while the other one "longer"? — user1812457

Jim Ashworth Jim Ashworth · Accepted Answer · 2017-01-17T17:44:56

So, without knowing exactly what your sorting algorithm is, I have created a somewhat generic example to demonstrate the concept:

convert(X, X) :- \+is_list(X).
convert([],[]).
convert([InHead|InTail], OutList) :-
    convert(InHead, OutHead),
    convert(InTail, OutTail),
    append([OutHead], OutTail, UnsortedList),
    sort(UnsortedList, DeduplicatedList),
    custom_sort(DeduplicatedList, OutList).

custom_sort(List,Sorted) :-
    permutation(List,Sorted),
    is_sorted(Sorted).

is_sorted([]).
is_sorted([_]).
is_sorted([X,Y|T]) :- 
    % perform any number of tests on X and Y here
    % default is:
    X @=< Y,
    is_sorted([Y|T]).

This recursively converts each list in the list, then uses the built-in sort to remove duplicates, then applies a custom sort (built on naive sort).

I initially thought that I had cracked your sorting algorithm (sort by depth of the list (where an atom has depth 0), then by length of the list (where an atom has length 0), then by elements of the list) and came up with the following:

list_length(X, 0) :- 
    \+is_list(X).
list_length(X, Y) :- 
    is_list(X), length(X, Y).

list_depth(X, 0) :- \+is_list(X).
list_depth([], 0).
list_depth([Head|Tail], Y) :-
    list_depth(Head, YH),
    list_depth(Tail, YTP),
    YT is YTP - 1,
    Y is max(YH, YT) + 1.

is_sorted([X,Y|T]) :- 
    list_length(X, XL), 
    list_length(Y, YL),
    list_depth(X, XD),
    list_depth(Y, YD),
    ( XD < YD ; 
      ( XD = YD,
        ( XL < YL ; 
          ( XL = YL, 
            X @=< Y) 
        )
      )
    ),
    is_sorted([Y|T]).

... but this fails for your third example, where [a,[a]],[a,b,c] has depth 2 followed by depth 1, so I present the code above for your enjoyment more than anything else.

Edit: The comment from Boris was enough for me to realise that sorting by flattened length then depth works for all of your examples, which looks like this:

list_length(X, 0) :- 
    \+is_list(X).
list_length(X, Y) :- 
    is_list(X), 
    flatten(X, Z), 
    length(Z, Y).

list_depth(X, 0) :- \+is_list(X).
list_depth([], 0).
list_depth([Head|Tail], Y) :-
    list_depth(Head, YH),
    list_depth(Tail, YTP),
    YT is YTP - 1,
    Y is max(YH, YT) + 1.

is_sorted([X,Y|T]) :- 
    list_length(X, XL), 
    list_length(Y, YL),
    list_depth(X, XD),
    list_depth(Y, YD),
    ( XL < YL ; 
      ( XL = YL,
        ( XD < YD ; 
          ( XD = YD, 
            X @=< Y) 
        )
      )
    ),
    is_sorted([Y|T]).

How to write predicate convert/2 in prolog?

2 Answers