Числа вхождений Пролога

Question

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

?- count_occurrences([a,b,c,a,b,c,d], X). 
X = [[d, 1], [c, 2], [b, 2], [a, 2]]. 

и это мой код, я знаю, что это не полное, но я стараюсь :

count_occurrences([],[]). 
count_occurrences([X|Y],A):- 
    occurrences([X|Y],X,N). 

occurrences([],_,0).  
occurrences([X|Y],X,N):- occurrences(Y,X,W), N is W + 1. 
occurrences([X|Y],Z,N):- occurrences(Y,Z,N), X\=Z. 

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

Answer 1

Вот мое решение, использующее bagof/3 и findall/3:

count_occurrences(List, Occ):- 
    findall([X,L], (bagof(true,member(X,List),Xs), length(Xs,L)), Occ). 

Пример

?- count_occurrences([a,b,c,b,e,d,a,b,a], Occ). 
Occ = [[a, 3], [b, 3], [c, 1], [d, 1], [e, 1]]. 

Как это работает

bagof(true,member(X,List),Xs) выполняется для каждого отдельного элемента списка X с Xs быть список с его длиной, равной числу вхождений X в List:

?- bagof(true,member(X,[a,b,c,b,e,d,a,b,a]),Xs). 
X = a, 
Xs = [true, true, true] ; 
X = b, 
Xs = [true, true, true] ; 
X = c, 
Xs = [true] ; 
X = d, 
Xs = [true] ; 
X = e, 
Xs = [true]. 

Наружный findall/3 собирает элемент X и длина связанный список Xs в списке, представляющем решение.

Редактировать I: первоначальный ответ был улучшен благодаря предложениям CapelliC и Boris.

Edit II: setof/3 может быть использован вместо findall/3, если есть свободные переменные в данном списке.Проблема с setof/3 заключается в том, что для пустого списка это не удастся, поэтому необходимо ввести специальное предложение.

count_occurrences([],[]). 
count_occurrences(List, Occ):- 
    setof([X,L], Xs^(bagof(a,member(X,List),Xs), length(Xs,L)), Occ). 

Answer 2

Одна вещь, которая должна сделать решение проблемы проще было бы разработать помощника пр чтобы увеличить счетчик.

Представьте предикат, который принимает список пар [SomeAtom,Count] и атом, счет которого необходимо увеличить, и создает список с увеличенным счетчиком или [SomeAtom,1] для первого вхождения атома. Этот предикат легко дизайн:

increment([], E, [[E,1]]). 
increment([[H,C]|T], H, [[H,CplusOne]|T]) :- 
    CplusOne is C + 1. 
increment([[H,C]|T], E, [[H,C]|R]) :- 
    H \= E, 
    increment(T, E, R). 

Первый пункт служит в качестве базового случая, когда мы добавляем первое вхождение. Второе предложение служит еще одним базовым случаем, когда элемент головки соответствует искомому элементу. Последний случай - это рекурсивный вызов ситуации, когда элемент головы не соответствует требуемому элементу.

С помощью этого предиката в руке, написание count_occ становится очень просто:

count_occ([], []). 
count_occ([H|T], R) :- 
    count_occ(T, Temp), 
    increment(Temp, H, R). 

Это заурядный рекурсивный предикат Пролога, с тривиальным п базового и рекурсивным вызовом, который обрабатывает хвост, а затем использует increment для учета элемента заголовка списка.

Demo.

Answer 3

Если вы используете SWI-Prolog, вы можете сделать:

:- use_module(library(lambda)). 

count_occurrences(L, R) :- 
    foldl(\X^Y^Z^(member([X,N], Y) 
      -> N1 is N+1, 
      select([X,N], Y, [X,N1], Z) 
      ; Z = [[X,1] | Y]), 
      L, [], R). 

Answer 4

Вы получили ответы. Prolog - это язык, который часто предлагает несколько «правильных» способов решения проблемы. Из вашего ответа неясно, настаиваете ли вы на каком-либо порядке в своих ответах. Таким образом, игнорируя приказ, один из способов сделать это будет:

1. Сортировка списка, используя стабильную сортировку (тот, который не падает дубликатов)
2. Нанести кодирование длин серий на отсортированном списке

Главным достоинством этого подхода является то, что он деконструирует вашу проблему до двух четко определенных (и решенных) под-проблем.

Первый легко: msort(List, Sorted)

Второй один немного сложнее, но по-прежнему прямо вперед, если вы хотите, чтобы предикат работать только в одну сторону, то есть, список -> Кодировка. Одним из возможных вариантов (довольно явный):

list_to_rle([], []). 
list_to_rle([X|Xs], RLE) :- 
    list_to_rle_1(Xs, [[X, 1]], RLE). 

list_to_rle_1([], RLE, RLE). 
list_to_rle_1([X|Xs], [[Y, N]|Rest], RLE) :- 
    ( dif(X, Y) 
    -> list_to_rle_1(Xs, [[X, 1],[Y, N]|Rest], RLE) 
    ; succ(N, N1), 
     list_to_rle_1(Xs, [[X, N1]|Rest], RLE) 
    ). 

