I saw this snippet and I don't understand how this is being done with pattern matching. It'd be great if someone can explain it to me (or anyone else who might not understand this as well)
def even_length?([]) do
true
end
def even_length?([_head | tail]) do
!even_length?(tail)
end
I'm simply lost when it comes given inputs such as [1, 2] or [3, 4, 5]
Thanks in advance.
Source of code: https://gist.github.com/mauricioabreu/8fdb64bef6a938dd1e34ac15e9268d4d
That's a very clever piece of code, though it might be easier to understand if you follow it's execution step by step.
Before we look at a few examples, it's important that you understand that Elixir implements Lists as Linked Lists and each list has a head and a tail where the tail itself is a separate list term.
Every list (other than an empty list) can be written as [ head | tail ]:
[1] == [ 1 | [] ]
# => true
[3, 2, 1] == [ 3 | [2, 1] ]
# => true
[3, 2, 1] == [ 3 | [ 2 | [ 1 | [] ] ] ]
# => true
[]Calling even_length?([]) would match the first signature and directly return true, since that's the base case of our recursive function.
[x]When calling the function on a list with one element, the VM would skip the first function definition (since it's not empty), and move on to the second one which in turn calls the function recursively on just the tail part and inverting the boolean value. If we expand the call stack, it would look like this:
even_length?([1]) # `1` is head, `[]` is tail
# => !even_length?([])
# => !(true) # We know value is `true` from base-case
# => false
[x, y]Same thing, but we will invert the result once more (since the function will be called an extra time):
even_length?([2, 1]) # `2` is head, `[1]` is tail
# => !even_length?([1]) # `1` is head, `[]` is tail
# => !(!even_length?([]))
# => !(!(true)) # We know value is `true` from base-case
# => !(false)
# => true
[x, y, z]even_length?([3, 2, 1]) # `3` is head, `[2, 1]` is tail
# => !even_length?([2, 1]) # `2` is head, `[1]` is tail
# => !(!even_length?([1])) # `1` is head, `[]` is tail
# => !(!(!even_length?([])))
# => !(!(!(true))) # We know value is `true` from base-case
# => !(!(false))
# => !(true)
# => false
[ ... ]And this will continue repeating. The simplest way to understand what this function does is that it has defined that a List with 0 elements should return true, and for every extra element it should invert (boolean not) the previous value.
When you call even_length?([1, 2]) it matches: even_length?([_head | tail])
where _head is 1 and tail is [2].
Then, recursively, it call: !even_length?([2]) which matches even_length?([_head | tail]) where _head is 2 and tail is [].
Since tail is [] then, it call: !even_length?([]) which matches the first function even_length?([]) where returns true.