最低在序言中列出的名單

Question

你好，我有一個這樣的名單：名單

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

列表... 我想找到內部列表 在這種情況下，我想回到的最小數量d = 2且L = [A，b，d]

我試圖此代碼：

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 
    ). 

在Prolog，可以簡化這一點了，因爲Prolog有一個更通用的術語比較運算，@< ，@>等，這是比較複雜的術語聰明。例如，[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]。

然後，我們根據內置謂詞keysort/2和 member/2定義minway_/3。使用SICStus序言4.3.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,_)) 
    ). 

樣品查詢：

| ?- 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