How to use foldr to add variables to each other in a list?

Question

When given a list [x0, x1, x2, . . . , xn−1], the function should return the list [y0, y1, y2, . . . , yn−1] where y0 = x0, y1 = x0 + x1, ...

So if you had [1,2,3] as input, you would get [1,3,6] as output

I don't completely understand foldr, so maybe if I could get some help in trying to figure out how to change that last line to get the right answer.

scan :: [Integer] -> [Integer]
scan [] = []
scan [x] = [x]

scan (x:xs) = x : foldr (/y -> y (+) x) 0 (scan xs)

My initial solution (that works) uses the map function.

scan :: [Integer] -> [Integer]
scan [] = []
scan [x] = [x]

scan (x:xs) = x : map (+x) (scan xs)

Answer 1

EDIT, I added this first section to better address your two implementations.

First, addressing your issue with your implementation using foldr, here are a few remarks:

1. Lambdas start with a backslash in Haskell, not a slash. That's because backslashes kind of look like the lambda greek letter (λ).

2. Functions named using only special characters, like +, are infix by default. If you use parens around them, it turns them into prefix functions:

$> (+) 1 5
$> 6

3. The function passed to foldr takes two argument, whereas you're only supplying one in your lambda. If you really want to ignore the second one, you can use a _ instead of binding it to a variable (\x _ -> x).

I think this you're going down a rabbit hole with this implementation. See the discussion below for my take on the right way to tackle this issue.

Note: It is possible to implement map using foldr (source), that's one way you could use foldr in your working (second) implementation.

---

Implementing this with foldr is not optimal, since it folds, as the name implies, from the right:

foldr1 (+) [1..5]
--is equivalent to:
(1+(2+(3+(4+5))))

As you can see, the summing operation is done starting from the tail of the list, which is not what you're looking for. To make this work, you would have to "cheat", and reverse your list twice, once before folding it and once after:

scan = tail . reverse . foldr step [0] . reverse where
  step e acc@(a:_) = (e + a) : acc

You can make this better using a left fold, which folds from the left:

foldl1 (+) [1..5]
--is equivalent to:
((((1+2)+3)+4)+5)

This, however, still isn't ideal, because to keep the order of elements in your accumulator the same, you would have to use the ++ function, which amounts to quadratic time complexity in such a function. A compromise is to use the : function, but then you still have to reverse your accumulator list after the fold, which is only linear complexity:

scan' :: [Integer] -> [Integer]
scan' = tail . reverse . foldl step [0] where
  step acc@(a:_) e = (e + a) : acc

This still isn't very good, since the reverse adds an extra computation. The ideal solution would therefore be to use scanl1, which, as a bonus, doesn't require you to give a starting value ([0] in the examples above):

scan'' :: [Integer] -> [Integer]
scan'' = scanl1 (+)

scanl1 is implemented in terms of scanl, which is defined roughly like this:

scanl f init list = init : (case list of
                      []   -> []
                      x:xs -> scanl f (f init x) xs)

You can therefore simply do:

$> scanl1 (+) [1..3]
$> [1,3,6]

As a final note, your scan function is unnecessarily specialized to Integer, as it only requires a Num constraint:

scan :: Num a => [a] -> [a]

This might even lead to an increase in performance, but that's where my abilities end, so I won't go any further :)