Prolog

Question

所以我有一个如下所示的列表：

[ 
  ["p1", "p2", "100", "Storgatan"], 
  ["p1", "p3", "200", "Lillgatan"], 
  ["p2", "p4", "100", "Nygatan"], 
  ["p3", "p4", "50", "Kungsgatan"], 
  ["p4", "p5", "150", "Kungsgatan"]
]

每个嵌套列表中的元素代表（按顺序）：
第一个元素 = 起点
第二个元素 = 终点
第三个元素=距离
第 4 个元素 = 街道名称。

我现在必须编写一个谓词，计算出哪条街道最短，哪条街道最长，以及它们各自的（总和）距离。

例如，最终输出应如下所示：

Longest street: Kungsgatan, 200
Shortest street: Storgatan, 100

我不太明白为什么起点和终点是这里的相关信息。我目前的想法是收集所有唯一的街道名称，将它们与从零开始的每条街道的计数器一起放在一个单独的列表中，然后使用该列表累积每条单独街道的所有距离。

类似于：

create_sum_list([
   ["p1", "p2", "100", "Storgatan"], 
   ["p1", "p3", "200", "Lillgatan"], 
   ["p2", "p4", "100", "Nygatan"], 
   ["p3", "p4", "50", "Kungsgatan"], 
   ["p4", "p5", "150", "Kungsgatan"]
], SL).

SL= [[Storgatan, 0], [Lillgatan, 0],
     [Nygatan, 0], [Kungsgatan ,0]]

accumulate(SL, List).

List=[[Storgatan, 100], [Lillgatan, 200], 
      [Nygatan, 100], [Kungsgatan ,200]]

这可能是个愚蠢的想法，可能有更好的方法来解决这个问题。我想过很多不同的想法，要么我走到了死胡同，要么它们对于这样的 "simple" 任务来说太复杂了。

我可以通过 "normal" 命令式编程轻松实现这一点，但我是逻辑编程和 Prolog 的新手。我不知道如何实现这一目标。

帮忙？

谢谢！

Answer 1

因为这是作业，所以我不会给你完整的答案，而是代码的关键部分。

正如我在评论中指出的那样，结构的格式很重要，例如列表、术语、原子、字符串等

test(Street_lengths,Shortest) :-
    List =
        [
         street(p1, p2, 100, 'Storgatan'),
         street(p1, p3, 200, 'Lillgatan'),
         street(p2, p4, 100, 'Nygatan'),
         street(p3, p4, 50,  'Kungsgatan'),
         street(p4, p5, 150, 'Kungsgatan')
        ],
    street_lengths(List,Street_lengths),
    lengths1(Street_lengths,Lengths),
    min_list(Lengths,Min),
    convlist(value_shortest2(Min),Street_lengths,Shortest).

street_lengths([H|T],Street_lengths) :-
    merge_streets(H,T,Street_lengths).

% 2 or more items in list
merge_streets(street(_,_,Length0,Name),[street(_,_,Length1,Name),street(_,_,Length2,Name2)|Streets0],[street(Length,Name)|Streets]) :-
    Length is Length0 + Length1,
    merge_streets(street(_,_,Length2,Name2),Streets0,Streets).
merge_streets(street(_,_,Length0,Name0),[street(_,_,Length1,Name1)|Streets0],[street(Length0,Name0)|Streets]) :-
    Name0 \= Name1,
    merge_streets(street(_,_,Length1,Name1),Streets0,Streets).

% 1 item in list
merge_streets(street(_,_,Length0,Name),[street(_,_,Length1,Name)],[street(Length,Name)]) :-
    Length is Length0 + Length1.
merge_streets(street(_,_,Length0,Name0),[street(_,_,Length1,Name1)],[street(Length0,Name0)|Streets]) :-
    Name0 \= Name1,
    merge_streets(street(_,_,Length1,Name1),[],Streets).

% no item in list
merge_streets(street(_,_,Length,Name),[],[street(Length,Name)]).

lengths1(List,Lengths) :-
    maplist(value_length1,List,Lengths).

value_length1(street(Length,_),Length).

value_shortest2(Min,street(Min,Name),street(Min,Name)).

示例运行：

?- test(Street_lengths,Shortest).
Street_lengths = [street(100, 'Storgatan'), street(200, 'Lillgatan'), street(100, 'Nygatan'), street(200, 'Kungsgatan')],
Shortest = [street(100, 'Storgatan'), street(100, 'Nygatan')] ;
false.

我给你留了最长的时间，但应该是小菜一碟。

要显示您在问题中提到的信息，我会使用 format/2。

因此，现在您要么必须更改将数据读入此代码格式的方式，要么更改此代码以适应您构建数据的方式。恕我直言，我会更改数据以使用此结构。

如果想知道您的代码效率如何，可以使用 time/1

?- time(test(Street_lengths,Shortest)).
% 44 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Street_lengths = [street(100, 'Storgatan'), street(200, 'Lillgatan'), street(100, 'Nygatan'), street(200, 'Kungsgatan')],
Shortest = [street(100, 'Storgatan'), street(100, 'Nygatan')] ;
% 17 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
false.

Answer 2

如果您已经有一个列表并且想要按街道名称分组并对长度求和，则必须决定如何进行分组。一种方法是使用 library(pairs):

streets_lengths(S, L) :-
    maplist(street_name_and_length, S, NL),
    keysort(NL, NL_sorted),
    group_pairs_by_key(NL_sorted, G),
    maplist(total_lengths, G, GT),
    transpose_pairs(GT, By_length), % sorts!
    group_pairs_by_key(By_length, L).

street_name_and_length([_, _, N, L], L_atom-N_number) :-
    number_string(N_number, N),
    atom_string(L_atom, L).

total_lengths(S-Ls, S-T) :-
    sum_list(Ls, T).

你可以这样使用它：

?- streets_lengths([
   ["p1", "p2", "100", "Storgatan"],
   ["p1", "p3", "200", "Lillgatan"],
   ["p2", "p4", "100", "Nygatan"],
   ["p3", "p4", "50", "Kungsgatan"],
   ["p4", "p5", "150", "Kungsgatan"]
], SL).
SL = [100-['Storgatan', 'Nygatan'], 200-['Lillgatan', 'Kungsgatan']].

由于可以有很多条相同长度的街道，因此结果按长度分组返回。您可以通过获取列表的第一个和最后一个元素来获取 "shortest" 和 "longest"，如下所示：

L = [First|_], last(L, Last)

Prolog - 跟踪多个总和计数器

Prolog - Keep track of multiple sum counters

counter

sum

list

accumulate