Using pattern matching and recursion in Elixir to split the list

Question

I am new in Elixir and new in programming, especially functional programming (less than 1 year experience in Ruby and RoR). For the moment I am reading "Programming Elixir" by Dave Thomas. And I am completely stuck with one problem from the Lists and Recursion theme.

Dave asking to "implement the following Enum functions using no library functions or list comprehensions: ...split ..."

The original function is here.

I solve the problem with rather long, probably not too optimal (and seems to me partially disobeying Dave's restrictions) way:

def split(list, count) do
  if count < 0, do: count = len(list) + count
  list1 = filter1(list, count)
  list2 = list -- list1
  # list2 = filter2(list, list1)
  { list1, list2 }
end

def len([]), do: 0
def len([ _head | tail ]), do: 1 + len(tail)

defp filter1([], _count), do: []
defp filter1([ head | tail], count) do
  if count > 0 do
    [ head | filter1(tail, count - 1) ]
  else
    filter1(tail, count - 1)
  end
end

Browsing through the page with Dave's and other readers solutions I find out pattern which was used by 2 or 3 readers:

def split([head | tail], count) when count > 0 do
  {left, right} = split(tail, count-1)
  {[head | left], right}
end
def split(list, _count), do: {[], list}

This code seems to me rather elegant, but I can not understand how it works. I mean I've tried to comprehend what happening step by step and I failed.

I can imagine what happening in my filter1 recursive function. List is forming like this: [ head_1 | ... head_n | filter1(tail_n, count - n) ]

But I can't understand why { left, right } tuple is matching the recursive call for the function. What should match to the left and what to the right? How this recursion works?...

(The meaning of the second line (of the function) is also not clear for me but I think this is strictly connected with the first question.)

UPD:

Thanks to @Josh Petitt, @tkowal and @CodyPoll I think I moved forward in my comprehension of the case.

Now I am thinking about the recursion-matching pattern discussed in this "pyramidal way":

1  split([1, 2, 3], 2)
2    {left, right} = split([2, 3], 1)
3    {[1 | left], right}
4      {left, right} = split([3], 0)
5      {[1 | [2 | left]], right}
6    {[1 | [2 | []]], [3]}
7  {[1 ,2], [3]}

First step (line 1): call the function.
Second step (lines 2, 3): match {left, right} tuple to the recursive function call and return {[1 | left], right} tuple
Third step (lines 4, 5): match {left, right} tuple to the next recursive call and return {[1 | [2 | left]], right} tuple
Fourth step (line 6): since split([3], 0) matching the second clause we get {left, right} = {[], [3]} at this point and we can no replace left and right variables in the line 5 with [] and [3] accordingly
Fifth step (line 7): "pipes" do their job and return the list to finally match the left variable

What I still don't understand is how folks come to this type of solution? (Probably experience with both pattern matching and recursion.)

And another thing bothers me. If we take line 3 for example, it is a "return" which contains two variables. But no values was actually matched to this variables. According to my scheme this variables only match their values in line 7.

How Elixir deal with this? Is it some implicit nil matching? Or I am taking the process wrong and there is no actual return until the final step?

Using pattern matching and recursion in Elixir to split the list

3 Answers