代码之家 › 专栏 › 技术社区 › JB.

修补递归定义的列表而不使用<<loop>>

tying-the-knot haskell

6

JB. · 技术社区 · 6 年前

语境

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

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

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

问题

我正在尝试在一些地方修补它,以便:

一般递归方程__element是前两个元素__holds的和,但是
对于单个元素的值,可能存在可计数的异常。

我在哪里

效用

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

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 功能?其他地方的一些严格问题?还有别的吗?

1 回复 | 直到 6 年前

1

4

dfeuer 6 年前

你比你想的要严格一点。看

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

编辑

丹尼尔·瓦格纳指出,你不需要所有的懒惰(或偏袒) splitAtGuaranteed . 只要稍微懒惰一点就够了:

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