scanl behaves like this:

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

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

rs !! 0 = s0

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

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

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

pow2s !! 0 = 1

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

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.

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)

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)

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.

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.

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