在Elixir中使用模式匹配和递归来拆分列表

我是Elixir的新手,也是编程方面的新手,特别是函数式编程(不到1年的Ruby和RoR经验) . 目前我正在阅读Dave Thomas的“Programming Elixir” . 我完全陷入了Lists和Recursion主题中的一个问题 .

戴夫要求“使用无库函数或列表推导来实现以下枚举函数:...拆分......”

原始功能是here .

我用相当长的时间解决问题,可能不是太优化(在我看来部分违反Dave的限制)方式:

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

使用Dave和其他读者解决方案浏览page,我发现2或3位读者使用的模式:

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 } 元组匹配函数的递归调用 . 什么应该匹配 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} 元组

  • 第三步(第4,5行):将 {left, right} 元组匹配到下一个递归调用并返回 {[1 | [2 | left]], right} 元组

  • 第四步(第6行):由于 split([3], 0) 与第二个子句匹配,我们此时得到 {left, right} = {[], [3]} 并且我们不能相应地用[]和[3]替换第5行中的 leftright 变量

  • 第五步(第7行):"pipes"完成工作并返回列表以最终匹配 left 变量

我还是不明白人们是如何找到这种解决方案的? (可能有模式匹配和递归的经验 . )

还有一件事困扰着我 . 例如,如果我们以第3行为例,则它是一个包含两个变量的“return” . 但实际上没有值与这些变量匹配 . 根据我的方案,这些变量只匹配第7行中的值 .

Elixir如何处理这个问题?是否有一些隐含的 nil 匹配?或者我的过程是错误的,直到最后一步才有实际的回报?

回答(3)

2 years ago

仅查看代码有时很难理解递归 . 精神上跟踪放在堆栈上的内容以及检索什么以及什么时候可以非常快地耗尽我们的工作记忆 . 在递归树的层次结构中绘制每个段落的路径会很有用,这就是我尝试回答你的问题所做的 .

为了理解这个例子中的工作原理,首先我们必须认识到第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 变量将首次被绑定?

  • 在第1条中将调用递归 split(tail, count - 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 的变量,在其 headtail 分量中被分解:

# FIRST STAGE
[head | tail] = in_list

然后 head 继续推进堆栈和 tail 以及更新 counter 传递给递归:

result = split(tail, count - 1)

count 次迭代之后,所有左分裂元素都在堆栈上,所有右分裂元素都打包在 tail 中 . 第2条现在被称为 .

在第2章调用之后,递归继续第二阶段,其中 result 变量绑定到前一个 split/2 迭代返回的两个(部分)拆分列表 .

现在,在每次迭代中,我们从结果中提取左侧和右侧列表:

{left,right} =结果

并添加到 left 从堆栈弹出的 head (在第一阶段计算),将结果返回给调用者:

return = {[head | left], right}

所以在每次迭代时左边部分都会增长到最终值 .

第2条返回第一个 result ,当迭代达到分裂点时匹配,即 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

希望这有助于澄清一点采用的策略和内部递归机制 .

(我的英语不是很好,希望有人能解决这个问题)

2 years ago

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

我在上面的代码中添加了一些注释 . 最终效果是列表的头部不断被剥离并与“左”列表连接,直到count减少为0.此时,您有一个返回为元组的两个列表 .

2 years ago

代码很棘手,因为它不是尾递归,因此它不是循环而且它记住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 实现的接近程度 .