7

语境

我们都知道递归定义的斐波那契数列：

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

补丁后

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

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

这满足要求 (2)。

完整补丁

为了也得到 (1)，我将用更明确的 tie-the-knot 样式重写定义：

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

问题

怎么了？

直观地说，数据流似乎是健全的。每个列表元素都应该有一个不涉及循环的正确定义。我的意思是，对于 no-patch 来说已经足够了fibs；修补只应该使它更明确。

所以我可能错过了一些东西。我的功能有一些严格性问题patch吗？其他地方的一些严格问题？完全不同的东西？

4

1 回答 1

5

你比你想象的要严格一些。看着

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
于 2018-12-31T16:09:05.817 回答