可持久化陣列 Persistent Array 始

回顧

• get(index): 回傳索引為 index 的元素，其中 $\text{index} \in \left [0, n-1 \right ]$
• set(index, value): 修改 index 上的元素
• pushBack(value): 陣列尾端後接一個新的元素
• popBack(): 移除陣列尾端的最後一個元素

二元樹 (Binary Tree)

2. $\textit{new}S = (p_1, p_2, \cdots, p_m)^\triangleleft$ 反轉成
$S = ()^\triangleleft$$\textit{aux}S = (p_1, p_2, \cdots, p_m)^\triangleright 3. \textit{aux}B = (q_{m+2}, q_{m+2}, \cdots, q_{3m+k})^\triangleleft 反轉成 \textit{aux}B = ()^\triangleleft$$\textit{new}B = (q_{m+2}, q_{m+2}, \cdots, q_{3m+k})^\triangleright$
4. $B = (q_1, q_2, \cdots, q_{m+1})^\triangleright$ 放入為
$\textit{new}S = (q_1, q_2, \cdots, q_{m+1})^\triangleleft$$B = ()^\triangleright 5. \textit{aux}S = (p_1, p_2, \cdots, p_m)^\triangleright 也放入為 \textit{new}S = (p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_{m+1})^\triangleleft$$\textit{aux}S = ()^\triangleright$

隊列操作說明

• pushFront/pushBack計算完的雙向隊列大小小於等於 4 時，採用攤平的方式操作，強制不進入上述轉移條件。反之，直接在相應的堆疊上操作。
• popFront/popBack計算完的雙向隊列大小小於 4 時，採用攤平的方式操作，強制不進入上述轉移條件。反之，直接在相應的堆疊上操作。

可持久化隊列 Persistent Queue 續

預先評估隊列 (Pre-Evaluation)

• SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

初階定義

\begin{aligned} \left [ \; \right ]_{q} &= \left \langle \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle L, \; R \right \rangle | &= |L| + |R| \\ \\ \textit{insert} \; (e, \left \langle L, \; R \right \rangle) &= \textit{makeq} \; (L, \; e : R) \\ \\ \textit{remove} \left \langle L, \; R \right \rangle &= \left \langle \text{hd} \; L, \textit{makeq} \; (\text{tl} \; L, \; R) \right \rangle \\ \\ \textit{makeq} \left \langle L, \; R \right \rangle &= \left \langle L, \; R \right \rangle &\{ |R| \le |L|\} \\ &= \left \langle \textit{rot}(L, R, \left [ \; \right ]), \left [ \; \right ] \right \rangle &\{ |R| = |L| + 1\}\\ \\ \textit{rot}(L, R, A) &= \text{hd} \; R : A & \{ |L| = 0 \} \\ &= \text{hd} \; L : \textit{rot}(\text{tl} \; L, \text{tl} \; R, \text{hd} \; R : A) & \{ |L| > 0 \} \end{aligned}

預先評估隊列 (Pre-Evaluation)

• SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

可持久化堆疊 操作 Persistent Stack Operators

串接 Append

\begin{aligned} \left [ \; \right ]_{\textit{append}} &= \left \langle \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle T, \; B \right \rangle | &= |T| + |B| \\ \\ \textit{push} \; (\textit{e}, \left \langle T, \; B \right \rangle) &= \left \langle e : T, \; B \right \rangle \\ \\ \textit{pop} \; (\left \langle T, \; B \right \rangle) &= \left \langle \text{hd} \; T, \left \langle \text{tl} \; T, \; B \right \rangle \right \rangle & \{ |T| > 0 \} \\ &= \left \langle \text{hd} \; B, \text{tl} \; B \right \rangle & \{ |T| = 0 \} \end{aligned}

提取 Take

\begin{aligned} \left [ \; \right ]_{\textit{take}} &= \left \langle 0, X \right \rangle \\ \\ |\left \langle n, X \right \rangle | &= n \\ \\ \textit{push} \; (\textit{e}, \left \langle n, X \right \rangle) &= \text{Append}(e,\; \left \langle n, X \right \rangle) \\ \\ \textit{pop} \; (\left \langle n, X \right \rangle) &= \left [ \; \right ] & \{ n = 1 \} \\ &= \left \langle \text{hd} \; X, \left \langle n-1, \text{tl} \; X \right \rangle \right \rangle & \{ n > 1 \} \end{aligned}

移除 Drop

\begin{aligned} \text{Drop} \; (n, X) &= X & \{ n = 0 \} \\ &= \text{Drop} \; (n-1, X) & \{ n > 1\} \end{aligned}

反轉 Rev

\begin{aligned} \text{Rev} \; (X) &= \text{Rev}'(X, \left [ \; \right ]) & \\ \\ \text{Rev}'(X, A) &= A & \{ |X| = 0\} \\ &= \text{Rev}' \; (\text{tl} \; X, \text{hd} \; X : A) & \{ |X| > 0\} \end{aligned}

參考資料

• SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

來點題目 《記憶中的堆疊》

題目描述

• 0 v: 退回版本 v
• 1 x: 在當前堆疊，push x 到堆頂
• 2: 印出當前堆疊狀態

可持久化堆疊 Persistent Stack

起因

• 惰性求值 (Lazy Evaluation)：
每一個惰性求值是需要的時候再計算，然而有些歷史代碼並不是這麼回事，導致一部分函數回傳整個串列，因此消耗了至少為 $\mathcal{O}(n)$ 的時間，而非函數式所需要的 $\mathcal{O}(1)$。如果一個函數只針對前 10 個數值感興趣，大部分的資料都會被捨棄掉，在未來使用這些函數接口時，都還要去檢查每一個相關實作是否為真惰性，而非假性惰性。請參閱 Java Stream 串流實作細節。

• 不可變物件 (Immutable Object)：
對於某些中間表達式，如檔案系統路徑。若要列出一個資料夾下的所有檔案路徑，在上述的惰性求值中，樸素的實作將會把路徑之間的重複不斷複製。正如同經典的字串問題，每串接一個字串，必然會複製一份，倘若複製的順序相反，時間複雜度將從 $\mathcal{O}(n)$ 變成 $\mathcal{O}(n^2)$

堆疊定義

• $\textit{push} \; (\textit{value})$：將一個元素 $\textit{value}$ 放置到堆頂
• $\textit{pop} \; ()$：將堆頂元素移除

可持久化堆疊定義

• $[\;]_{\textit{stack}} = \left \langle [\;] \right \rangle$
• $|\left \langle A \right \rangle| = |\left \langle \text{hd} \; A \right \rangle| + |\left \langle \text{tl} \; A \right \rangle|$
• $\textit{push} \; (\textit{e}, A) = \left \langle e : A \right \rangle$
• $\textit{pop} \; (A) = \left \langle \text{hd} \; A, \left \langle \text{tl} \; A \right \rangle \right \rangle$

• $\text{hd}$ 為堆疊的首元素。另一個使用術語為 $\textit{car}$
• $\text{tl}$ 為剔除首元素之後的結果。另一個使用術語為 $\textit{cdr}$。從堆疊來看，即為回傳指向前一個節點的位置。
• $:$ 為串接操作。