Подсписки уникальной длины

Question

Я пишу программу, которая проверяет, содержит ли список подсписки уникальной длины:

например, diffLengthLists([[2],[3,4]]) должен возвращать true, тогда как diffLengthLists([[3],[4]]) должен возвращать false.

Вотмой код:

diffLengthLists(A):- is_list(A),
                     diffLength(A,[_]).

diffLength([A|B], [C|D]):- length(A, C), 
                           diffLength(B, D), 
                           unique([C|D]).

unique([A|B]):- \+member(A, B), unique(B).
unique([]).

Поэтому я в основном добавляю длину каждого подсписка в другой список, [C|D], а затем проверяю, являются ли элементы в [C|D] уникальными.

Однако моя программа работает не так, как ожидалось.Что я здесь не так делаю?Есть ли лучший (более четкий) способ написания этой программы?

Спасибо за вашу помощь заранее!

РЕДАКТИРОВАТЬ: я протестировал предикаты помощника, и проблема, кажется, возникает из diffLengthОднако я не понимаю, почему это не работает.Я добавил unique([]). в код, и теперь этот предикат работает правильно.

Answer 1

diffLengthLists(Xss) :-
   maplist(length,Xss,Ls),
   alldifferent(Ls).

alldifferent([]).
alldifferent([E|Es]) :-
   maplist(=\=(E),Es),
   alldifferent(Es).

Это решение прекращается, если известны все длины всех списков.Вот о чем твоя домашняя работа.

Но она не заканчивается на diffLengthLists([[],[],_]), когда она должна потерпеть неудачу.Реализовать реализацию, которая могла бы завершиться во всех возможных случаях, очень сложно.

В SWI предопределено следующее, поэтому нет необходимости его определять.Но другим системам это нужно:

maplist(_Cont_1, []).
maplist( Cont_1, [A|As]) :-
   call(Cont_1, A),
   maplist(Cont_1, As).

Для maplist/3 см. этот пост .

А вот еще одно решение, которое заканчивается для указанной цели:

diffLengthLists([]).
diffLengthLists([L|Ls]) :-
   maplist(diffLength(L),Ls),
   diffLengthLists(Ls).

diffLength([], [_|_]).
diffLength([_|_], []).
diffLength([_|Es], [_|Fs]) :-
   diffLength(Es, Fs).

Найдите случай, когда этот предикат не заканчивается, когда он должен потерпеть неудачу!

Answer 2

Теперь у вас есть время, чтобы пережевать его и найти решение, вот еще один способ напасть на него.

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

'uniqll имеет значение true, если длина подсписка не является членом списка, содержащего длины для остальной части списка'

uniqll([],[]).

uniqll([H|T], [LenH|LensSoFar]) :-
  uniqll(T, LensSoFar),
  length(H, LenH),
  not(member(LenH, LensSoFar)).

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

[trace] 10 ?-  uniqll([[2,3],[4,5]],X).
   Call: (6) uniqll([[2, 3], [4, 5]], _G1276) ? creep
   Call: (7) uniqll([[4, 5]], _G1360) ? creep
   Call: (8) uniqll([], _G1363) ? creep
   Exit: (8) uniqll([], []) ? creep
   Call: (8) length([4, 5], _G1362) ? creep
   Exit: (8) length([4, 5], 2) ? creep
^  Call: (8) not(member(2, [])) ? creep
^  Exit: (8) not(user:member(2, [])) ? creep
   Exit: (7) uniqll([[4, 5]], [2]) ? creep
   Call: (7) length([2, 3], _G1359) ? creep
   Exit: (7) length([2, 3], 2) ? creep
^  Call: (7) not(member(2, [2])) ? creep
^  Fail: (7) not(user:member(2, [2])) ? creep
   Fail: (6) uniqll([[2, 3], [4, 5]], _G1276) ? creep
false.

И для успеха:

[trace] 11 ?-  uniqll([[2,3],[4]],X).         
   Call: (6) uniqll([[2, 3], [4]], _G1479) ? creep
   Call: (7) uniqll([[4]], _G1560) ? creep
   Call: (8) uniqll([], _G1563) ? creep
   Exit: (8) uniqll([], []) ? creep
   Call: (8) length([4], _G1562) ? creep
   Exit: (8) length([4], 1) ? creep
^  Call: (8) not(member(1, [])) ? creep
^  Exit: (8) not(user:member(1, [])) ? creep
   Exit: (7) uniqll([[4]], [1]) ? creep
   Call: (7) length([2, 3], _G1559) ? creep
   Exit: (7) length([2, 3], 2) ? creep
^  Call: (7) not(member(2, [1])) ? creep
^  Exit: (7) not(user:member(2, [1])) ? creep
   Exit: (6) uniqll([[2, 3], [4]], [2, 1]) ? creep
X = [2, 1].

Как побочный эффект, список, когда True, список в конце - это список длин.

Пролог просто чертовски крут и элегантен.