在没有<< loop >>的情况下修补递归定义的列表

Question

上下文

我们都知道递归定义的Fibonacci序列:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

?> fibs
[1,1,2,3,5,9,13,21,34,55,89...

题

我试图在几个地方"修补"它,所以:

1. 一般递归方程"元素是前两个元素的总和",但是
2. 对于个别元素的价值,可以存在可数的例外情况.

我在哪里

效用

为此,我将定义以下函数来修改列表中的特定元素:

patch :: Int -> a -> [a] -> [a]
patch i v xs = left ++ v : right where (left,_:right) = splitAt i xs

我可以用它来改变自然的顺序:

?> patch 5 0 [0..]
[0,1,2,3,4,0,6,7,8,9...

后补丁

到现在为止还挺好.现在修补Fibonacci序列:

?> patch 1 0 fibs
[1,0,2,3,5,8,13,21,34,55,89...

这符合要求(2).

完整补丁

为了获得(1),我将以更明确的结合风格重写定义:

fibs' p = rec where rec = p (1 : 1 : zipWith (+) rec (tail rec))

没有补丁,它仍然按预期工作:

?> fibs' id
[1,1,2,3,5,9,13,21,34,55,89...

我现在可以修补我想要的元素并保持递归定义:

?> fibs' (patch 1 0)
[1,0,1,1,2,3,5,8,13,21,34...

局限性

但我可以吗？

?> fibs' (patch 5 0)
<<loop>>

问题

怎么了？

直觉上,数据流看起来很合理.每个列表元素都应该有一个不涉及循环的正确定义.我的意思是,这对于无补丁来说已经足够了fibs; 修补只应该使其更加明确.

所以我可能错过了一些东西.我的patch功能有些严格问题？别的一些严格问题？还有别的吗？

Answer 1

您比您想要的要严格一些。看着

patch i v xs = left ++ v : right where (left,_:right) = splitAt i xs

我相信您打算xs保证至少要有i要素。但是splitAt不知道。您可能可以使用自己的分离器修复程序。

splitAtGuaranteed :: Int -> [a] -> ([a], [a])
splitAtGuaranteed 0 xs = ([], xs)
splitAtGuaranteed n ~(x:xs) = first (x :) $ splitAtGuaranteed (n - 1) xs

编辑

丹尼尔·瓦格纳（Daniel Wagner）指出，您不需要的所有懒惰（或局部性）splitAtGuaranteed。只是一点点懒惰就足够了：

patch i v xs = left ++ [v] ++ drop 1 right where (left, right) = splitAt i xs