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置换库函数 - 请澄清一下？

回答

相关问题