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:
- the general recursive equation “element is sum of two previous elements” holds, but
- 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?
You're a bit stricter than you mean to be. Look at
I believe you intend that
xs
is guaranteed to have at leasti
elements. ButsplitAt
doesn't know that. You can likely fix your program using your own splitter.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: