prolog - 如何在序言中编写谓词convert/2？

Question

我想写一个谓词convert/2。 它应该像这样工作

? - 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

我知道，我必须首先找到列表的长度。 然后我必须对其进行排序，最后我必须合并重复的元素。

Answer 1

因此，在不确切知道您的排序算法是什么的情况下，我创建了一个有点通用的示例来演示这个概念:

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]).

这会递归地转换列表中的每个列表，然后使用内置排序来删除重复项，然后应用自定义排序(基于朴素排序构建)。

我最初以为我已经破解了你的排序算法(按列表的深度排序(其中原子的深度为 0)，然后按列表的长度排序(其中原子的长度为 0)，然后按列表的元素排序)并得出以下结论:

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]).

...但是这对于你的第三个例子来说是失败的，其中 [a,[a]],[a,b,c] 的深度为 2，后跟深度 1，所以我提供上面的代码是为了让你享受。否则。

编辑: 鲍里斯的评论足以让我意识到按扁平化长度然后深度进行排序适用于您的所有示例，如下所示:

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]).