Тестирование, если все списки в списке имеют одинаковую длину

Question

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

?- equalLists([[a,b,c],[1,2,3],[d,4,e],[5,6]]).
false

Поэтому я пытаюсь проверить каждый список, чтобы увидеть, имеет ли он ту же длину, что и предыдущий список. Может ли кто-нибудь указать мне правильное направление?

Answer 1

Сначала мы определим некоторые стандартные отношения более высокого порядка, map и fold. Для этого требуется встроенный предикат call. Можно просто определить maxlist и т. Д. Как одноразовые, но это должно быть более ярким.

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

maplist(_, [], []).
maplist(P, [X | Y], [A | B]) :-
  call(P, X, A),
  maplist(P, Y, B).

max(A, B, M) :- A <  B, M = B.
max(A, B, M) :- A >= B, M = A.

min(A, B, M) :- B <  A, M = B.
min(A, B, M) :- B >= A, M = A.

fold(_, [X], X).
fold(P, [X, Y], R) :- call(P, X, Y, R).
fold(P, [X, Y | Z], R) :-
  fold(P, [Y | Z], NR),
  call(P, NR, X, R).

maxlist(L, M) :- fold(max, L, M).

minlist(L, M) :- fold(min, L, M).

equallists(L) :-
  maplist(length, L, Lengths),
  maxlist(Lengths, Max),
  minlist(Lengths, Min),
  Max == Min.

Answer 2

@ Решение Петериса излишне сложное.Вы можете сделать это так:

equal_lengths([]).
equal_lengths([[]]).
equal_lengths([[_|_]]).
equal_lengths([X,Y|Rest]) :- 
  length(X, Len), 
  length(Y, Len), 
  equal_lengths([Y|Rest]).

Думайте индуктивно.Я утверждаю, что длина пустого списка и список из одного списка "равны" (нет / только один другой для сравнения).Затем я говорю, если длина первого элемента равна длине второго элемента, при условии, что длина второго элемента и остальных совпадают, мы хороши.

Примечание: мыявно не говорите, что длина X и Y одинакова с некоторым тестом на равенство.Мы позволяем Прологу справиться с этим для нас, просто объявив, что длина X и Y - это Len.Поэтому, если длина Y не объединяется с длиной X, предикат завершится ошибкой.

Поворот процесса

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

unequal_lengths(X) :- unequal_lengths(X, []).

Теперь мы снова начнем с аналогичных базовых случаев:

unequal_lengths([], _).
unequal_lengths([[]], _).
unequal_lengths([[_|_]], _).

Вещистановиться интереснее, когда у нас есть фактический список:

unequal_lengths([X|Rest], Lengths) :-
  length(X, Len),
  \+ member(Len, Lengths),
  unequal_lengths(Rest, [Len|Lengths]).

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

Приложение: неравное с / о

Вдохновленные другими ответами, вы можете реализовать unsqual_lengths в более высоком-порядок моды так:

unequal_lengths(Lists) :-
  findall(Len, (member(X, Lists), length(X, Len)), Lengths),
  forall(select(Len, Lengths, Remaining), \+ member(Len, Remaining)).

Если подумать, это очень близко соответствует формальному логическому выражению проблемы: для каждой длины списка не существует элемента оставшихся длин спискасоответствующий этому.

Answer 3

Следующее блюдо в моем меню: барокко clpfd пролог-сопратин солянка.

:- use_module(library(clpfd)).

samelength_of(N,Xss) :- maplist(length_of__lazy(N),Xss).

length_of__lazy(N,Xs) :-
   N #>= 0,
   (  nonvar(N)
   -> length(Xs,N)
   ;  var(Xs)
   -> when((nonvar(Xs);nonvar(N)), length_of__lazy(N,Xs))
   ;  Xs = []
   -> N = 0
   ;  Xs = [_|Xs0]
   -> N0 + 1 #= N,
      length_of__lazy(N0,Xs0)
   ;  throw(error(type_error(list,Xs),length_of__lazy/2))
   ).

my_indomain(N) :-
   fd_inf(N,I),
   (  N #= I
   ;  N #> I, my_indomain(N)
   ).

Некоторые примеры запросов:

?- Xss = [As,Bs,Cs], <b>As=[]</b>, samelength_of(N,Xss).
N = 0, Xss = [[],[],[]], As = [], Bs = [], Cs = [].

?- Xss = [As,Bs,Cs], samelength_of(N,Xss), <b>As=[]</b>.
N = 0, Xss = [[],[],[]], As = [], Bs = [], Cs = [].

Еще?Хотите попробовать камбалу?

?- samelength_of(N,[As,Bs,Cs]).
N in 0..sup,
when((nonvar(As);nonvar(N)), length_of__lazy(N,As)),
when((nonvar(Bs);nonvar(N)), length_of__lazy(N,Bs)),
when((nonvar(Cs);nonvar(N)), length_of__lazy(N,Cs)).

Камбала не по вкусу? Нет проблем!

?- samelength_of(N,[As,Bs,Cs]), my_indomain(N).
N = 0, As = [],            Bs = [],            Cs = []            ;
N = 1, As = [_A1],         Bs = [_B1],         Cs = [_C1]         ;
N = 2, As = [_A1,_A2],     Bs = [_B1,_B2],     Cs = [_C1,_C2]     ;
N = 3, As = [_A1,_A2,_A3], Bs = [_B1,_B2,_B3], Cs = [_C1,_C2,_C3] ...

