假设我想计算一个序列，notfib，递归定义在其最后 9000 个值上，如下所示：
notfib i | i > 9000 = notfib (i - 1500) - notfib (i - 9000) `xor` 75
| otherwise = {- an IV -} ...
9000 是编译时常数;但主要要求是有一个生成器，它可以一直产生值，直到世界末日。当然，在恒定的记忆中。
由于很明显我需要以某种方式将最后 9000 个元素保留在内存中，因此我尝试实现一个环形缓冲区(这似乎是......作业的出色数据结构(位于可变数组之上。现在我的代码充斥着隐藏前奏的合格导入，笨拙的记录取消/打包，注释掉STUArray的，我放弃了失败的范围检查(Not in scope: V.fromList(，因为Data.Vector有多少接口。
我还没有写过单do，但代码已经很臭了！
一些纯洁可以帮助我吗？你会如何解决这个问题？
notfib :: [Int]
notfib = {- first 9000 values -} ++ zipWith (a b -> a - b `xor` 75) (drop (9000 - 1500) notfib) notfib
是通常的伎俩。
也就是说，您可能不想保留对notfib本身的引用，因为它将与您计算的最远值一样大。 如何解决这个问题取决于你想对序列做什么。
为什么要关心函数的操作语义？就把它写在指称语义上，让Haskell的魔力担心性能：
notfibgo _notfib (i :: Integer)
| i > 9000 = _notfib (i - 1500) - _notfib (i - 9000) `xor` 75
| otherwise = i
请注意，此函数几乎与原始函数完全相同，只是以开放递归样式编写(递归调用被替换为仅作为函数参数给出的函数(。现在我们定义算法的两个版本：
import Data.Function.Memoize (memoize)
slow_notfib = let r = notfib_go r in r
fast_notfib = let r = memoize (notfib_go r) in r
也许这两个版本都不明显，在这种情况下，有关此主题的出色详细讨论，请参阅此处。
最后，一个简单的测试函数：
main = do
n:m:_ <- getArgs
let f = [slow_notfib,fast_notfib]!!read n
print $ f (read m)
以及一些试验结果：
Yuriy@Yuriy-PC ~/haskell
$ time ./test.exe 0 110000
698695701
real 0m3.111s
user 0m0.000s
sys 0m0.000s
Yuriy@Yuriy-PC ~/haskell
$ time ./test.exe 1 110000
698695701
real 0m0.017s
user 0m0.000s
sys 0m0.000s
即使是中等小的值也能提高 100 倍以上！
让我们概括一下。
对于某些序列{ a_i | i >= 0 }，假设我们有k基本情况a_0 ... a_{k-1}和所有a_n的k-nary递归关系f，n >= k：
a_n = f(a_{n-k}, a_{n-k+1}, ..., a_{n-2}, a_{n-1})
在 haskell 中，我们可以将这个序列写成一个核心草书无限列表：
as = a_0 :
a_1 :
{- ... : -}
a_kMinus1 :
zipWithK f (drop 0 as) (drop 1 as) {- ... -} (drop (k-1) as)
zipWithK f (a_nMinusK:as_nMinusK) {- ... -} (a_nMinus2:as_nMinus2) (a_nMinus1:as_nMinus1) =
f a_nMinusK {- ... -} a_nMinus2 a_nMinus1 : zipWithK f as_nMinusK as_nMinus2 {- ... -} as_nMinus1
zipWithK f _ _ {- ... -} _ = []
例如，我们可以小跑出斐波那契
fibs = 1 :
1 :
zipWith2 (+) (drop 0 fibs) (drop 1 fibs)
zipWith2 f (a_nMinus2:as_nMinus2) (a_nMinus1:as_nMinus1) =
f a_nMinus2 a_nMinus1 : zipWith2 f as_nMinus2 as_nMinus1
zipWith2 f _ _ = []
无限列表的好处是它们允许我们任意计算序列的许多元素。通过zips定义它们很好，因为它只有产生序列的每个元素的恒定开销，因为我们避免了列出昂贵的 (O(n(( 随机访问。
也就是说，ai iifiiite 列表仍然是一个列表辅助工具，而 processiig 的第一个i elemeits ii 你的后遗症可能会油腻地花费 O( i 的开销(，它仍然有不好的雷电访问 - 所以访问IIG只是i的Elemeit II续集也有O(i(的AI开销。
如果你想证明第一n的兰登访问的同义词elenents，你可以通过把这些 elenents 放在一个 Vector 中来做到这一点。 然后当你想要随机访问第 i 个序列元素，将i与n进行比较 - 如果 i小于 n ，只需在向量中查找(即 O(1((，否则回退到在序列的其余部分查找它，即 O(i - n(。
import Data.Vector ((!), Vector)
import qualified Data.Vector as V
vectorize n as = lookupV n bv cs
where (bs, cs) = splitAt n as
bv = V.fromList bs
lookupV n av _ i | i < n = av ! i
lookupV n _ as i = as !! (i - n)
所以你似乎希望这些东西被垃圾收集，你不想缓存一个巨大的列表。您可能喜欢的是一组严格的 spine 队列：
-- strict lists, strict queues.
data SL x = Nil | Cons x !(SL x)
data SQ x = SQ !(SL x) !(SL x)
sl_from_list :: [x] -> SL x
sl_from_list = foldr Cons Nil
sl_reverse :: SL x -> SL x
sl_reverse x = go Nil x where
go acc Nil = acc
go acc (Cons x rest) = go (Cons x acc) rest
enqueue :: x -> SQ x -> SQ x
enqueue x (SQ front back) = SQ front (Cons x back)
dequeue :: SQ x -> (x, SQ x)
dequeue (SQ Nil back) = case sl_reverse back of Cons x xs -> (x, SQ xs Nil)
dequeue (SQ (Cons x f') b) = (x, SQ f' b)
有了这些，您的随机数生成器看起来更加紧凑：
data MyRandGen x = MRG !(SQ x) !(SQ x)
next_rand (MRG a b) = (cv, MRG a'' b'') where
(av, a') = dequeue a
(bv, b') = dequeue b
cv = bv - av `xor` 75
a'' = enqueue bv a'
b'' = enqueue cv b'
请注意，这为生成新的随机数提供了"摊销"的 O(1( 性能：是的，有时它会在内存中创建 9000 个新单元格的昂贵重新分配，但这仅在对函数的 1/9000 调用时发生。这种保证的关键是，您不会尝试和重试从同一个MRG对象生成相同的随机数，因为它可能处于"即将重新分配大量数据"的状态，因此可能会发生不好的事情。如果你把这些东西不严格，你可以删除这种"最坏情况"的表现：事实证明，正如冈崎和其他人所指出的，懒惰既必要又足以将这些摊销操作转换为持久的恒定时间结构(你基本上做了上述一些反向工作(。
至于想清楚发生了什么：基本上我们有一个"三指清单"。手指进入列表是指存储具有语义的([x], [x])，您可以在两个不同的方向上导航： forwards (xs, y:ys) = (y:xs, ys)或backwards (x:xs, ys) = (xs, x:ys)：换句话说，两个列表在其"头部"连接，第一个列表的[]被认为是整个列表的开始，第二个列表的[]被认为是整体列表的末尾列表。
1500 个元素(，一根手指进入列表的末尾(过去 0 个元素，没有"后退"列表(。因为我们知道这种队列结构，所以我们知道如何有效地将中指的前部连接到起始指的末端(只需将所有元素反转到另一个(，如果我们不这样做，那么我们想要跟踪不同手指中有多少元素，并且只是"共享一些"，以便我们可以有效地支持以任何方式移动每个手指;但是由于我知道手指只是向一个方向移动，所以我只是为此进行了优化。