Understanding the implementation of the sum function
I started playing with Haskell a bit and came across the following function implementation sum
:
sum [] = 0
sum (x:xs) = x + sum xs
And then an explanation comes up showing how the function would behave in a real-world example:
sum [1,2,3]
1 + (sum [2,3])
1 + (2 + sum [3])
1 + (2 + (3 + sum []))
1 + (2 + (3 + 0))
= 6
I don't understand why every time the sum [x]
list is called, it decreases by 1 element?
My only guess is that when the construct is done, (x:xs)
the x
list item is not only retrieved but also removed (similar to the stacks pop()
. Method ), but I'm not sure about that.
In notation, x:xs
x is the head of the list, which is 1 element, and xs is the tail of the list, which is a list of 0 or more elements.
Since the recursive call is at xs, the set of task sizes decreases by 1 with each level of recursion.
There is no such thing as "removing an item from the list". Lists are immutable, like any other object. Now, in terms of implementation, in:
sum (x:xs) = x + sum xs
you are the template matching the list with the heading x
, and the rest of the list (headless) xs
. Specifically, sum [1, 2, 3]
you get:
sum (1:[2, 3]) = 1 + sum [2, 3]
If you remember, it is (:)
used to add an item to the list. So: 1:[2, 3]
in fact [1, 2, 3]
, which can also be written as: 1:2:3:[]
.
The only thing you have to remember is pattern matching on (x:xs)
means: put the title of the list on x
and the rest of the list on xs
.
This is recursion
Basically, you call the function again with the rest of the list summed up with the first item.