如何在 Prolog 中编写一个对列表进行操作的函数

Question

如何在Prolog中编写包含n个a和n个b的程序，这里需要注意的是列表中a和b的数量必须相等，而且列表必须始终从头开始以 a 结束，以 b 结束，否则为假。示例：[a,b] 是 true，[a,a,a,b,b,b] 是 true，[a,a,a,a] 是 false，[a,a,a,b,b] 也是 false .

这是我尝试做的事情：

langageB([b]).
langageB([b| S]):- langageB(S).

language([]).

langage([a,b]).
langage([a | S]):- langage(S).
langage([a| S]):- langageB(S).

但它并没有像我想要的那样工作。

Answer 1

使用DCG表示法，所需的语言可以定义为：

langage --> [a,b].
langage --> [a], langage, [b]. % For each a at the beginning of the list 
                               % there must be a corresponding b at the end

langage(List) :- phrase(langage, List).

示例：

?- langage([a,a,a,b,b,b]).
true .

?- langage([a,a,b,b,b]).
false.

?- langage(L).
L = [a, b] ;
L = [a, a, b, b] ;
L = [a, a, a, b, b, b] ;
L = [a, a, a, a, b, b, b, b] .

如果你想看看如何直接使用差异列表定义谓词，你可以列出谓词的子句langage/2:

?- listing(langage).

langage([a, b|A], A).

langage([a|A], B) :-
    langage(A, C),
    C=[b|B].

因此，另一种解决方案是：

langage(List) :-
  langage(List, []).

langage([a, b|A], A).

langage([a|A], B) :-
    langage(A, C),
    C = [b|B].

Answer 2

假设例如[a, b, a, b] 是可接受的列表：

go :-
    findnsols(20, ABs, ab_list(ABs), ABsLst), !,
    writeln(ABsLst).


ab_list(ABsWrapped) :-
    length(ABs, Len),
    ab_list_(Len, 0, [], ABs),
    append([[a], ABs, [b]], ABsWrapped).


ab_list_(0, 0, ABs, ABs) :- !.

ab_list_(CharsToAdd, Bal, SoFar, ABs) :-
    succ(CharsToAdd0, CharsToAdd),
    add_char(Char, Inc),
    Bal1 is Bal + Inc,
    % Ensure that the balance can be zero for the complete list
    CharsToAdd0 >= abs(Bal1),
    ab_list_(CharsToAdd0, Bal1, [Char|SoFar], ABs).

add_char(b, -1).
add_char(a, 1).

结果：

?- time(go).
[[a,b],[a,a,b,b],[a,b,a,b],[a,a,a,b,b,b],[a,a,b,a,b,b],[a,b,a,a,b,b],[a,a,b,b,a,b],[a,b,a,b,a,b],[a,b,b,a,a,b],[a,a,a,a,b,b,b,b],[a,a,a,b,a,b,b,b],[a,a,b,a,a,b,b,b],[a,b,a,a,a,b,b,b],[a,a,a,b,b,a,b,b],[a,a,b,a,b,a,b,b],[a,b,a,a,b,a,b,b],[a,a,b,b,a,a,b,b],[a,b,a,b,a,a,b,b],[a,b,b,a,a,a,b,b],[a,a,a,b,b,b,a,b]]
    % 935 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 1419728 Lips)

原文：这是一个（非常低效的）解决方案，作为 swi-prolog 中的一行：

length(As, 2), same_length(As, Bs), maplist(=(a), As), maplist(=(b), Bs), append([As, Bs], ABs), distinct(ABsPerm, permutation(ABs, ABsPerm)), append([[a], ABsPerm, [b]], Final).

Answer 3

langage --> [a], ( [] | langage ) , [b].

?- phrase(langage, Xs).
   Xs = "ab"
;  Xs = "aabb"
;  Xs = "aaabbb"
;  Xs = "aaaabbbb"
;  Xs = "aaaaabbbbb"
;  ...

如何在 Prolog 中编写一个对列表进行操作的函数

How to program in Prolog a function that does operations on lists

prolog

dcg