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?
(+)
! – Phosphate