Split list and make sum from sublist?

Question

im searching for a solution for my Haskell class.

I have a list of numbers and i need to return SUM for every part of list. Parts are divided by 0. I need to use FOLDL function.

Example:
initial list: [1,2,3,0,3,4,0,5,2,1]
sublist [[1,2,3],[3,4],[5,2,1]]
result [6,7,7]

I have a function for finding 0 in initial list:

findPos list = [index+1 | (index, e) <- zip [0..] list, e == 0] 

(returns [4,6] for initial list from example)

and function for making SUM with FOLDL:

sumList list = foldl (+) 0 list

But I completely failed to put it together :/

---- MY SOLUTION
In the end I found something completely different that you guys suggested.
Took me whole day to make it :/

groups :: [Int] -> [Int]
groups list = [sum x | x <- makelist list]

makelist :: [Int] -> [[Int]]
makelist xs = reverse (foldl (\acc x -> zero x acc) [[]] xs)  

zero :: Int -> [[Int]] -> [[Int]]
zero x acc | x == 0 = addnewtolist acc
           | otherwise = addtolist x acc

addtolist :: Int -> [[Int]] -> [[Int]]
addtolist i listlist = (i : (head listlist)) : (drop 1 listlist)

addnewtolist :: [[Int]] -> [[Int]]
addnewtolist listlist = [] : listlist

Answer 1

I'm going to give you some hints, rather than a complete solution, since this sounds like it may be a homework assignment.

I like the breakdown of steps you've suggested. For the first step (going from a list of numbers with zero markers to a list of lists), I suggest doing an explicit recursion; try this for a template:

splits []     = {- ... -}
splits (0:xs) = {- ... -}
splits (x:xs) = {- ... -}

You can also abuse groupBy if you're careful.

For the second step, it looks like you're almost there; the last step you need is to take a look at the map :: (a -> b) -> ([a] -> [b]) function, which takes a normal function and runs it on each element of a list.

As a bonus exercise, you might want to think about how you might do the whole thing in one shot as a single fold. It's possible -- and even not too difficult, if you track through what the types of the various arguments to foldr/foldl would have to be!

Additions since the question changed:

Since it looks like you've worked out a solution, I now feel comfortable giving some spoilers. =)

I suggested two possible implementations; one that goes step-by-step, as you suggested, and another that goes all at once. The step-by-step one could look like this:

splits []     = []
splits (0:xs) = [] : splits xs
splits (x:xs) = case splits xs of
    []       -> [[x]]
    (ys:yss) -> ((x:ys):yss)

groups' = map sum . splits

Or like this:

splits' = groupBy (\x y -> y /= 0)
groups'' = map sum . splits'

The all-at-once version might look like this:

accumulate 0 xs     = 0:xs
accumulate n (x:xs) = (n+x):xs

groups''' = foldr accumulate [0]

To check that you understand these, here are a few exercises you might like to try:

• What do splits and splits' do with [1,2,3,0,4,5]? [1,2,0,3,4,0]? [0]? []? Check your predictions in ghci.
• Predict what each of the four versions of groups (including yours) output for inputs like [] or [1,2,0,3,4,0], and then test your prediction in ghci.
• Modify groups''' to exhibit the behavior of one of the other implementations.
• Modify groups''' to use foldl instead of foldr.

Answer 2

Now that you've completed the problem on your own, I am showing you a slightly less verbose version. Foldr seems better in my opinion to this problem*, but because you asked for foldl I will show you my solution using both functions.

Also, your example appears to be incorrect, the sum of [5,2,1] is 8, not 7.

The foldr version.

makelist' l = foldr (\x (n:ns) -> if x == 0 then 0:(n:ns) else (x + n):ns) [0] l

In this version, we traverse the list, if the current element (x) is a 0, we add a new element to the accumulator list (n:ns). Otherwise, we add the value of the current element to the value of the front element of the accumulator, and replace the front value of the accumulator with this value.

Step by step:

1. acc = [0], x = 1. Result is [0+1]
2. acc = [1], x = 2. Result is [1+2]
3. acc = [3], x = 5. Result is [3+5]
4. acc = [8], x = 0. Result is 0:[8]
5. acc = [0,8], x = 4. Result is [0+4,8]
6. acc = [4,8], x = 3. Result is [4+3,8]
7. acc = [7,8], x = 0. Result is 0:[7,8]
8. acc = [0,7,8], x = 3. Result is [0+3,7,8]
9. acc = [3,7,8], x = 2. Result is [3+2,7,8]
10. acc = [5,7,8], x = 1. Result is [5+1,7,8] = [6,7,8]

There you have it!

And the foldl version. Works similarly as above, but produces a reversed list, hence the use of reverse at the beginning of this function to unreverse the list.

makelist l = reverse $ foldl (\(n:ns) x -> if x == 0 then 0:(n:ns) else (x + n):ns) [0] l

*Folding the list from the right allows the cons (:) function to be used naturally, using my method with a left fold produces a reversed list. (There is likely a simpler way to do the left fold version that I did not think of that eliminates this triviality.)