2013-05-29 61 views
0

這應該是一個簡單的解決方法,但我似乎無法解決這個問題,並且令人沮喪。我編寫了一個程序,用於計算或驗證兩個列表是相關的,因爲第二個列表的元素都從第一個列表的元素中遞增了一個。這適用於給出兩個列表時,但在需要計算列表時不適用。Prolog程序將不會計算可變的答案?

代碼如下:

inc([], []). 
inc([X|XS],[Y|YS]) :- 
    Y =:= X+1, 
    inc(XS,YS). 
ERROR: =:=/2: Arguments are not sufficiently instantiated 

任何幫助將不勝感激!

+0

': - Y是X + 1,...' – CapelliC

+0

@CapelliC只能解決一個方向。 –

+0

@DanielLyons:我知道,只是建議(恕我直言)更簡單的更正。 BTW succ/2比算術慢兩倍。 – CapelliC

回答

0
inc([],[]). 
inc([X|XS],[Y|YS]) :- 
    nonvar(X), 
    Z is X + 1, 
    Y = Z, 
    inc(XS,YS), !. 
inc([X|XS],[Y|YS]) :- 
    nonvar(Y), 
    Z is Y - 1, 
    X = Z, 
    inc(XS,YS), !. 

在這裏,我們需要得到一個真正的加法計算,然後嘗試使用=實例化。謂詞不得不被分割來處理X未被實例化的情況,而Y則不是。每一個末端的!都是爲了防止它在兩條相似的路徑中找到一條路徑後嘗試更多的解決方案。

+0

非常感謝!我已經嘗試過分配一個單獨的變量進行比較,但由於某些原因,它不能以我想要的方式工作,因爲我的=:=比較器。這是否意味着不可能找到一個可以評估左右手錶達的謂詞? –

+0

如果兩個參數都是變量(例如:'? - inc(X,Y).'),則這不起作用。考慮將CLP(FD)約束用於更一般的解決方案。 – mat

+0

@Daniel。感謝您對我糟糕的解釋提出的意見。我刪除了它,以免進一步混淆。我推測沒有給出適當的想法,對此我表示歉意。然而,我認爲把這個描述爲我在這些有限的情況下「......關於Prolog的一些非常奇怪的想法」是不公平的。此外,如果根據你明顯更大的經驗提供一個更正的解釋,那麼對於我(和我)來說,這將會更有好處。 – lurker

1

你的問題本質上是=:=/2是測試,而不是建立綁定,但is/2仍然沒有真正做你想做的。例如,儘管2 is 1 + 1爲真,2 is X+1將不會導致X被綁定到1,因爲is/2預計在左側只有一個變量或值,而在右側有一個表達式,並且它不像「關係」那樣運行Prolog的其餘部分。如果你想要這樣的算術,你應該檢查出clpfd;考慮到它增加的複雜性是對事情是如何發生的一個很好的解釋。

幸運的是,您不需要全部算術來解決您的問題。該succ/2內建將不正是你所需要的,和獎金,你會得到一個在線解決方案:

inc(X, Y) :- maplist(succ, X, Y). 

在使用中:

?- inc([1,2,3], [2,3,4]). 
true. 

?- inc([1,2,3], X). 
X = [2, 3, 4]. 

?- inc(X, [1,2,3]). 
X = [0, 1, 2]. 

如果使用succ/2代替=:=/2你的代碼也能正常工作:

inc([], []). 
inc([X|XS],[Y|YS]) :- 
    succ(X, Y), 
    inc(XS,YS). 

這一定是您懷疑的「簡單修復」。 :)

我不確定@mbratch指的是關於一個謂詞有「太多變量」。我懷疑這是對Prolog的一個誤解,也許是其他語言的功能可以返回一個值或某物的擱置。這裏沒有技術限制;謂詞可以採取儘可能多的理由或非理性的論點,並儘可能多地綁定你想要的;限制因素是你的創造力。

同樣,我不認爲「不對稱」在這裏是一個有意義的概念。定義僅具有單一實例化模式的謂詞是非常正常的,但是對於實例化而言很靈活的謂詞也是正常的和可取的,因爲謂詞可以提前知道未來可能需要什麼用途。您可能會認爲,破壞信息的實例化模式可能會排除反例化模式,但實際上,您經常可以將其轉化爲生成器。

舉一個陳腐的例子,append/3的名字似乎暗示着這個模式:

?- append([1,2], [3,4], X). 
X = [1,2,3,4] 

這是一個非常好的使用,但這樣是:

?- append(X, Y, [1,2,3,4]). 

這是一個不確定性實例化模式並將產生五種解決方案:

X = [], Y = [1,2,3,4] 
X = [1], Y = [2,3,4] 
X = [1,2], Y = [3,4] 
X = [1,2,3], Y = [4] 
X = [1,2,3,4], Y = [] 

這似乎站在co對一些@ mbratch的想法進行了部署,但在append/3的通常定義中沒有對地面/非地面進行明確測試,因爲它不是必需的,同樣對於第二種調用模式,您從一個輸入中獲得兩個「返回值」。 SWI source

append([], L, L). 
append([H|T], L, [H|R]) :- 
    append(T, L, R). 

編輯:負數。我忘記succ/2只在正整數上定義。我們可以申請@ mbratch的技術,仍然可以得到具有所需性能的漂亮的解決方案:

isucc(X, Y) :- var(X), X is Y-1. 
isucc(X, Y) :- Y is X+1. 

inc(X, Y) :- maplist(isucc, X, Y). 

在行動:

?- inc(X, [-1,2]). 
X = [-2, 1] ; 
false. 

編輯:使用CLP(FD)(通過@mat):

fdsucc(X,Y) :- Y #= X + 1. 
inc(X, Y) :- maplist(fdsucc, X, Y). 

此產生,即使是最普通的查詢:

?- inc(X, Y). 
X = Y, Y = [] ; 
X = [_G467], 
Y = [_G476], 
_G467+1#=_G476 ; 
X = [_G610, _G613], 
Y = [_G622, _G625], 
_G610+1#=_G622, 
_G613+1#=_G625 ; 
X = [_G753, _G756, _G759], 
Y = [_G768, _G771, _G774], 
_G753+1#=_G768, 
_G756+1#=_G771, 
_G759+1#=_G774 
... 

這個問題的實用性值得懷疑,但可能是因爲您使用了clp(fd),您最終會施加其他約束並獲得一些有用的結果。

+0

您的代碼不適用於最常用的查詢:'? - inc(X,Y).'。它確實如果你使用CLP(FD)。 – mat

+0

我嘗試了''maplist'和'succ'的解決方案'inc(X,[0,3])',並且失敗了。但是,我提供的解決方案不使用'succ'或'maplist'工作併產生'X = [-1,2]'。 – lurker

+0

@mbratch查看編輯:) –