scanl behaves like this:
One way to state it in general: let rs = scanl (⊕) s0 xs:
Conversely, if we have a list rs satisfying these two equations, we can use scanl (⊕) s0 xs for it. Actually we will use the converse more often — we have some list in mind, we verify that it satisfies the two equations, and we conclude that we can use scanl to produce the list.
| rs !! 0 = s0 | |
| rs !! (n+1) = (rs !! n) ⊕ (xs !! n) | |
| ⇒ | |
| rs = scanl (⊕) s0 xs |
This characterization talks about “the nth item” because we will connect it with recurrences, which also talk about “the nth item”.
The powers of 2 (1, 2, 4, 8, 16, 32, 64…) satisfy this recurrence:
If we set rs=pow2s, xs=pow2s, s0=1, (⊕)=(+), this matches the scanl equations, and we can conclude:
Yes this is recursive. Sometimes it is written:
This derivation is superior to my previous explanation. But my previous explanation was for
Let's bridge the small gap:
Therefore pow2s = s.
The Fibonacci sequence goes as 0, 1, 1, 2, 3, 5, 8, 13… or as 1, 1, 2, 3, 5, 8, 13… depending on convenience. I normally start from 0; here I start from 1 to match a previous explanation. The story for starting from 0 is similar.
From here there are two ways to proceed.
One way sets rs=fibs, s0=1, (⊕)=(+), and the story for xs is more complicated. Note two oddities: the equation for fibs!!1 doesn't have a home, and the equation for fibs!!(n+1) has a gap at n=0. These two oddities help cancel each other: unify the two equations, now the homeless has a home and the gap is filled:
| fibs !! (n+1) = (fibs !! n) + 0 (if n=0) | |
| fibs !! (n+1) = (fibs !! n) + (fibs !! (n-1)) (if n≥1) | |
| ⇒ | |
| fibs !! (n+1) = (fibs !! n) + if n=0 then 0 else fibs!!(n-1) | |
| ⇒ | |
| fibs !! (n+1) = (fibs !! n) + ((0 : fibs) !! n) |
So xs = 0 : fibs
Sometimes it is written
Another way assigns rs!!n = fibs!!(n+1), in other words fibs = 1 : rs. (Nothing says rs must be responsible for the full answer, right?) This leads to easier equations and choice of xs.
So s0=1, (⊕)=(+), xs=fibs
Sometimes it is written
This derivation is superior to my previous explanation.
Both methods used in Fibonacci above apply to all 2nd-order recurrences. I like the second method more.
| o2s !! 0 = a | |
| o2s !! 1 = b | |
| o2s !! (n+2) = (o2s !! (n+1)) ⊕ (o2s !! n) | |
| ⇒ | |
| o2s = a : rs | |
| rs !! 0 = b | |
| rs !! (n+1) = (rs !! n) ⊕ (o2s !! n) | |
| ⇒ | |
| o2s = a : scanl (⊕) b o2s |
The Pell numbers:
| pells !! 0 = 0 | |
| pells !! 1 = 1 | |
| pells !! (n+2) = 2 * (pells !! (n+1)) + (pells !! n) | |
| ⇒ | |
| pells = 0 : scanl (\y z -> 2*y+z) 1 pells |
A contrived recurrence:
| foo !! 0 = 1 | |
| foo !! 1 = 2 | |
| foo !! (n+2) = (foo !! (n+1)) * (foo !! n) + 1 | |
| ⇒ | |
| foo = 1 : scanl (\y z -> y*z+1) 2 foo |
Given a list of numbers like [2,-3,40,-4,50,-1], find a segment (consecutive sublist) that has the maximum sum, and find that sum. The answer for the example is the segment [40,-4,50], sum 86. Empty segments are allowed, and their sum is 0; for example the answer for [-3,-2,-4] is [], sum 0.
Let xs be the given list of numbers. A solution assigns rs!!n to record a best segment ending just before xs!!n and its sum, and then the answer is some kind of maximum over rs. (This solution is not ingenious; it can be mechanically derived by a common heuristic, but that's another story.) Example:
| n | best segment | sum | ||||||
|---|---|---|---|---|---|---|---|---|
| 0 | [] | 0 | ||||||
| 1 | 2 | 2 | ||||||
| 2 | [] | 0 | ||||||
| 3 | 40 | 40 | ||||||
| 4 | 40 | -4 | 36 | |||||
| 5 | 40 | -4 | 50 | 86 | ||||
| 6 | 40 | -4 | 50 | -1 | 85 | |||
I use a tuple (segment,sum) for each rs!!n. They can be computed inductively. Base case: [] is the best segment ending just before x!!0.
Induction step: If you already know a best segment ending just before xs!!n, appending xs!!n normally gives you a best segment ending just before xs!!(n+1) — except, sometimes this is worse than just []. (Example: extending [2] to [2,-3] is worse than just [].) In terms of sums, normally you add xs!!n — except, sometimes this is worse than just 0.
| rs !! (n+1) = | let | (oldseg, oldsum) = rs !! n |
| newsum = oldsum + (xs !! n) | ||
| in | if newsum>=0 then (oldseg ++ [xs!!n], newsum) else ([], 0) |
The ⊕ here is rather lengthy, but rs is still a scanl:
| rs = scanl (⊕) ([],0) xs | ||
| (oldseg, oldum) ⊕ x = | let | newsum = oldsum + x |
| in | if newsum>=0 then (oldseg ++ [x], newsum) else ([], 0) | |
And lastly look for the maximum in rs:
(Import Data.List and Data.Ord for maximumBy and comparing, respectively)
Granted my use of oldseg++[x] is inefficient. You are invited to improve it.
I have more Haskell Notes and Examples