haskell - 修补没有 <> 的递归定义列表

Question

上下文

我们都知道the recursively-defined Fibonacci sequence :

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

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

问题

我正在尝试在几个地方“修补”它，以便:

1. 一般递归方程“元素是前两个元素的和”成立，但是
2. 单个元素的值可能存在很多异常(exception)情况。

我在哪里

实用程序

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

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...

补丁后

到目前为止，一切都很好。现在修补斐波那契数列:

λ> 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