Prolog：一次对列表的一个元素求和

Question

我是 Prolog 的新手，决定尝试解决一个问题，其中我有一个符号序列，每个符号的值为 1 或 -1。我需要的是将它们全部加在一起，一次加一个元素，然后提取总和第一次低于 0 的索引。因为我来自命令式背景，所以我想象一个计数变量和一个for 循环，但显然我不能在 Prolog 中这样做。

value('(', 1).
value(')', -1).

main(R) :- readFile("input", R), ???

readFile(Path, R) :- 
    open(Path, read, File), 
    read_string(File, _, Str), 
    stringToCharList(Str, Xs), 
    maplist(value, Xs, R).

stringToCharList(String, Characters) :-
    name(String, Xs),
    maplist(toChar, Xs, Characters ).

toChar(X, Y) :- name(Y, [X]).

如您所见，到目前为止我真正做到的是读取包含序列的文件，并将其转换为 1 和 -1。我不知道从这里去哪里。我想问题有三方面：

我需要遍历列表
我需要对列表中的每个元素求和
我需要return某个索引

有什么建议吗？我能以某种方式切断列表，其中迭代会将总和降低到零以下，并且只是 return 长度吗？

Answer 1

我将使用 Prolog 中的一个原则，辅助变量作为计数器，直到条件达到我们想要的。然后辅助计数器在基本情况下与该点的变量统一。

我在这里盲目地假设您的代码按规定工作。我没有测试它（那取决于你）。

main(IndexAtZeroSum) :- readFile("input", R), index_at_zero_sum(R, IndexAtZeroSum).

readFile(Path, R) :- 
    open(Path, read, File), 
    read_string(File, _, Str), 
    stringToCharList(Str, Xs), 
    maplist(value, Xs, R).

stringToCharList(String, Characters) :-
    name(String, Xs),
    maplist(toChar, Xs, Characters ).

toChar(X, Y) :- name(Y, [X]).

% The following predicate assumes indexing starting at 0
index_at_zero_sum([V|Vs], IndexAtZeroSum) :-
    index_at_zero_sum(Vs, V, 0, IndexAtZeroSum).

% When sum is zero, Index is what we want
index_at_zero_sum(_, 0, Index, Index).
index_at_zero_sum([V|Vs], Sum, CurIndex, Index) :-
    S is Sum + V,
    NextIndex is CurIndex + 1,
    index_at_zero_sum(Vs, S, NextIndex, Index).

index_at_zero_sum/2 提供总和变为零的给定列表的索引。它通过使用辅助谓词 index_at_zero_sum/4 来实现，从第一个值的总和开始（总和是值本身），当前索引从 0 开始。因此第二个参数是索引 0 处的总和。对 index_at_zero_sum/4 的后续调用会递增索引并累加总和，直到总和变为 0。此时，基本情况成功并将第 4 个参数与当前索引统一。如果在列表变空之前总和永远不会变为 0，则谓词失败。

您还可以避免读取整个文件并使用 get_char/2:

创建数字列表

index_at_zero_sum(Path, Index) :-
    open(Path, read, File),
    get_char(File, C),
    value(C, V),
    (   index_at_zero_sum(File, V, 0, Index)
    ->  close(File)
    ;   close(File),
        fail
    ).

index_at_zero_sum(_, 0, Index, Index).
index_at_zero_sum(File, Sum, CurIndex, Index) :-
    get_char(File, C),
    value(C, V),
    S is Sum + V,
    NewIndex is CurIndex + 1,
    index_at_zero_sum(File, S, NewIndex, Index).

Prolog：一次对列表的一个元素求和

Prolog: Sum one element of a list at a time

iteration

sum

list

prolog

swi-prolog