Undoing a prefix sum

Question

The simple way to calculate a prefix sum in Haskell is

scanl1 (+) [1,2,3,4,5,6]

which produces the output

[1,3,6,10,15,21]

I needed to write the inverse, and this is what I came up with:

undo_prefix_sum :: (Num a) => [a] -> [a]
undo_prefix_sum s = init $ snd $ 
    foldr (\cur (tot, l) -> (cur, (tot-cur):l)) 
          (last s, []) 
          (0:s)

This seems to be correct (but I might have missed something). Is there a simpler or more efficient way to do this, possibly using a scan?

Answer 1

In my opinion, as prefix_sum is naturally expressed as a fold, undo_prefix_sum is more naturally expressed as an unfold.

import Data.List

undo_prefix_sum  = unfoldr (\xs -> if null xs 
                                   then Nothing
                                   else let (h:t) = xs 
                                        in Just (h,  map (subtract h) t))

unfoldr uses a function to build a list starting from a seed value. In this case, the seed is a list itself; we use the first element of the seed in our result, and (a modified version of) the rest of the list as the seed to compute the rest of the result recursively.

Answer 2

Your function should have been written as

undo_prefix_sum' :: (Num a) => [a] -> [a]
undo_prefix_sum' xs = init $ snd $ 
    foldr (\x ~(y, ys) -> (x, (y-x):ys)) 
          (undefined, []) 
          (0:xs)

The tot in your code is not "total", it's simply the next value in the input after x. So some symmetry in the names is called for here (naming is important). The last xs bit is never calculated because of the init call so can just be undefined, to avoid giving the false impression.

Since all it does is to calculate the difference between each element and its predecessor (or 0 for the very first one), we might as well be clear about that:

foo xs = [y-x | i <- [0..length xs-1], let y=xs!!i ; x = (0:xs)!!i ]

which is of course quadratic, and it calculates the length which is a big no-no; but at least it's simple, so it's simple enough to fix:

bar xs = [y-x | x <- 0:xs | y <- xs]
       = map (uncurry (-)) $ zip xs (0:xs)
       = zipWith (-) xs (0:xs)

which you've already seen, as stated in the comments. So it really is equivalent to your code, computationally, unlike the code in the other answer which calculates the same result by means of a substantially different, essentially quadratic (and needlessly so), calculation.

If you really wanted to express the zipWith (-) process as an unfolding, it could be done as

baz xs = [y-x | (x:y:_) <- tails (0:xs)]

since tails ~= iterate tail, and iterating and unfolding are essentially the same thing (each can be expressed as the other, with some possibly needed pre- and/or post- processing steps).

One last thing. There indeed is a problem with your code. It is needlessly strict:

> take 2 $ undo_prefix_sum $ [1,2] ++ undefined
*** Exception: Prelude.undefined

> take 2 $ undo_prefix_sum' $ [1,2] ++ undefined
[1,1]

foo above is also similarly strict. All the other versions in this answer (and code in the other answer as well) successfully and correctly calculate the result. The only difference between the undo_prefix_sum' here and your code, except for the variables renaming, is a very small one.

Can you spot it?

With that out of the way, whether your code is nominally using foldr or unfoldr, the important thing is whether it is lazy enough. foldr with a lazy combining function is just as capable of coding that. Catamorphisms like sum are necessarily strict. To write your function as a proper anamorphism so it is still linear as it should be, we need to pre-process the input by zipping it with its tail since we need the two head elements at once. Another way to code this is with a paramorphism so that we'd have access to the input's current tail as well as its current element. And paramorphisms are emulated easily enough by folding over the tails (yes, like baz is doing).