在Elixir中使用模式匹配和遞歸來分割列表

Question

我是Elixir中的新成員，在編程，尤其是函數式編程（Ruby和RoR中少於1年的經驗）方面是新的。目前我正在閱讀戴夫托馬斯的「Programming Elixir」。而且我完全陷入了列表和遞歸主題中的一個問題。

戴維問到「落實不使用庫函數或列表推導如下枚舉功能：...分裂......」

原始功能是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 

瀏覽通過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]}在這一點上，第二子句和我們不能用[]代替在線路5和left變量right和[3]相應
• 第五步（7號線）：「管道」做好自己的工作，並返回列表中最後匹配left變量

我還是不明白，是人是怎麼得出這個類型的解決方案？ （可能經驗模式匹配和遞歸）

另一件事困擾我。如果我們以第3行爲例，它是一個包含兩個變量的「返回」。但沒有值實際上與這些變量相匹配。根據我的計劃，這個變量只能匹配第7行的值。

Elixir如何處理這個問題？ 是否隱含nil匹配？ 或者我正在考慮這個過程錯誤，直到最後一步纔有實際回報？

Answer 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的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} 

我在上面的代碼中添加了一些註釋。 最終結果是，列表的頭部不斷被剝離並與「左」列表連接，直到count遞減爲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實現的距離有多近。