минимум в списке списков в прологе

Question

Привет У меня есть список, как это:

[[3,[a,b,c,d]],[2,[a,b,d]],[5,[d,e,f]]] 

список списков ... я хочу найти минимальное количество на внутреннем списке в этом случае я хочу, чтобы вернуться D = 2 и L = [а, б, г]

я попробовал этот код:

minway([[N|L]],N,L). 
minway([[M|L1]|L2],D,_):- M<D, minway(L2,M,L1). 
minway([[M|_]|L2],D,L):- M>=D, minway(L2,D,L). 

, но я получил сообщение об ошибке:

</2: Arguments are not sufficiently instantiated 
    Exception: (8) minway([[3,[a,b,c,d]],[2,[a,b,d]],[5,[d,e,f]]], _G7777, _G7778) ? 
    creep 

для этого выполнения предложения:

minway([[3,[a,b,c,d]],[2,[a,b,d]],[5,[d,e,f]]],D,L). 

результат нужно быть:

D=2. 
L=[a,b,d]. 

где моя проблема? и как его исправить?

tnx много

Answer 1

Есть пара фундаментальных проблем.

В вашей задаче находится ваше представление о списке. Ваши предикаты, по-видимому, предполагают, что, например, [3, [a,b,c]] представлен как [3 | [a,b,c]], но это не так. Список [3 | [a,b,c]] - это список с 3 в качестве главы, а [a,b,c] как остальная часть списка или хвост. Другими словами, [3 | [a,b,c]] - [3, a, b, c].

И, таким образом, ваш базовый случай будет:

minway([[N,L]], N, L). 

Вторая проблема в ваших других предикатных статей. Начальная точка для D. Другими словами, ему никогда не давали значения, поэтому вы получаете ошибку создания. Вы не можете сравнить N > D, если одна из переменных не имеет значения.

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

minway([[N,L]|T], D, R) :- 
    minway(T, N, L, D, R). 

minway([], D, R, D, R).   % At the end, so D, R is the answer 
minway([[N,L]|T], Dm, Rm, D, R) :- 
    ( N < Dm 
    -> minway(T, N, L, D, R)  % N, L are new candidates if N < Dm 
    ; minway(T, N, Dm, Rm, D, R) % Dm, Rm are still best candidate 
    ). 

В Прологе, вы можете упростить это немного, поскольку Пролог имеет более общий термин оператор сравнения, @< , @> и т. Д., Которые умеют сравнивать более сложные термины. Например, значение [2, [d,e,f]] @< [3, [a,b,c]] верно, так как значение 2 < 3. Затем мы можем написать:

minway([H|T], D, R) :- 
    minway(T, H, D, R). 

minway([], [D, R], D, R). 
minway([H|T], M, D, R) :- 
    ( H @< M 
    -> minway(T, H, D, R) 
    ; minway(T, M, D, R) 
    ). 

Answer 2

Во-первых, мы переходим к лучшему представлению данных: Вместо [3,[a,b,c,d]] мы используем 3-[a,b,c,d].

Затем мы определяем minway_/3 на основе встроенных предикатов keysort/2 и member/2.

 
minway_(Lss, N, Ls) :- 
    ( ground (Lss)    % (actually, only the keys must be ground) 
    ->keysort (Lss, Ess), 
     Ess  = [N-_|_], 
     member (N-Ls, Ess) 
    ; throw (error (instantiation_error,_)) 
    ). 

Пример запроса с использованием SICStus Пролог 4.3.2:

| ?- minway_([3-[a,b,c,d],2-[a,b,d],5-[d,e,f],2-[x,t,y]], N, Ls). 
N = 2, Ls = [a,b,d] ? ; 
N = 2, Ls = [x,t,y] ? ; 
no