程式語言簡介/列表成本模型
< 程式語言簡介
列表可能是函數語言程式設計語言中最著名的資料結構。函式式列表為使用者提供了兩個眾所周知的操作：頭和尾。前者返回列表的第一個元素。後者返回對列表尾部的引用，即包含原始序列中所有元素的子列表，但第一個元素除外。僅使用這兩個操作，我們無法進行隨機訪問，即無法以相同的時間成本讀取列表中的任何元素。為了說明這一點，讓我們考慮一下下面這個謂詞的實現，它允許我們連線列表
@([], L, L).
@([H|T], L, [H|Tt]) :- @(T, L, Tt).
這個謂詞由兩個子句組成。第一個顯然是 O(1)，因為它總是為真。另一方面，第二個涉及遞迴。對於第一個列表上的每個元素，謂詞將被遞迴呼叫一次。每個遞迴呼叫執行 O(1) 量的計算。因此，這個謂詞對於第一個列表的元素數量是線性的。請注意，我們談論的是元素的數量，而不是元素的大小。換句話說，無論第一個列表包含什麼，謂詞都應該在相同的時間內執行。再舉一個例子，這次讓我們分析一個對反轉列表的謂詞的簡單實現
reverse([],[]).
reverse([Head|Tail],Rev) :- reverse(Tail,TailRev), @(TailRev,[Head],Rev).
有人可能會認為這個謂詞對我們要反轉的列表的大小是線性的：第一個子句在 O(1) 內執行，第二個子句遞迴呼叫一次 reverse。但是，每次呼叫 reverse 的成本並非 O(1)。除了最後一次呼叫之外，每次呼叫都使用了我們的 append，我們已經知道它是 O(N)，N 是第一個列表的元素數量。因此，我們目前實現的 reverse 對列表元素的數量是二次的。鑑於在 C、Python 或 Java 中，以線性時間反轉陣列是如此容易，我們可能會想知道是否可以在函式式列表的成本模型上實現相同的複雜度。的確，這是可能的，我們很快就會證明這一點。現在，我們將把這個問題放到我們的堆疊中。