接續前一篇 《可持久化隊列 Persistent Queue 序》，開始搬運論文的內容，就當作個翻譯吧
預先評估隊列 (Pre-Evaluation)
- SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995
初階定義
定義：隊列 $Q = \left \langle L, \; R \right \rangle$ 且滿足 $|R| \le |L|$
$$\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}$$看到這一大串的語法樹，就要開始構思曾經在編譯器學到的 LL Parser，操作完之後仍然是一個隊列，為了找到隊列的頭，我們要去完成 LL(1) 的計算，使用向前探查 (lookahead) 問第一個元素為何。
不幸地，上述語法的 $\textit{remove}$ 為 $\mathcal{O}(\log n)$，其他操作為 $\mathcal{O}(1)$。原因很簡單，當我們不斷地 $\textit{insert}$ 進去時，根據語法樹會不斷地構造長度為 $1,\; 2,\; 4, \cdots, 2^n$ 長度的 $\textit{rot}$ 堆疊，這時候若要看第一個元素為何，運算量就等同於遞迴深度。
縱使我們在每個堆疊建構時，預先計算出 front() 的結果，那麼在 pop() 回傳的時候，仍需要付出代價，而我們更不能在建構子中預先計算出 pop() ，這違反遞迴定義，更會落入退化成線性操作，而不是想要的惰性操作。當瞭解上述的問題後，接下來要想辦法把 $\textit{remove}$ 變成 $\mathcal{O}(1)$ 操作。
進階定義
定義：隊列 $Q = \left \langle L, \; R, \; \hat{L} \right \rangle$ 且滿足 $|R| \le |L| \wedge |\hat{L}| = |L| - |R|$
$$\begin{aligned} \left [ \; \right ]_{q} &= \left \langle \left [ \; \right ], \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle L, \; R, \; \hat{L} \right \rangle | &= |L| + |R| \\ \\ \textit{insert} \; (e, \left \langle L, \; R, \; \hat{L} \right \rangle) &= \textit{makeq} \; (L, \; e : R, \hat{L}) \\ \\ \textit{remove} \left \langle L, \; R, \; \hat{L} \right \rangle &= \left \langle \text{hd} \; L, \textit{makeq} \; (\text{tl} \; L, \; R, \hat{L}) \right \rangle \\ \\ \textit{makeq} \left \langle L, \; R, \; \hat{L} \right \rangle &= \left \langle L, \; R, \; \text{tl} \; \hat{L} \right \rangle &\{ |\hat{L}| > 0\} \\ &= \left \langle L', \left [ \; \right ], L' \right \rangle, \; \text{let} \; L' = \textit{rot}(L, R, \left [ \; \right]) &\{ |\hat{L}| = 0\}\\ \\ \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}$$透過額外的 $\hat{L}$，避開了 LL Parser 和 lookahead 造成的遞迴定義，如此一來每一個操作複雜度皆為 $\mathcal{O}(1)$。其概念也很簡單，為了維持條件 $|R| \le |L|$，我們將 $\hat{L}$ 定義為其差值，為即將地部分 $R$ 反轉到變成 $L$ 計數做準備。
特別注意到，在 $\text{makeq}$ 的時候，同步移除掉了一部分的 $\hat{L}$，而在長度 $|\hat{L}| = 0$ 觸發反轉。實作上，可以當作一個長度數值去看待，而在可持久化概念上，它們實際上共享同一塊內存，所以也就沒有太大的差別。
概念與前一篇的 Realtime Queue 構造方式類同。只不過，我們預先將答案放置於 $\textit{rot}$ 堆疊定義中的 $A$ 中，而重複使用了 $\hat{L}$ 找到完成時刻。