im really having trouble understanding how this entire function works. I am familiar with folds, and i have tried writing out it with an example like this : scanr (+) [1,2,3,4]. Its the two last lines that i dont understand.
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr _ q0 [] = [q0]
scanr f q0 (x:xs) = f x q : qs
where qs@(q:_) = scanr f q0 xs
Let’s first start with what scanr is trying to accomplish. The left and right versions of scan are the same thing as a fold except that we hold onto each state value we produce, ultimately returning an entire list of state values, instead of only returning the final state value like we would in a fold.
Let’s look at that first line:
scanr f q0 (x:xs) = f x q : qs
so we know this is the branch that gets run when the 3rd argument actually has at least one element in it, which we call x. f is a function that takes the current element + the state so far and returns the resulting state. So we’re going to call f with the our one element x, plus the “current state” q and we’re going to cons that with the list of preceeding states that we’ve already calculated, qs. Of course we haven’t defined q or qs yet, those come in the second line:
where qs@(q:_) = scanr f q0 xs
qs@(q:_) is a shorthand. You can kind of think of it the same as
where
qs = scanr f q0 xs
(q:_) = qs
So q is just the first element of qs, and qs is our recursive call to scanr where this time we pass in xs (the tail of our original input). That recursion where we pass in the tail is going to help us iterate through all of our input list.
Did that help?
do we first add the accumulator value at the end when we reach the end of the list, and if that is the case how does that become apart of our list. When i run through the first step :
(+) 1 q : qs
scanr (+) 5 [3,4,5]
(+) 2 q : qs
scanr (+) 5 [3,4,5]
(+) 3 q : qs
scanr (+) 5 [4,5]
(+) 4 q : qs
scanr (+) 5 [5]
(+) 5 q : qs
scanr (+) 5 []
scanr _ q0 [] = [5+4+3+2+1]
if this is how it happens im a little confused on how this is is appended onto the actual list qs
yeah, let’s step through it as if we just called
scanr (+) 0 [1,2]
So we first set f=(+), q0=0, x=1, xs=[2], and want to evaluate f x q : qs.
But in order to do that we need to evaluate qs which is our recursive call: scanr f q0 xs. So let’s put our calculation of f x q : qs on hold while we go do that.
Now x=2, xs=[], and we’re trying to evaluate this new f x q : qs. (note q and qs also change values in addition to x and xs, but we don’t have those values yet). Same problem, though, we’ve got to put that on hold while we recurse again to go calculate the new qs
Now we hit our terminating case, which just returns [q0]. In this case [0]. Finally a real answer! Now we can start backtracking to those former calculations we had to put on hold. So up one step, we had x=2, xs=[] and we were trying to calculate f x q : qs. This time we know qs is [0], and since q is just the first element of qs that’s going to be 0. So I evaluate that as
(+) 2 0 : [0] = [2,0].
Let’s go up one step further, where we had x=1, xs=[2], and now qs=[2,0] and q=2. So
(+) 1 2 : [2, 0] = [3,2,0]. This matches what we see in the REPL:
Prelude> scanr (+) 0 [1,2]
[3,2,0]
So to summarize:
scanr (+) 0 [1,2]
scanr (+) (0 + 2) [1] : [0]
scanr (+) (2 + 1) [] : [2, 0]
[3, 2, 0]
Because calculating each element depends on the recursive call using our tail, it forces us to evaluate the last element of our input list first, which is how it scans “from the right.”
how do we go from the first terminating case where we get [0] back to calling scanr. Is it just recursively backtracking to the calls we made prior ?
From a computing sense, yes. Every time you go to evaluate some function, you keep track of where you are first so that when you’re done evaluating that function, you can return to the same spot. That’s called a “call stack.”
I think the tricky part for a right scan as opposed to a left scan is that you can’t produce the answer for the current element until you’ve computed the answer for the recursive call - for the next element. Let’s look at a slightly simpler example of the same thing, the classic fibonacci sequence:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Say I want to calculate fib 4. To get that I need fib 3 + fib 2. Now one way to look at it would be the way I expressed above. We put that calculation on hold while we calculate fib 3 = fib 2 + fib 1. And then put that on hold while we calculate fib 2 = fib 1 + fib 0. Then when we substitute in our answers to get fib 2 = 1 + 0 = 1, we can “backtrack” to our previous expression fib 3 = fib 2 + fib 1, and “backtrack” again up to our original expression for fib 4. Another way of looking at it which might be more intuitive is successive substitutions:
fib 4 = fib 3 + fib 2
= (fib 2 + fib 1) + (fib 1 + fib 0)
= ((fib 1 + fib 0) + 1) + (1 + 0)
= ((1 + 0) + 1) + 1
= 3
We can’t do successive substitutions like that in the case of scanr, since we get two bindings out of a single recursive call (q and qs). But maybe you can sort of envision substituting in the recursive call for both q and qs, even though you can’t write it out?
Personally I have a computing background more so than a mathematics background so I tend to describe things as a computer would execute it.
I wonder if there’s a more intuitive explanation from the maths side?