Haskell: how do you slide and sum a list to the right more than once?

Question

In this answer to a problem that I failed to explain, but was considered useful due to its outline and solution, the list was shifted to the right once, and addition was used between this list and the initial one, to produce outputs like these:

[1,2] -> [1,3,2]
[1,2,3] -> [1,3,5,3]
[1,2,3,4] -> [1,3,5,7,4]

It was an answer that I rewrote to suit my needs like this:

slideSum :: [Integer] -> [Integer]

slideSum l = slideRight l []
  where
    slideRight [] a = a
    slideRight (x:[]) a = (x:a)
    slideRight (x:y:zs) a = slideLeft (x:a) (slideRight (sum (x:y:a):a) (slideLeft (y:zs) a))
      where
        slideLeft [] a = a
        slideLeft (x:[]) a = (x:a)
        slideLeft (x:y:zs) a = slideRight (sum (x:y:a):a) (slideLeft (y:zs) a)

And what it does is to keep the first and last elements intact, sum the first two and the following pair, for which I had to go left and right. When I tried to rewrite this for the following outputs:

[1,2,3] -> [1,3,6,5,3] [1,2,3,4] -> [1,3,6,10,9,7,4]

That is to shift the first list as many times as the number of elements minus one to sum them, I could not arrive at a solution that I considered to be natural, because I had to manipulate the result of two smaller expressions by dropping one element. This is the problem illustrated:

  0:0:1:2:3:[]    
  0:1:2:3:0:[]    0:1:2:[]
  1:2:3:0:0:[]    1:2:0:[]
+ ------------  + --------
  1:3:6:5:3:[]    1:3:2:[]

And this is how I manipulated its result, which I want to avoid:

slideSum :: [Integer] -> [Integer]
slideFromLeft :: [Integer] -> [Integer]
slideFromRight :: [Integer] -> [Integer]

slideFromLeft l = slideRight l []
  where
    slideRight [] a = a
    slideRight (x:[]) a = (x:a)
    slideRight (x:y:zs) a = slideRight (x:a) (slideRight (sum (x:y:a):zs) a)

slideFromRight l = slideLeft l []
  where
    slideLeft [] a = a
    slideLeft (x:[]) a = (x:a)
    slideLeft (x:y:zs) a = slideLeft (sum (x:y:zs):a) (slideLeft (y:zs) a)

slideSum l = slideFromLeft l ++ (tail slideFromRight l)

Does the nature of this problem require a different thought process or is the solution in need of its problem to be split into smaller parts? Can you slide the initial list and produce different results by keeping the former in memory?

user_849891 · Answer

What you want is apparently

foo :: Num b => [b] -> [b]
foo xs = map sum . transpose . take n . map (take (n+n-1))
                 . map (++ repeat 0) . iterate (0:) $ xs
   where
   n = length xs

See? Since Haskell is lazy, we don't care if we add more 0s than are actually needed. It will all get sorted out in the end by lazy evaluation.

Testing:

> foo [1..2]
[1,3,2]

> foo [1..3]
[1,3,6,5,3]

> foo [1..4]
[1,3,6,10,9,7,4]

We can make it properly non-strict so it works with infinite lists as well by throwing away the length computation, using zipWith const instead,

bar :: (Integral b) => [b] -> [b]
bar xs  =  map sum . zipWith take [1..]
                . transpose 
                . zipWith (const id) xs  
                . map (zipWith (const id) (xs ++ drop 1 xs))
                . map (++ repeat 0) . iterate (0:) $ xs

though all these takes, explicit and otherwise, make it look a bit too busy.

Or we could use diagonals from one of the packages that define it.

Haskell: how do you slide and sum a list to the right more than once?

1 Answers