Пролог: Создание списка частот другого списка

Question

Итак, я написал программу, которая читает входные данные из файла .txt в виде 2 целых чисел и списка целых чисел: первое целое число - длина списка, второе - количество различных элементов,и список является рассматриваемым списком.

Затем я хочу создать список частот для элементов, например, так:

List = [1, 2, 3, 1, 3, 2, 3, 1],
FreqList = [3, 2, 3].

Вот мой код:

% Create random list
createList(List) :-
length(List, 10), 
maplist(random(0,4), List).

% Count the frequency of an element:
countElement(_, [], 0) :- !.
countElement(_, [], _).
countElement(Element, [Element|Tail], Counter) :-
    countElement(Element, Tail, Counter2),
    Counter is Counter2 + 1.
countElement(Element, [_|Tail], Counter) :-
    countElement(Element, Tail, Counter).

% Create frequency list:
createFreqList(_, _, Numbers, [], CurrentNumber) :-
    Numbers = CurrentNumber.
createFreqList(List, Length, Numbers, [Head|Tail], CurrentNumber) :-
    Numbers \= CurrentNumber,
    countElement(CurrentNumber, List, Head),
    CurrentNumber2 is CurrentNumber + 1,
    createFreqList(List, Length, Numbers, Tail, CurrentNumber2).

frequency(List, FreqList) :-
    createList(List),
    Numbers2 is 4,
    createFreqList(List, 10, Numbers2, FreqList, 1).

Итак, при первом выполнениипрограмма работает нормально и выводит правильный список частот.Однако, если я введу ';', вместо того, чтобы дать мне 'false', он снова запустится, выведет неправильный список частот, и это будет повторяться, пока я нажимаю ';'.

Answer 1

Я бы, вероятно, сделал что-то вроде этого:

frequencies(Xs, Fs) :-
  msort(Xs,Sorted),
  glob( Sorted, [], Fs ).

glob( [], Fs, Fs ).
glob( [X|Xs], [X:N|Ts], Fs ) :-
  !,
  N1 is N+1,
  glob(Xs, [X:N1|Ts], Fs ).
glob( [X|Xs], Ts, Fs ) :-
  glob(Xs, [X:1|Ts], Fs).

Это использовало msort/2, чтобы поместить список в последовательность. Результирующий список находится в порядке убывания по значению ключа - [ 3:123, 2:25, 1:321 ].

Вы также можете сделать что-то вроде этого:

frequencies(Xs, Fs) :- frequencies( Xs, [], Fs ).

frequencies( [],     Fs, Fs ).
frequencies( [X|Xs], Ts, Fs ) :-
  tote( X, Ts, T1),
  frequencies(Xs, T1, Fs).

tote( X, Ts, Fs ) :-
  append( Pfx, [X:N|Sfx], Ts),
  !,
  N1 is N+1,
  append( Pfx, [X:N1|Sfx], Fs).
tote( X, Ts, [X:1|Ts] ).

Я подозреваю, что одноразовая сортировка исходного списка, вероятно, будет быстрее, чем повторное сканирование списка аккумуляторов.

Answer 2

На всякий случай, если вы не хотите изобретать велосипед.

Существует квазистандарт, называемый библиотекой (агрегатом). Но библиотека (агрегат) также может быть реализована поверх базового стандарта ISO bagof / 3, который также поможет вам:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.6)

?- aggregate(count, member(X,[1, 2, 3, 1, 3, 2, 3, 1]), R).
X = 1,
R = 3 ;
X = R, R = 2 ;
X = R, R = 3.

?- bagof(hit, member(X,[1, 2, 3, 1, 3, 2, 3, 1]), L), length(L, R).
X = 1,
L = [hit, hit, hit],
R = 3 ;
X = R, R = 2,
L = [hit, hit] ;
X = R, R = 3,
L = [hit, hit, hit].

Или в другой системе Prolog:

Jekejeke Prolog 3, Runtime Library 1.3.7 (May 23, 2019)

?- use_module(library(advanced/aggregate)).
% 3 consults and 0 unloads in 110 ms.
Yes

?- use_module(library(basic/lists)).
% 0 consults and 0 unloads in 0 ms.
Yes

?- aggregate(count, member(X,[1, 2, 3, 1, 3, 2, 3, 1]), R).
X = 1,
R = 3 ;
X = 2,
R = 2 ;
X = 3,
R = 3

?- bagof(hit, member(X,[1, 2, 3, 1, 3, 2, 3, 1]), L), length(L, R).
X = 1,
L = [hit,hit,hit],
R = 3 ;
X = 2,
L = [hit,hit],
R = 2 ;
X = 3,
L = [hit,hit,hit],
R = 3