Using pattern matching and recursion in Elixir to break down a list

Question

I am new to Elixir and new to programming, especially functional programming (less than 1 year of experience in Ruby and RoR). Right now I'm reading Dave Thomas's Elixir Programming. And I'm completely stuck in one problem from the topic "Lists and recursion".

Dave asks "to implement the following Enum functions without using any library functions or lists: ... split ..."

The original function is here .

I have been solving the problem for quite some time, perhaps not too optimally (and, it seems to me, partially does not obey Dave’s limitations):

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

As I browse through the page using the solutions of Dave and other readers, I find a pattern that 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}

, , . , , , .

, filter1. : [ head_1 | ... head_n | filter1(tail_n, count - n) ]

, { left, right } tuple . left, - right? ?...

( () , , .)

UPD:

@Josh Petitt, @tkowal @CodyPoll, , .

, " ":

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]}

• ( 1): .
• ( 2, 3): {left, right} {[1 | left], right} tuple
• ( 4, 5): {left, right} {[1 | [2 | left]], right} tuple
• ( 6): split([3], 0) , {left, right} = {[], [3]} , left right 5 [] [3] ,
• ( 7): "pipe" , left

, , ? (, , .)

. 3, , "", . . , 7.

? nil ? ?

Answer 1

, . , , , . , , , .

, , 1, - , , - , .

( , )

# Clause 1
def split(in_list, count) when count > 0 do
  # FIRST STAGE
  [head | tail] = in_list

  # RECURSION
  result = split(tail, count - 1)

  # SECOND STAGE
  {left, right} = result 
  return = {[head | left], right}
end

#Clause 2
def split(list, _count), do: return = {[], list}

, , :

• , result ?
• split(tail, count - 1) 1?
• 2 split(list, _count)?
• 2?

, , :

( [1, 2, 3, 4, 5] , {[1, 2, 3], [4, 5]})

split([1,2,3,4,5], 3)

> FIRST STAGE of CLAUSE 1 / ITERATION 1 called as: split( [1, 2, 3, 4, 5], 3 ):
  Got 'head'=1, 'tail'=[2, 3, 4, 5], 'count'=3
  now I'm going to iterate passing the tail [2, 3, 4, 5],
  Clause 1 will match as the counter is still > 0
     > FIRST STAGE of CLAUSE 1 / ITERATION 2 called as: split( [2, 3, 4, 5], 2 ):
       Got 'head'=2, 'tail'=[3, 4, 5], 'count'=2
       now I'm going to iterate passing the tail [3, 4, 5],
       Clause 1 will match as the counter is still > 0
          > FIRST STAGE of CLAUSE 1 / ITERATION 3 called as: split( [3, 4, 5], 1 ):
            Got 'head'=3, 'tail'=[4, 5], 'count'=1
            Now the counter is 0 so I've reached the split point,
            and the Clause 2 instead of Clause 1 will match at the next iteration

> Greetings from CLAUSE 2 :-), got [4, 5], returning {[], [4, 5]}

          < Im BACK to the SECOND STAGE of ITERATION 3
            got result from CLAUSE 2: {[], [4, 5]}
            {left, right} = {[], [4, 5]}
            Now I'm build the return value as {[head | left], right},
            prepending 'head' (now is 3) to the previous value
            of 'left' (now is []) at each iteration,
            'right' instead is always [4, 5].
            So I'm returning {[3], [4, 5]} to iteration 2
     < Im BACK to the SECOND STAGE of ITERATION 2
       got result from previous Clause 1 / Iteration 3, : {[3], [4, 5]}
       {left, right} = {[3], [4, 5]}
       Now I'm build the return value as {[head | left], right},
       prepending 'head' (now is 2) to the previous value
       of 'left' (now is [3]) at each iteration,
       'right' instead is always [4, 5].
       So I'm returning {[2, 3], [4, 5]} to iteration 1
< Im BACK to the SECOND STAGE of ITERATION 1
  got result from previous Clause 1 / Iteration 2, : {[2, 3], [4, 5]}
  {left, right} = {[2, 3], [4, 5]}
  Now I'm build the return value as {[head | left], right},
  prepending 'head' (now is 1) to the previous value
  of 'left' (now is [2, 3]) at each iteration,
  'right' instead is always [4, 5].
  And my final return is at least: {[1, 2, 3], [4, 5]}
{[1, 2, 3], [4, 5]}

