# scanl tricks

Albert Y. C. Lai, trebla [at] vex [dot] net

## Theory

scanl behaves like this:

scanl (⊕) s0 [x,y,z] = [s0, s0x, (s0x)⊕y, ((s0x)⊕y)⊕z]

One way to state it in general: let rs = scanl (⊕) s0 xs:

rs !! 0 = s0
rs !! (n+1) = (rs !! n) ⊕ (xs !! n)

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”.

## Powers of 2

The powers of 2 (1, 2, 4, 8, 16, 32, 64…) satisfy this recurrence:

pow2s !! 0 = 1
pow2s !! (n+1) = (pow2s !! n) + (pow2s !! n)

If we set rs=pow2s, xs=pow2s, s0=1, (⊕)=(+), this matches the scanl equations, and we can conclude:

pow2s = scanl (+) 1 pow2s

Yes this is recursive. Sometimes it is written:

pow2s = fix (scanl (+) 1)

This derivation is superior to my previous explanation. But my previous explanation was for

s = 1 : tail (scanl (+) 1 s)

Let's bridge the small gap:

pow2s = head pow2s : tail pow2s = 1 : tail (scanl (+) 1 pow2s)

Therefore pow2s = s.

## Fibonacci

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.

fibs !! 0 = 1
fibs !! 1 = 1
fibs !! (n+1) = (fibs !! n) + (fibs !! (n-1)) (if n≥1)

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

fibs = scanl (+) 1 (0 : fibs)

Sometimes it is written

fibs = fix (scanl (+) 1 . (0:))

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.

rs !! 0 = fibs !! 1 = 1
rs !! (n+1) = fibs !! (n+2) = (fibs !! (n+1)) + (fibs !! n) = (rs !! n) + (fibs !! n)

So s0=1, (⊕)=(+), xs=fibs

fibs = 1 : rs = 1 : scanl (+) 1 fibs

Sometimes it is written

fibs = fix ((1:) . scanl (+) 1)

This derivation is superior to my previous explanation.

## More 2nd-Order Recurrences

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

## Maximum Segment Sum

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:

nbest segmentsum
0[]0
122
2[]0
34040
440-436
540-45086
640-450-185

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.

rs !! 0 = ([], 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:

mss xs = maximumBy (comparing snd) (scanl (⊕) ([],0) xs)

(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