Calculate sum and length of a list simultaneously with foldl and a tuple

Question

I've been struggling with foldr for a while now. i want to convert a list of ints to a single tuple that contains the sum of list and number of ints. for example [1,2,3,4] -> (10,4) the function i have below iterates through the list fine but only outputs the last element as the x val and 1 as the y val.

toTuple xs = let tuple = foldl (\a b -> ((sum1 + b),(len1 + 1))) (0.0,0.0) xs 
              in tuple   
               where sum1 = 0
                     len1 = 0  

i originally had sum1 and len1 as functions that take in an single int as an input but that didnt' work either so i changed them to variables initailized to 0. however it seems like its setting sum and len to 0 at every element in the list. any suggestions to modify this? thanks!

Answer 1

It looks like you haven’t built an intuition for folds yet. You can think of a fold like foldl combine start input as starting with some start value, then combining that value with each element of the input using the combine function. The function accepts the current “state” and the next element of the list, and returns the updated state. So you are very close to a working solution:

toTuple xs = foldl (\ (sum, len) x -> (sum + x, len + 1)) (0, 0) xs

Stepping through an example input like [1, 2, 3, 4], the state (sum, len), usually called an “accumulator”, takes on the following values each time the folding function is called:

(0, 0)
(0+1, 0+1)             = (1, 1)
(0+1+2, 0+1+1)         = (3, 2)
(0+1+2+3, 0+1+1+1)     = (6, 3)
(0+1+2+3+4, 0+1+1+1+1) = (10, 4)

At no point are we modifying any variables, just calculating the next value of the sum and the length by combining the current partial sum & length with each element of the list. For a left fold (foldl) that’s done from left to right; for a right fold (foldr) it’s from right to left, so the order of the parameters ((sum, len) and x) is reversed:

toTuple xs = foldr (\ x (sum, len) -> (sum + x, len + 1)) (0, 0) xs

However, for right folds, I find it easier to think of them as replacing all the : in a list with a function and replacing the [] with a value:

foldr f z [1, 2, 3, 4]
foldr f z (1 : (2 : (3 : (4 : []))))
1 `f` (2 `f` (3 `f` (4 `f` z)))

Answer 2

Well foldl has type foldl :: (a -> b -> a) -> a -> [b] -> a with a the type of the accumulator (here a 2-tuple), and b the type of elements in the list.

But in your lambda expression you write

\a b -> ((sum1 + b),(len1 + 1))

Note that here the variable b is an element of the list, and a is a tuple. But here you omit the accumulator. You always add sum1 to b, but since sum1, is a constant, that is rather useless. The same for len1, as a result, you will always obtain a tuple that contains the last element of the list as first item, and 1 as second item.

But based on your attempt, I think that you somehow aim to write "imperative" code in Haskell. Now in Haskell all variables are immutable, so setting len1 to 0 (in the where clause), will result in the fact that len1 is always 0, etc. We do not change the accumulator, in fact foldr is a recursive function that each time calls itself with parameters with different values, and at the end returns the parameter we call the "accumulator".

We can thus change the attempt to:

toTuple = (Fractional s, Fractional n) => [s] -> (s, n)
toTuple = foldl (\(cursum, curlen) b -> (cursum + b, curlen + 1)) (0.0,0.0)

So here we each time pattern match the accumulator with (cursum, curlen) (containing the "current" (thus far) sum and length), and each time we construct a new tuple that contains the "new" current sum (the sum of the old sum and b), and the "new" current length (the length incremented with one).

But it it still not very elegant: here the initial tuple has value (0.0, 0.0), but as a result, you tell Haskell that this is a 2-tuple where both elements are Fractionals. Although this will probably work given there are no rounding errors, why restrict this to Fractionals? If you have a list of Integers for example, we can sum these up without any rounding errors. By using (0, 0) as initial tuple, we make the tuple a 2-tuple where both elements have a type that belongs to the Num typeclass: so numbers. Note that the two do not per se have the same Num type, which is less restrictive.

So now we got:

toTuple = (Num s, Num n) => [s] -> (s, n)
toTuple = foldl (\(cursum, curlen) b -> (cursum + b, curlen + 1)) (0, 0)