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.
source to share
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
.
source to share