Answer 4

Следует второе решение с лучшими свойствами завершения по сравнению с моей первой попыткой.Основная идея заключается в том, что при каждом обходе списка списков мы удаляем по одному элементу из каждого списка.

equal_lengths([]).
equal_lengths([L1| Ls]) :-
    pick(L1, Ls, Rs),
    equal_lengths(Rs).

pick([], Ls, []) :-
    all_empty(Ls).
pick([_| R1], Ls, [R1| Rs]) :-
    pick(Ls, Rs).

pick([], []).
pick([[_|R1]| Ls], Rs) :-
    pick([_|R1], Ls, Rs).

all_empty([]).
all_empty([[]| Rs]) :-
    all_empty(Rs).

Проблемный случай @false, упомянутый в комментарии к моему первому решению, был:

| ?- equal_lengths([_,_,[]]).

true ? ;

no

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

| ?- equal_lengths([L1,L2,[]]).

L1 = []
L2 = [] ? ;

no

Все предыдущие примеры запросов в моем первом решении не создают проблем.В частности, стоит упомянуть один запрос, поскольку он ошибочно предоставил только одно решение вместо генерации решений в предыдущей попытке.Теперь он работает, как и ожидалось:

| ?- equal_lengths([L]).

L = [] ? ;

L = [_] ? ;

L = [_,_] ? ;

L = [_,_,_] ? ;

...

Может кто-нибудь найти пример запроса, приводящий к проблемам с этим решением?

Answer 5

Решение, использующее преимущества индексации по первому аргументу в большинстве систем Prolog, чтобы избежать ложных точек выбора в большинстве (но не во всех) случаях:

equal_lengths([]).
equal_lengths([L1| Ls]) :-
    equal_lengths_aux(Ls, L1).

equal_lengths_aux([], _).
equal_lengths_aux([L2| Ls], L1) :- 
    equal_length(L1, L2), 
    equal_lengths_aux(Ls, L2).

equal_length([], []).
equal_length([_| Tail1], [_| Tail2]) :-
    equal_length(Tail1, Tail2).

Некоторые примеры запросов:

| ?- equal_lengths([]). 

yes
| ?- equal_lengths([[]]).

yes
| ?- equal_lengths([_]). 

yes
| ?- equal_lengths([[],_]).

yes
| ?- equal_lengths([_,[]]).

true ? ;

no
| ?- equal_lengths([L1,L2]).

L1 = []
L2 = [] ? ;

L1 = [_]
L2 = [_] ? ;

L1 = [_,_]
L2 = [_,_] ? 

...
| ?- equal_lengths([[a,b,c],[1,2,3],[d,4,e],[5,6]]).

no
| ?- equal_lengths([[a,b,c],[1,2,3],[d,4,e],[5,6,7],L]).

L = [_,_,_]

yes
| ?- equal_lengths([L1,[_,_],L3]).                      

L1 = [_,_]
L3 = [_,_] ? ;

no

| ?- equal_lengths([L1,[_,_|_],L3]).

L1 = [_,_]
L3 = [_,_] ? ;

L1 = [_,_,_]
L3 = [_,_,_] ? ;

L1 = [_,_,_,_]
L3 = [_,_,_,_] ? ;

...

Мы получаем ложную точку выбора (т. Е. Точку выбора, которая не приводит к решению), когда первый элемент не связан и имеются связанные элементы списка.Если ни один элемент списка не связан с конечным списком , предикат генерирует решения, в которых длина списка продолжает расти, как показано в примерах запросов.

Answer 6

Я перепишу ответ Петериса (+1), используя встроенные SWI-Prolog maplist и совокупность :

equallists(L) :-
  maplist(length, L, Lengths),
  aggregate(max(T), member(T, Lengths), N),
  aggregate(min(T), member(T, Lengths), N).

Готово!

Еще проще, используя lambda (здесь страница документа ), чтобы настроить порядок аргументов:

:- [lambda].

equallists([H|T]) :-
  length(H, N),
  maplist(\L^length(L, N), T).

Variazione sulma (это должно быть минимально):

equallists([H|T]) :-
  length(H, N),
  forall(member(L, T), length(L, N)).

Как заметил @false, когда T не заземлен, тест может не пройти.Возможное исправление:

equallists([H|T]) :-
  length(H, N),
  forall(member(L, T), (nonvar(L), length(L, N))).

forall / 2, которое, я думаю, можно описать как форму цикла, управляемого отказом, может быть легко неправильно использовано.

OTOH, каждая конструкция потока управления в Prologможет быть трудно использовать должным образом, и это, возможно, является основной причиной недостаточной популярности языка.

Answer 7

С правильными инструментами --- мета-предикатом maplist/2 и Пролог лямбда --- все, что нам нужно, это одна строка:

?- Xss = [[1,2],[2,3],<b>[3,4,5]</b>], maplist(<b>N</b>+\Xs^length(Xs,<b>N</b>),Xss).
<b>false</b>.

?- Xss = [[1,2],[2,3],[3,4]],   maplist(<b>N</b>+\Xs^length(Xs,<b>N</b>),Xss).
<b>N</b> = 2.

(+\)/2 помогает нам утверждать, что N является бесплатным, поэтому мы используем тот же N в качестве длины каждого Xs в Xss.

Answer 8

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

equalLengths([]).
equalLengths([Head|Tail]) :-
    length(Head, Length),
    forall(member(List, Tail), length(List, Length)).