Patching a recursively-defined list without a <

问题:

Context

We all know the recursively-defined Fibonacci sequence:

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. the general recursive equation “element is sum of two previous elements” holds, but
2. there can be countable exceptions as to individual elements' values.

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

This fulfills requirement (2).

Full patch

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?

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.

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

回答1:

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

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

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