Add lists of numbers respecting a relative shift between the starts of
the lists. The shifts must be non-negative. The list of relative
shifts is one element shorter than the list of summands. Infinitely
many summands are permitted, provided that runs of zero shifts are all
finite.
We could add the lists either with
foldl or with
foldr,
foldl would be straightforward, but more time consuming
(quadratic time) whereas foldr is not so obvious but needs only linear
time.
(stars denote the coefficients, frames denote what is contained in the
interim results)
foldl sums this way:
| | | *******************************
| | +--------------------------------
| | ************************
| +----------------------------------
| ************
+------------------------------------
I.e.
foldl would use much time find the time differences by
successive subtraction 1.
foldr mixes this way:
+--------------------------------
| *******************************
| +-------------------------
| | ************************
| | +-------------
| | | ************