Haskell 置换库函数 - 请澄清一下？

Question

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

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' ，就功能的流程而言，我迷失了。

谢谢!

Answer 1

首先，我将用一种可能更容易让你改写的形式来重写代码
理解，将内部函数定义移到主函数之外。请注意，我必须在 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)