Haskell - Sum up the first n elements of a list

Question

I´m new to Haskell.

Let´s say I want to sum up the first n elements of a list with a generated function on my own. I don´t know how to do this with Haskell. I just know how to sum up a whole given list, e.g.

sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

In order to sum up the first n elements of a list, for example

take the first 5 numbers from [1..10], which is 1+2+3+4+5 = 15

I thought I could do something like this:

sumList :: Int -> [Int] -> Int
sumList take [] = 0
sumList take (x:xs) = x + take $ sumList xs

But it doesn´t work... What´s wrong?

Solution 1

So you know how to sum up the numbers in a list,

sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

and if that list has no more than 5 elements in it, this function will even return the correct result if you indeed intended to sum no more than 5 elements in an argument list. Let's make our expectations explicit by renaming this function,

sumUpToFiveElements :: [Int] -> Int
sumUpToFiveElements [] = 0
sumUpToFiveElements (x:xs) = x + sumUpToFiveElements xs

it won't return the correct result for lists longer than five, but at least the name is right.

Can we fix that? Can we count up to 5? Can we count up to 5 while also advancing along the input list as we do?

sumUpToFiveElements :: Int -> [Int] -> Int
sumUpToFiveElements counter [] = 0
sumUpToFiveElements counter (x:xs) = x + sumUpToFiveElements (counter + 1) xs

This still isn't right of course. We do now count, but for some reason we ignore the counter. What is the right time to react to the counter, if we want no more than 5 elements? Let's try counter == 5:

sumUpToFiveElements :: Int -> [Int] -> Int
sumUpToFiveElements 5       [] = 0
sumUpToFiveElements counter [] = 0
sumUpToFiveElements counter (x:xs) = x + sumUpToFiveElements (counter + 1) xs

But why do we demand the list to also be empty when 5 is reached? Let's not do that:

sumUpToFiveElements :: Int -> [Int] -> Int
sumUpToFiveElements 5       _  = 0        -- the wildcard `_` matches *anything*
sumUpToFiveElements counter [] = 0
sumUpToFiveElements counter (x:xs) = x + sumUpToFiveElements (counter + 1) xs

Success! We now stop counting when 5 is reached! More, we also stop the summation!!

Wait, but what was the initial value of counter? We didn't specify it, so it's easy for a user of our function (that would be ourselves) to err and use an incorrect initial value. And by the way, what is the correct initial value?

Okay, so let's do this:

sumUpToFiveElements :: [Int] -> Int
sumUpToFiveElements xs = go 1 xs     -- is 1 the correct value here?
  where
    go counter  _ | counter == 5 = 0  
    go counter [] = 0
    go counter (x:xs) = x + go (counter + 1) xs

Now we don't have that extraneous argument that made our definition so brittle, so prone to a user error.

And now for the punchline:

Generalize! (by replacing an example value with a symbolic one; changing 5 to n).

sumUpToNElements :: Int -> [Int] -> Int
sumUpToNElements n xs = .......
   ........

Done.

---

One more word of advice: don't use $ while at the very beginning of your learning Haskell. Use explicit parens.

sumList take (x:xs) = x + take $ sumList xs 

is parsed as

sumList take (x:xs) = (x + take) (sumList xs)

