如何在 prolog 中编写谓词 convert/2? [英] How to write predicate convert/2 in prolog?

问题描述

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

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.

推荐答案

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

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

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

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

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

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

Boris 的评论足以让我意识到按展平长度排序，然后按深度排序适用于您的所有示例，如下所示:

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

这篇关于如何在 prolog 中编写谓词 convert/2?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！