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

Question

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

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)

有人可以花时间向我解释一下这段代码是如何工作的吗？

我的困惑源于这样一个事实:我非常习惯编写没有外部依赖项的函数(即使它们嵌套在另一个函数中)，特别是如果它们是递归的。 perms 内存在 permutations 以及 interleave' 内存在 t 和 ts >，就功能流程而言，我迷失了。

谢谢!

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 所做的那样，它会为我们提供输入元素的所有其他可能的排列。我们所要做的就是附加原来的序列，然后我们就得到了答案。 (如果您查看上面的排列，您就会发现这正是它的作用。)

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

这是定义或权限。

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)