2

这是permutationsHaskellData.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)

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

我的困惑源于我非常习惯于编写没有外部依赖关系的函数（即使它们嵌套在另一个函数中），尤其是当它们是递归的时候。随着permutationsinsideperms和inside的存在t，就函数的流程而言，我迷失了方向。tsinterleave'

谢谢！

4

2 回答 2

3

首先，我将以一种可能更容易理解的形式重写代码，并将内部函数定义移到主函数之外。请注意，我必须添加一些参数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-25T16:24:36.997 回答
0

尝试将任何递归调用简单地视为对相同函数但具有不同参数的调用（希望如此，否则您可能会遇到无限循环），然后尝试遵循一个非常简单示例的逻辑，permutations []例如permutations [1]或permutations [1,2]。

寻找内部表达式何时减少到基本情况，这是不再发生递归的地方。例如interleave'有基本情况interleave' _ []和perms有perms [] _ = []。

虽然我可能会在尝试跟随这个函数的曲折时有点迷失，但我相信你会发现一些表达式会到达基本情况并从那里展开，你将能够评估导致那里的递归调用.

于 2013-06-25T17:00:03.987 回答