Patching a recursively-defined list without a <<loop>>
Asked Answered
P

1

7

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?

Phosphate answered 31/12, 2018 at 15:22 Comment(1)
My real problem is way more involved, but when splitting it down to subproblems I couldn't even get this part right, so here we are. I'll definitely have one or more questions pending. At any rate: my core function is certainly not (+)!Phosphate
T
5

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
Torytoryism answered 31/12, 2018 at 16:9 Comment(6)
Good find. Instead of rewriting splitAt, making the pattern lazier (as in (left,~(_:right)) = splitAt i xs) appears to be sufficient.Homologous
@DanielWagner, I didn't actually do any testing, so I took the conservative route ;-).Torytoryism
(Another possibility is to use only total functions and pattern matches which are guaranteed to suceed, as in patch i v xs = left ++ [v] ++ drop 1 right where (left, right) = splitAt i xs.)Homologous
Great, thanks a lot! I'd have two minor subquestions. Any difference/intent behind that a++[b]++c instead of my a++b:c? Any meaningful difference between those drop 1 and a simple tail?Phosphate
a++b:c is just as good (better without optimization). I was just copying from Daniel's comment. drop 1 has the advantage of being a total function. drop 1 [] = [] while tail [] is an error.Torytoryism
@Phosphate I find the symmetry of a++[b]++c pleasing; in most cases, it is also closer to the "intent" that I have in my head than a++b:c is. Since GHC is well smart enough to turn a++[b]++c into the more efficient a++b:c on its own, these aesthetics win out over the only technical consideration that differentiates them.Homologous

© 2022 - 2024 — McMap. All rights reserved.