How to find sum of list of numbers in Haskell

Haskell is a functional programming language known for its strong type system and lazy evaluation. In Haskell, we can calculate the sum of a list using a recursive function that repeatedly adds each element to a variable until we encounter an empty list, or we can use a built-in sum function to find the sum of the list.

Custom function

We will construct our own recursive function to explore the problem and examine its code structure.

Approach

We can use a very basic approach to solve this problem. Here are the steps you need to follow to be able to find the sum of a list:

1. Define a function that accepts a list.

2. In the recursive case, calculate the sum by adding the current element to the sum of the rest of the list, whereas in the base case, an empty list will return the sum as 0.

3. Once the function reaches the base case, it effectively "calls back" to the previous recursive step, where the sum of each element was accumulated. This completes the recursion process, and the final sum is returned as the result of the function.

Code

The function sumList calculates the sum of a list using recursion, adding the current element to the sum of the rest of the list until it reaches the base case of an empty list, where it returns 0. This process effectively computes the sum of all elements in the list.

• Line 2: The sumList function signature indicates that it takes a list of elements of type a (belonging to the Num class) and returns a single value of the same type a. The Num a => part is a type constraint, ensuring a must be a numeric type like Int, Integer, or Float for the function to work.

• Line 3: When the input list is empty (represented by []), the function returns 0. This is the terminating condition for the recursion. When the list is empty, there are no elements left to add, so the sum is 0.

• Line 4: This is the recursive case of the sumList function, it calculates the sum by adding the current element x (the head of the list) to the sum of the rest of the list obtained through recursive calls with sumList xs, which represents the rest of the list.

Built-in sum function

The sum function helps us to find the sum of a list directly in Haskell. It uses the same recursive approach which we have discussed above to calculate the sum.

Code

Complexity

The custom and in-built functions use a recursive approach, so they have similar complexities. They have a time complexity of $O(n)$ as it involves $n$recursive calls, one for each element in the list, where $n$ represents the number of elements in the input list. Moreover, the space complexity is $O(n)$, as it creates additional function call records (activation records) for each element in the list.