This adds together two unrelated numbers, and then uses the result as a function to be called with (sumList xs) as an argument (in other words it's an error).

You probably wouldn't write it that way if you were using explicit parens.

Solution 2

Well you should limit the number of values with a parameter (preferably not take, since that is a function from the Prelude), and thus limit the numbers.

This limiting in your code is apparently take $ sumList xs which is very strange: in your function take is an Int, and $ will basically write your statement to (x + take) (sumList xs). You thus apparently want to perform a function application with (x + take) (an Int) as function, and sumList xs as argument. But an Int is not a function, so it does not typecheck, nor does it include any logic to limit the numbers.

So basically we should consider three cases:

1. the empty list in which case the sum is 0;
2. the number of elements to take is less than or equal to zero, in that case the sum is 0; and
3. the number of elements to take is greater than 0, in that case we add the head to the sum of taking one element less from the tail.

So a straightforward mapping is:

sumTakeList :: (Integral i, Num n) => i -> [n] -> n
sumTakeList _ [] = 0
sumTakeList t (x:xs) | t <= 0 = 0
                     | otherwise = x + sumTakeList (t-1) xs

But you do not need to write such logic yourself, you can combine the take :: Int -> [a] -> [a] builtin with the sum :: Num a => [a] -> a functions:

sumTakeList  :: Num n => Int -> [n] -> n
sumTakeList t = sum . take t

Now if you need to sum the first five elements, we can make that a special case:

subList5 :: Num n => [n] -> n
sumList5 = sumTakeList 5

Solution 3

A great resource to see what functions are available and how they work is Hoogle. Here is its page on take and the documentation for the function you want.

As you can see, the name take is taken, but it is a function you can use to implement this.

Note that your sumList needs another argument, the number of elements to sum. the syntax you want is something like:

sumList :: Int -> [Int] -> Int
sumList n xs = _ $ take n xs

Where the _ are blanks you can fill in yourself. It's a function in the Prelude, but the type signature is a little too complicated to get into right now.

Or you could write it recursively, with two base cases and a third accumulating parameter (by means of a helper function):

sumList :: Int -> [Int] -> Int
sumList n xs = sumList' n xs 0 where
  sumList' :: Int -> [Int] -> Int -> Int
  sumList' 0 _ a = _ -- A base case.
  sumList' _ [] a = _ -- The other base case.
  sumList' m (y:ys) a = sumList' _ _ _ -- The recursive case.

Here, the _ symbols on the left of the equals signs should stay there, and mean that the pattern guard ignores that parameter, but the _ symbols on the right are blanks for you to fill in yourself. Again, GHC will tell you the type you need to fill the holes with.

This kind of tail-recursive function is a very common pattern in Haskell; you want to make sure that each recursive call brings you one step closer to the base case. Often, that will mean calling itself with 1 subtracted from a count parameter, or calling itself with the tail of the list parameter as the new list parameter. here, you want to do both. Don't forget to update your running sum, a, when you have the function call itself recursively.

Solution 4

Here's a short-but-sweet answer. You're really close. Consider the following:

• The take parameter tells you how many elements you need to sum up, so if you do sumList 0 anything you should always get 0 since you take no elements.

• If you want the first n elements, you add the first element to your total and compute the sum of the next n-1 elements.

  sumList 0 anything = 0
  sumList n []       = 0
  sumList n (e:es)   = e + sumList (n-1) e
  

View more solutions

Comments

[amalloy]

take is an Int in the question posted, not the take function from Prelude.

[Davislor]

Ah. Well, you could write it with take from the Prelude, and it's a bad idea to re-use names from the Prelude. :)

[Will Ness]

replacing the _ in _ . take is not an easy thing for a beginner to do.

[Davislor]

@WillNess That'll show me to code at 1 AM without testing. Thanks.

[Will Ness]

you're welcome. :) this simple rule helps: remove one argument at a time.

[Davislor]

@WillNess Right. curry ( _ . uncurry take ) might be getting a little ahead of ourselves. :)

[Will Ness]

the standard way to write this (I think) is (_ .) . take.

[Slifer]

@Davislor: You´re right. I should not do that. I will consider this in the future. Sorry for that missunderstanding :)

[Slifer]

Thanks for this detailed explanation. This gives me a better understanding on how to solve such questions :) Presently, I´m more working like "trial and error" ... For beginners it might actually be better to use explicit parens ;)

[Will Ness]

you're welcome. with time, when you get a feel for it, you'll learn how to avoid this kind of explicit programming and follow the inductively defined data types more directly, or use built-in higher-order functions, or folding, etc. but first you must acquire a feel for it! :)

[Will Ness]

@Slifer there's no prohibition per se, it just adds some confusion, and also shadows the name so the built-in function becomes unavailable inside your function.

[amalloy]

It'd be simpler to explain counting down from n, rather than counting up from 0 to n, because you don't need go at all.

[Will Ness]

@amalloy I thought about it, and chose the counting up. I think it is simpler. With counting down, all must align perfectly for this one number. With counting up, we're free to choose any other number instead.

[Will Ness]

@amalloy counting up also keeps the two different aspects separate (while counting down conflates them) -- the one is the counting itself (following the inductive data type definition for Nats) and the other is the testing for the target value. so, conceptually, it is cleaner, I think. (and code economy was not my goal here :) ).