Haskell置換庫函數 - 請澄清一下？

這是在Haskell的Data.List模塊permutations函數的代碼：Haskell置換庫函數 - 請澄清一下？

permutations   :: [a] -> [[a]] 
permutations xs0  = xs0 : perms xs0 [] 
    where 
    perms []  _ = [] 
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is) 
     where interleave xs  r = let (_,zs) = interleave' id xs r in zs 
      interleave' _ []  r = (ts, r) 
      interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r 
            in (y:us, f (t:y:us) : zs)

有人能花時間向我解釋這段代碼是如何工作的？

我的困惑源於我非常習慣於編寫沒有外部依賴（即使它們嵌套在另一個函數中）的函數，尤其是如果它們是遞歸的。由於permutations裏面perms以及t和ts裏面interleave'，我就失去了功能的流程。

謝謝！

來源

2013-06-25 dxh

有很多不同的方式來編寫'排列'。這個不是最快的。但它有一個有趣的屬性，最快的版本並沒有。 – Carl

即，它適用於無限列表。 –

首先，我將移動重寫代碼的形式，這對您來說可能更容易理解，其中內部函數定義已移到主函數之外。請注意，我必須添加一些參數到interleave和 interleave'，以便他們可以「看到」它們在其他函數中定義時訪問的所有相同變量。

爲了清楚起見，我還添加了類型簽名。

permutations :: [a] -> [[a]] 
permutations xs0 = xs0 : perms xs0 []

功能perms需要兩個列表，並創建兩個列表元素的每一個可能的排列 - 但不包括原來的順序。例如：

λ> perms "ab" "XY" 
["aXYb","XaYb","aYXb","YaXb","baXY","abXY","aXbY","bXaY","XbaY","XabY","bYXa","YbXa","YXba","bXYa","XbYa","XYba","bYaX","YbaX","YabX","baYX","abYX","aYbX"]

所以，當我們有一個空的第二個列表來調用它，如permutations做，它給我們所有其他可能的輸入元素的排列。我們所要做的就是加緊原始序列，並且我們已經回答了。（如果你看一下permutations，上面，你會看到這正是它做什麼。）

λ> perms "abc" "" 
["bac","cba","bca","cab","acb"]

這裏的定義或perms。

perms :: [a] -> [a] -> [[a]] 
perms []  _ = [] 
perms (t:ts) is = foldr (interleave (t:ts)) (perms ts (t:is)) (permutations is)

功能interleave需要兩個列表，併產生各種可能的方式洗牌在一起（因爲你會一副撲克牌）。然後將第三個列表追加到可能的混洗列表中。例如：

λ> interleave "ab" "XY" ["@", "#"] 
["aXYb","XaYb","@","#"]

下面是它的定義：

interleave :: [t] -> [t] -> [[t]] -> [[t]] 
interleave (t:ts) xs r = let (_,zs) = interleave' (t:ts) id xs r in zs 

interleave' :: [t] -> ([t] -> a) -> [t] -> [a] -> ([t], [a]) 
interleave' (_:ts) _ []  r = (ts, r) 
interleave' (t:ts) f (y:ys) r = let (us,zs) = interleave' (t:ts) (f . (y:)) ys r 
            in (y:us, f (t:y:us) : zs)

來源

2013-06-25 16:24:36 mhwombat

謝謝！如果我正在實現這個功能並且知道我在做什麼，我可能會這樣寫;依靠捕獲外部變量，即在**模式綁定**，可以改變或甚至不存在於另一個電話中，只是簡單的混淆！ – dxh

儘量想任何遞歸調用簡單地以相同的功能，但使用不同的參數（希望呼叫的，否則你可能有一個無限循環），然後嘗試遵循一個非常簡單的例子的邏輯，如permutations [],permutations [1]或permutations [1,2]。

尋找何時內部表達式減少到基本情況，這是沒有更多的遞歸發生。例如，interleave'具有基本情況interleave' _ []和perms具有perms [] _ = []。

雖然我自己可能會迷失自己試圖追隨這個函數的繞圈，但我相信你會發現有些表達式會到達基本情況並從那裏展開，你將能夠評估遞歸那裏的電話。

來源

2013-06-25 17:00:03

Haskell置換庫函數 - 請澄清一下？

回答

相關問題