Так что теперь, с верхнего уровня:

?- msort([a,b,c,a,b,c,d], Sorted), list_to_rle(Sorted, RLE). 
Sorted = [a, a, b, b, c, c, d], 
RLE = [[d, 1], [c, 2], [b, 2], [a, 2]]. 

На стороне записки, это почти всегда лучше предпочесть «пары», как и в X-N, вместо списков с двумя элементами точно, как в [X, N]. Кроме того, вы должны сохранить первоначальный порядок элементов в списке, если вы хотите быть верным. От this answer:

rle([], []). 
rle([First|Rest],Encoded):- 
    rle_1(Rest, First, 1, Encoded).    

rle_1([], Last, N, [Last-N]). 
rle_1([H|T], Prev, N, Encoded) :- 
    ( dif(H, Prev) 
    -> Encoded = [Prev-N|Rest], 
     rle_1(T, H, 1, Rest) 
    ; succ(N, N1), 
     rle_1(T, H, N1, Encoded) 
    ). 

Почему это лучше?

• мы избавились от 4-х пара ненужных скобок в коде

• мы избавились от беспорядка в отчётном растворе

• мы избавились от всего много ненужных вложенных терминов: сравните .(a, .(1, [])) с -(a, 1)

• Мы сделали программу более понятной для читателя (это обычный способ представления пар в Prolog)

С верхнего уровня:

?- msort([a,b,c,a,b,c,d], Sorted), rle(Sorted, RLE). 
Sorted = [a, a, b, b, c, c, d], 
RLE = [a-2, b-2, c-2, d-1]. 

Представленных длинами кодера очень четко в своем определении, что имеет, конечно, свои плюсы и минусы. См. this answer для более сжатого способа сделать это.

Answer 5

рафинирования joel76 answer:

count_occurrences(L, R) :- 
    foldl(\X^Y^Z^(select([X,N], Y, [X,N1], Z) 
      -> N1 is N+1 
      ; Z = [[X,1] | Y]), 
      L, [], R). 

Answer 6

Следует отметить, что до сих пор все предложения имеют трудности со списками, которые содержат также переменные. Подумайте об этом случае:

?- count_occurrences([a,X], D). 

Должно быть два разных ответа.

X = a, D = [a-2] ; 
    dif(X, a), D = [a-1,X-1]. 

Первый ответ означает: список [a,a] содержит a дважды, и, таким образом, D = [a-2]. Второй ответ охватывает все термины X, которые отличаются от a, для них у нас есть одно вхождение a и одно появление этого другого термина. Обратите внимание, что этот второй ответ включает бесконечность возможных решений, включая X = b или X = c или что бы вы ни пожелали.

И если реализация неспособна произвести эти ответы, ошибка создания экземпляра должна защитить программиста от дальнейшего повреждения. Что-то вдоль:

count_occurrences(Xs, D) :- 
    (ground(Xs) -> true ; throw(error(instantiation_error,_))), 
    ... . 

В идеале, предикат Пролога определяется как чистое отношение, like this one. Но часто чистые определения довольно неэффективны.

Настоящая версия является чистой и эффективной. Эффективен в том смысле, что он не оставляет открытых лишних точек выбора. Я выбрал определение @ dasblinkenlight как источник вдохновения.

В идеале такие определения используют некоторую форму if-then-else. Однако традиционная (;)/2 написана

(If_0 -> Then_0 ; Else_0) 

является по своей сути не-монотонная конструкция. Я буду использовать монотонный аналог

if_(If_1, Then_0, Else_0) 

вместо этого. Основное различие - это условие. Традиционные конструкции управления полагаются на успех или неудачу If_0, который разрушает всю чистоту. Если вы напишете (X = Y -> Then_0 ; Else_0), переменные X и Y являются унифицированными и на тот момент времени принимается окончательное решение о том, следует ли идти за Then_0 или Else_0. Что, если переменные недостаточно созданы? Ну, тогда нам не повезло и получить какой-то случайный результат, настаивая только на Then_0.

Сравните это с if_(If_1, Then_0, Else_0). Здесь первым аргументом должна быть какая-то цель, которая описала бы в своем последнем аргументе, является ли случай Then_0 или Else_0. И если цель не определена, она может выбрать для обоих.

count_occurrences(Xs, D) :- 
    foldl(el_dict, Xs, [], D). 

el_dict(K, [], [K-1]). 
el_dict(K, [KV0|KVs0], [KV|KVs]) :- 
    KV0 = K0-V0, 
    if_(K = K0, 
     (KV = K-V1, V1 is V0+1, KVs0 = KVs), 
     (KV = KV0, el_dict(K, KVs0, KVs))). 

=(X, Y, R) :- 
    equal_truth(X, Y, R). 

Это определение требует следующих вспомогательных определений: if_/3, equal_truth/3, foldl/4.