> FIRST STAGE of CLAUSE 1 / ITERATION n called as: ...

< I'm BACK to the SECOND STAGE of ITERATION n

, :

• ;
• 2 ;
• , 2, 1;
• 2 , 1.

, 2? , , , .

:

, in_list, head tail:

# FIRST STAGE
[head | tail] = in_list

head , tail counter :

result = split(tail, count - 1)

count , , , tail. 2.

2 , result () , split/2.

, , :

{left, right} = result

left head, ( ), :

return = {[head | left], right}

.

result 2, , , .. count = 0. ( 2 ). result 1.

:

def split(in_list, count), do: split(in_list, count, 1)

    # Clause 1
    def split(in_list=[head | tail], count, iteration) when count > 0 do
      offset = String.duplicate " ", 5 * (iteration - 1)
      IO.puts offset <> "> FIRST STAGE of CLAUSE 1 / ITERATION #{inspect iteration} called as: split( #{inspect in_list}, #{inspect(count)} ):"
      IO.puts offset <> "  Got 'head'=#{inspect head}, 'tail'=#{inspect tail}, 'count'=#{inspect count}"
      if (count - 1) > 0 do
        IO.puts offset <> "  now I'm going to iterate passing the tail #{inspect(tail)},"
        IO.puts offset <> "  Clause 1 will match as the counter is still > 0"
      else
        IO.puts offset <> "  Now the counter is 0 so I've reached the split point,"
        IO.puts offset <> "  and the Clause 2 instead of Clause 1 will match at the next iteration"
      end

      result = split(tail, count-1, iteration + 1)

      IO.puts offset <> "< Im BACK to the SECOND STAGE of ITERATION #{inspect(iteration)}"
      if (count - 1) == 0 do
        IO.puts offset <> "  got result from CLAUSE 2: #{inspect result}"
      else
        IO.puts offset <> "  got result from previous Clause 1 / Iteration #{iteration + 1}, : #{inspect result}"
      end
      IO.puts offset <> "  {left, right} = #{inspect result}"
      {left, right} = result
      IO.puts offset <> "  Now I'm build the return value as {[head | left], right},"
      IO.puts offset <> "  prepending 'head' (now is #{inspect head}) to the previous value"
      IO.puts offset <> "  of 'left' (now is #{inspect left}) at each iteration,"
      IO.puts offset <> "  'right' instead is always #{inspect right}."
      return = {[head | left], right}
      if (iteration > 1) do
        IO.puts offset <> "  So I'm returning #{inspect return} to iteration #{inspect(iteration - 1)}"
      else
        IO.puts offset <> "  And my final return is at least: #{inspect return} "
      end
      return
    end

    # Clause 2
    def split(list, _count, _iteration) do
      IO.puts ""
      IO.puts "> Greetings from CLAUSE 2 :-), got #{inspect(list)}, returning #{inspect({[], list})}"
      IO.puts ""
      {[], list}
    end

, .

( , - )

Answer 2

# the first element is head, the tail is the rest of the list
# count must be greater than 0 to match
def split([head | tail], count) when count > 0 do

  # recursively call passing in tail and decrementing the count
  # it will match a two element tuple
  {left, right} = split(tail, count-1)

  # return a two element tuple containing
  # the head, concatenated with the left element
  # and the right (i.e. the rest of the list)
  {[head | left], right}

end

# this is for when count is <= 0
# return a two element tuple with an empty array the rest of the list
# do not recurse
def split(list, _count), do: {[], list}

. , "" , 0. , .

Answer 3

, , O (n).

, :

split([1,2,3], 2) ->
#head = 1, tail = [2,3], count = 2
{left, right} = split([2,3], 1) -> #this is the recursive call
  #head = 2, tail = [3], count = 1
  {left, right} = split([3], 0)    #this call returns immediately, because it matches second clause
  {left, right} = {[], [3]} #in this call
  #what we have now is second list in place, we need to reassemble the first one from what we remember in recursive calls
  #head still equals 2, left = [], right = [3]
  {[head | left], right} = {[2], [3]} #this is what we return to higher call
#head = 1, left = [2], right = [3]
{[head | left], right} = {[1,2], [3]}

, , , . :

def identity([]) -> []
def identity([head | tail]) do
  # spot 1
  new_tail = identity(tail)
  # spot 2
  [head | tail]
end

. . , , , IO.puts head 1 2.

, , , split.