修补没有<< loop>>的递归定义的列表. [英] Patching a recursively-defined list without a <<loop>>

问题描述

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

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

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

问题

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

Question

I'm trying to "patch" it in a few places, so that:

1. 一般的递归方程元素是两个先前元素的和"，但是
2. 关于单个元素的值，可以有很多例外情况.

我在哪里

实用程序

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

Where I'm at

Utility

To this end, I'll define the following function to modify a specific element in a list:

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

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

I can use it to change the sequence of naturals:

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

补丁发布

到目前为止，太好了.现在修补斐波那契序列:

Post-patch

So far, so good. Now to patch the Fibonacci sequence:

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

这满足要求(2).

同样要得到(1)，我将以更明确的打结样式重写定义:

To get (1) as well, I'll rewrite the definition in a more explicit tie-the-knot style:

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

没有补丁，它仍然可以按预期工作:

With no patch, it still works as expected:

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

现在我可以修补所需的元素并保留递归定义:

And I now can patch the element I want and keep the recursive definition:

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

限制

但是我可以吗?

Limitation

But can I?

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

问题

怎么了?

Problem

What's wrong?

直觉上，数据流听起来不错.每个列表元素都应该有一个不涉及循环的正确定义.我的意思是，对于不带补丁的fibs来说已经足够了；修补程序仅应使其定义为 more .

Intuitively, the dataflow seems sound. Every list element ought to have a proper definition that does not involve loops. I mean, it was good enough for no-patch fibs; the patching only ought to make it more defined.

所以我可能丢失了一些东西.我的patch函数存在一些严格性问题吗?其他地方有一些严格性问题吗?完全还有其他东西吗?

So I'm probably missing something. Some strictness issue with my patch function? Some strictness issue elsewhere? Something else entirely?

推荐答案

您比您想要的要严格一些.看

You're a bit stricter than you mean to be. Look at

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

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

I believe you intend that xs is guaranteed to have at least i elements. But splitAt doesn't know that. You can likely fix your program using your own splitter.

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

编辑

Daniel Wagner指出，您并不需要splitAtGuaranteed的所有惰性(或局部性).只是一点点懒惰就足够了:

Edit

Daniel Wagner points out that you don't need all the laziness (or the partiality) of splitAtGuaranteed. It's enough to be just a tiny bit lazier:

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

这篇关于修补没有<< loop>>的递归定义的列表.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！