Haskell排列库函数 - 请澄清一下？

问题描述

这是Haskell的 Data.List 模块中的 permutations 函数的代码：

  permutations :: [a]  - > [[a]] 
 permutations xs0 = xs0：perms xs0 [] 
其中
 perms [] _ = [] 
 perms（t：ts）is = foldr interleave ts（t：is））（置换是）
其中交织xs r =（ts，r）是在zs 
交织'_ [ 
 interleave'f（y：ys）r = let（us，zs）= interleave'（f。（y :)）ys r 
 in ）：
  

有人可以花时间向我解释这段代码的工作原理吗？

我的困惑来自于我非常习惯于编写没有外部依赖性的函数（即使它们嵌套在另一个函数中），特别是如果它们是递归的。在内部中存在置换以及 t 和 ts 里面 interleave'，我就失去了功能的流程。

谢谢！

解决方案

首先，这可能更容易让你
理解，内部函数定义移动到main函数之外。注意，我不得不添加一些参数到 interleave 和
interleave'所有相同的变量，他们有
访问时，它们在其他函数中定义。

我还添加了类型签名为了清晰。

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

函数 perms 需要两个列表，并在两个列表中创建元素的每个可能的
排列，但不是 包括原始顺序。例如：

 λ> permsabXY
 [aXYb，XaYb，aYXb，YaXb，baXY，abXY，aXbY，bXaY，XbaY，XabY ，bYXa，YbXa，YXba，bXYa，XbYa，XYba，bYaX，YbaX，YabX，baYX，abYX，aYbX 
 

所以当我们用一个空的第二个列表调用它时， permutations ，它给了我们所有的输入元素的其他可能的排列。我们所要做的是处理原始序列，我们已经得出答案。 （如果你看看排列，上面，你会看到这是它的作用。）

 λ> permsabc
 [bac，cba，bca，cab，acb] 
  

以下是定义或 perms 。

  perms :: [a]  - > [a]  - > （t：ts））（perms ts（t：is））（permutations is）（[t] = 1）
 perms [] _ = [] 
 perms 
  

函数 interleave 需要两个列表，生成每一种可能的
方式将它们一起洗牌（就像你一张纸牌一样）。然后
将第三个列表附加到可能的shuffle列表。例如：

 λ>交错abXY[@，＃] 
 [aXYb，XaYb，@，＃] 
  pre> 
 
 
这是它的定义：
  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：ts）f（y：ys）r = let（t：t） （y：us，f（t：y：us）：zs）
（us，zs）= interleave'（t：ts） code> 
 
This is the code for the permutations function in Haskell's Data.List module:
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)
Can someone take the time to explain to me how this code works?
My confusion stems from the fact that I am highly used to writing functions that have no external dependencies (even if they are nested inside another function), especially if they are recursive. With the presence of permutations inside perms as well as t and ts inside interleave', I am lost as far as the flow of the function is concerned.
Thanks!
 解决方案 
First, I'll move rewrite the code in a form that's probably easier for you tounderstand, with the internal function definitions moved outside the main function.  Note that I had to add some parameters to interleave andinterleave' so that they could "see" all the same variables they hadaccess to when they were defined within other functions.
I also added type signatures for clarity.
permutations :: [a] -> [[a]]
permutations xs0 =  xs0 : perms xs0 []
The function perms takes two lists, and creates every possiblepermutation of the elements in both lists -- but not including the original order. For example:
λ> 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"]
So when we invoke it with an empty second list, as permutations does, it gives us all the other possible permutations of the input elements. All we have to do is tack on the original sequence, and we have out answer. (If you look at permutations, above, you'll see that's exactly what it does.)
λ> perms "abc" ""
["bac","cba","bca","cab","acb"]
Here's the definition or perms.
perms :: [a] -> [a] -> [[a]]
perms []     _  = []
perms (t:ts) is = foldr (interleave (t:ts)) (perms ts (t:is)) (permutations is)
The function interleave takes two lists, and generates every possibleway to shuffle them together (as you would a pack of cards). It thenappends the third list onto the list of possible shuffles. For example:
λ> interleave "ab" "XY" ["@", "#"]
["aXYb","XaYb","@","#"]
Here's its definition:
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)
                        
这篇关于Haskell排列库函数 - 请澄清一下？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！