合併備用元件從兩個列表中的Prolog

Question

我需要編寫一個Prolog的謂詞mergealt(X,Y,Z)該成功如果列表Z是備用元件從列表X合併和Y.

輸入和輸出會喜歡下面：

?- mergealt([1,2,3,4],[6,7,8],Z). 
Z = [1, 7, 3] . 
?- mergealt([1,2,3,4],[6,7,8,9],Z). 
Z = [1, 7, 3, 9] . 
?- mergealt([1,2,3,4],[6,7,8,9,10],Z). 
Z = [1, 7, 3, 9] . 

我不太瞭解遞歸。我該如何開始解決這個問題？

Answer 1

序言可以被視爲聲明性語言的'旗手'。 所以儘量描述您的問題，自上而下：如果在十 這一事實凸顯了遞歸終止的情況下沒有任何元素

mergealt(X, Y, Z) :- 
    'take first element from X and put it in Z', 
    'discard first element from Y', 
    'mergealt rest-of-X and rest-of-Y, but exchange them'. 

第一步無法實現。原來，Prolog的沒用過if then else，而不是替代品表述爲不同的規則：

mergealt([], _Y, []). 

在這裏你可以看到pattern matching的第一個參數是區分替代的關鍵，和內容，Z得到勢必到空的清單。 Y未使用，所以它被標記爲anonymus佔位符，只是爲了避免警告。

然後這個更簡單的情況表明我們應該使用模式匹配來完成那些詳細的描述。看看你能不能用這些準則完成該過程：

mergealt([X|Xs], Y, [X|Zs]) :- 
    % take first element from X and put it in Z : done in the head 
    % discard first element from Y : see below 
    % mergealt rest-of-X and rest-of-Y, but exchange them'. : make your recursive call 

discard_first_element([_|Rest], Rest). 
% why is this necessary? do you see where it fails if we don't specify this case? 
discard_first_element([], []). 

Answer 2

• 請注意，結果始終始於第一個列表的第一個元素。
• 這意味着，如果第一個列表是空的，您馬上就知道答案。
• 另請注意，如果它不是空的，我們已經知道結果的第一項，所以我們需要使用mergealt來計算其餘的。但是「其餘」將第二個列表中的第二個項目作爲結果的第一個項目，正如我們上面所說的那樣，這意味着調用mergealt來計算它將不得不成爲第一個項目的第一個項目列表（是的，這是棘手的部分）。