如何在序言中编写谓词 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]).

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