Haskell中列出的这些列表是如何实现的？ [英] What does this list permutations implementation in Haskell exactly do?

查看：119
本文介绍了Haskell中列出的这些列表是如何实现的？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述



 <$ c $ 
我正在研究Data.List模块中的代码， c> permutations :: [a]  - > [[a]] 
置换xs0 = xs0：perms xs0 [] 
其中
 perms [] _ = [] 
 perms（t：ts）is = foldr interleave（perms ts（t，is））（置换是）
其中交织xs r = let（_，zs）=交织'id xs r in zs 
 interleave'_ [] r =（ts，r） $（y：y）r = let（us，zs）= interleave'（f。（y :)）ys r 
 in（y：us，f（t：y：us） ）：zs）

有人可以详细解释这些嵌套函数如何相互连接/工作吗？

解决方案

对于迟到的回答，抱歉比写预计要花一点时间。





因此，首先要在这样的列表函数中最大化懒惰，有两个目标：


  • 在检查输入列表的下一个元素之前生成尽可能多的答案

  • 答案themselv现在考虑排列
    • $ b $ c>函数。这里最大的懒惰意味着：


    • 我们应该确定至少有 n！在检查 n 输入元素之后进行排列

    • 对于每个 n！排列，第一个 n 元素应该仅依赖于输入的第一个 n 元素。 b $ b

      第一个条件可以被形式化为 

        length （采用（阶乘n）$ permutations（[1..n] ++ undefined）））`seq`（）​​==（）



      David Benbennick把第二个条件形式化为：

      pre $ map $（n）（take（factorial n ）$ permutations [1..n] == permutations [1..n]

      有（$ n $）

      pre $ == permutations [1..n]

      让我们从一些简单的例子开始。首先 permutation [1 ..] 。我们必须有

        permutations [1 ..] = [1，???]：???

      有了两个元素，我们必须有

        permutations [1 ..] = [1,2，???]：[2,1，???]：???

      请注意，前两个元素的顺序没有选择，我们不能将 [2,1，...] 首先，因为我们已经决定第一个排列必须以 1 开头。现在应该清楚， permutations xs 的第一个元素必须等于 xs 本身。





      现在就执行。

      首先，有两个不同的方法来做一个列表的所有排列：


      1. 选择样式：保持从列表中选取元素，直到没有剩下的元素

          permutations [] = [[]] 
         permutations xxs = [（y：ys）| （y，xs）< - 选择xxs，ys < - 置换xs] 
        其中
        选择（x：xs）=（x，xs）：[（y，x：ys） （y，ys）<  - 挑选xs]


      2. 插入样式：插入或交错元素在所有可能的位置

        pre $ code> permutations [] = [[]]
        permutations（x：xs）= [y | （y：ys）=（x：y：ys），其中x是交织的数量， ：map（y :)（interleave ys）


      请注意，这些都不是最大限度的懒惰。第一种情况，这个函数做的第一件事是从整个列表中选择第一个元素，这根本不是懒惰的。在第二种情况下，我们需要尾部的排列，然后才能进行排列。

      首先，请注意 interleave 可以变得更加懒惰。 interleave yss 列表的第一个元素是 [x] if yss = [] 或（x：y：ys） if yss = y：ys 。但这两者都与 x：yss 相同，所以我们可以写出 

       <$ c （y：ys）= map（y :)（interleave ys）$ b $交错yss =（x：yss）：交错'yss 
      交错'[] = [] 
      交错' b

      Data.List中的实现继续这个想法，但使用了更多的技巧。



      也许最简单的方法是通过邮件列表讨论。我们从David Benbennick的版本开始，它与我上面所写的版本相同（没有懒惰交错）。我们已经知道， permutations xs 的第一个元素本身应该是 xs 。所以，让我们把它放在

      pre code> permutations中b $ b permutations'（x：xs）= tail $ concatMap interleave $ permutations xs
      where interleave = ..

      调用 tail 当然不是很好。但如果我们将置换和交错的定义联系起来，我们就可以得到

        permutations'（x：xs）
       = tail $ concatMap interleave $ permutations xs 
       = tail $ interleave xs ++ concatMap interleave（permutations'xs）
       = tail $（x：xs）：interleave'xs ++ concatMap interleave（permutations'xs）
       = interleave'xs ++ concatMap interleave（permutations'xs）
        
       
        permutations xxs =  
      > 
       
       
       xxs：permutations'xxs 
       permutations'[] = [] 
       permutations'（x：xs）= interleave'xs ++ concatMap interleave（permutations'xs）
       where 
       interleave yss =（x：yss）：interleave'yss 
       interleave'[] = [] 
       interleave'（y：ys）= map（y :)（interleave ys）
              
      下一步是优化。一个重要的目标是消除交织中的（++）调用。这并不容易，因为最后一行 map（y :)（interleave ys）。我们不能立即使用传递尾部的foldr / ShowS技巧作为参数。出路是摆脱地图。如果我们传递一个参数 f 作为必须映射到结尾的函数，我们得到
       
       
       <$ （x：xs）= interleave'id xs ++ concatMap（interleave id）（permutations'xs）
      其中
      交错f yss = f（x ：yss）：interleave'f yss 
       interleave'f [] = [] 
       interleave'f（y：ys）= interleave（f。（y :)）ys

      现在我们可以在尾部传递

       <$ c（x：xs）= interleave'id xs $ foldr（interleave id）[]（permutations'xs）
       where 
       interleave f yss r = f（x：yss）： interleave'f yss r 
       interleave'f [] r = r 
       interleave'f（y：ys）r = interleave（f。（y :)）ys r

      这看起来像Data.List中的一个，但它现在还不一样。特别是，它并不像它那样懒惰。
      让我们试试看： 

        * Main>让n = 4 
       * Main> map（take n）（take（factorial n）$ permutations（[1..n] ++ undefined））
       [[1,2,3,4]，[2,1,3,4]， [2,3,1,4]，[2,3,4,1] ***例外：Prelude.undefined

      呃哦，只有第一个 n 元素是正确的，而不是第一个 factorial n 。
      原因是在尝试其他任何事情之前，我们仍然尝试将第一个元素（上例中的 1 ）放置在所有可能的位置。





      Yitzchak Gale想出了一个解决方案。考虑将输入分成初始部分，中间元素和尾部的所有方法：

      pre $ [1..n] == [] ++ 1：[2..n]
      == [1] ++ 2：[3..n]
      == [1,2] ++ 3：[4 ..n]

      如果您之前没有看到过生成这些技巧，您可以这与 zip（inits xs）（tails xs）。
      现在， [1..n] 的排列将为


      • [] ++ 1：[2..n] aka。插入（交叉存取） [1..n] 或
      • 2 在 [1] ，然后是 [3..n] 的排列中。但是在 [1] 的末尾插入 2 ，因为我们已经将该结果放在前一个项目符号点中。

      • 3 交错排列为 [1,2] （不是然后是 [4..n] 。

      • 等。

        • ul>

        你可以看到这是最大的懒惰，因为在我们甚至考虑使用 3 做一些事情之前，我们已经给出了所有的排列开始于 [1,2] 的一些排列。 Yitzchak提供的代码是

        pre $ code> permutations xs = xs：concat（zipWith newPerms（init $ tail $ tails xs）
        （init $ tail $ inits xs））
        其中
        newPerms（t：ts）= map（++ ts）。 concatMap（interleave t）。 permutations3
        interleave t [y] = [[t，y]]
        interleave t ys @（y：ys'）=（t：ys）：map（y :)（interleave t ys'）

        请注意对 permutations3 的递归调用，可以是不需要最大限度地懒惰的变体。



        正如您所看到的，这比我们以前的版本少了一些优化。但我们可以应用一些相同的技巧。



        第一步是摆脱 init 和尾。让我们看看 zip（init $ tail $ tail xs）（init $ tail $ inits xs）实际上是

          *主> （init $尾$尾xs）
         [（[2,3,4,5]，[1]），（[ 3,4,5]，[1,2]），（[4,5]，[1,2,3]），（[5]，[1,2,3,4]）]

        init 不需要组合（[]，[1..n]），而尾部摆脱组合（[1 ...... N]，[]）。我们不希望前者，因为这会使 newPerms 中的模式匹配失败。后者将失败交错。两者都很容易解决：只需为 newPerms [] 和 interleave t [] 添加一个案例。

          permutations xs = xs：concat（zipWith newPerms（tails xs）（inits xs））
        其中
         newPerms [ ]是= [] 
         newPerms（t：ts）is = map（++ ts）（concatMap（interleave t）（permutations is））
         interleave t [] = [] 
         interleave t ys @（y：ys'）=（t：ys）：map（y :)（interleave t ys'）

        现在我们可以尝试内联 tails 和 inits 。他们的定义是：

          tails xxs = xxs：case xxs of 
         []  - > [] 
        （_：xs） - > tails xs 
         
         inits xxs = []：case xxs of 
         []  - > [] 
        （x：xs） - > map（x :)（inits xs）

        问题在于 inits 不是尾递归。但是，既然我们要采取排列的方式，我们并不关心元素的顺序。所以我们可以使用累加参数，

          inits'= inits''[] 
        其中
         inits ''是xxs = is：case xxs of 
         []  - > [] 
        （x：xs） - > inits''（x：is）xs

        现在我们使 newPerms 一个函数 xxs 和这个累积参数，而不是 tails xxs 和 inits xxs 。

         排列xs = xs：concat（newPerms'xs []）
         where 
         newPerms'xxs is = 
         newPerms xxs is：
         case xxs of 
         []  - > [] 
        （x：xs） - > newPerms'xs（x：is）
         newPerms [] is = [] 
         newPerms（t：ts）is = map（++ ts）（concatMap（interleave t）（permutations3 is））

        内联 newPerms 到 newPerms '然后给出 

          permutations xs = xs：concat（newPerms'xs []）$ b $ （其中
         newPerms'[] is = []：[] 
         newPerms'（t：ts）is = 
         map（++ ts）（concatMap（interleave t）（permutations is） ）：
         newPerms'ts（t：is）

        内嵌和展开 concat ，并将最终的 map（++ ts）移动到 interleave 中， 

         置换xs = xs：newPerms'xs [] 
        其中
         newPerms'[] is = [ ] 
         newPerms'（t：ts）is = 
         concatMap interleave（permutations is）++ 
         newPerms'ts（t：is）
         where 
         interleave [] = [] 
         interleave（y：ys）=（t：y：ys ++ ts）： map（y :)（interleave ys）

        最后，我们可以重新应用 foldr 诡计摆脱（++）：

         $ $ b $ newPerms'（t：ts）= $ b $ （交织ID）（newPerms'ts（t：is））（置换是）
        其中
        交织f [] r = r 
        交织f（y：ys）r = f （t：y：ys ++ ts）：interleave（f。 （y :)）ys r

        等等，我说要摆脱 （++）。我们摆脱了其中的一个，但不是 interleave 中的一个。
        为此，我们可以看到我们总是将 yys 的尾部连接到 ts 。因此，我们可以展开计算（ys ++ ts）以及 interleave 的递归，并且具有函数 interleave'f ys r 返回元组（ys ++ ts，interleave f ys r）。这给出了

        pre $ permutations xs = xs：newPerms'xs []
        其中
        newPerms'[]是= []
        newPerms'（t：ts）is =
        foldr interleave（newPerms'ts（t：is））（permutations is）
        where
        interleave ys r = let （z，z）= interleave'id ys r in zs
        interleave'f [] r =（ts，r）
        interleave'f（y：ys）r =
        let （y：us，f（t：y：us）：zs）
         pre>

        并且在那里， Data.List.permutations 在它最大的懒惰优化荣耀中。 p>



        Twan的优秀写作！我（@Yitz）只会添加一些引用：




        • Twan开发此算法的原始电子邮件线程， Twan，吸引人的是阅读。

          • 4 Fasc。 2秒7.2.1.2。

        • Twan的 permutations3 与Knuth的算法P基本相同。据Knuth所知，该算法在1600年代首先由英国教堂钟声响起。



        I am studying the code in the Data.List module and can't exactly wrap my head around this implementation of 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)

        Can somebody explain in detail how these nested functions connect/work with each other?

        解决方案

        Sorry about the late answer, it took a bit longer to write down than expected.

        So, first of all to maximize lazyness in a list function like this there are two goals:

        • Produce as many answers as possible before inspecting the next element of the input list
        • The answers themselves must be lazy, and so there the same must hold.

        Now consider the permutation function. Here maximal lazyness means:

        • We should determine that there are at least n! permutations after inspecting just n elements of input
        • For each of these n! permutations, the first n elements should depend only on the first n elements of the input.

        The first condition could be formalized as

        length (take (factorial n) $ permutations ([1..n] ++ undefined))) `seq` () == ()

        David Benbennick formalized the second condition as

        map (take n) (take (factorial n) $ permutations [1..]) == permutations [1..n]

        Combined, we have

        map (take n) (take (factorial n) $ permutations ([1..n] ++ undefined)) == permutations [1..n]

        Let's start with some simple cases. First permutation [1..]. We must have

        permutations [1..] = [1,???] : ???

        And with two elements we must have

        permutations [1..] = [1,2,???] : [2,1,???] : ???

        Note that there is no choice about the order of the first two elements, we can't put [2,1,...] first, since we already decided that the first permutation must start with 1. It should be clear by now that the first element of permutations xs must be equal to xs itself.

        Now on to the implementation.

        First of all, there are two different ways to make all permutations of a list:

        1. Selection style: keep picking elements from the list until there are none left

          permutations []  = [[]]
permutations xxs = [(y:ys) | (y,xs) <- picks xxs, ys <- permutations xs]
  where
    picks (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- picks xs]

        2. Insertion style: insert or interleave each element in all possible places

          permutations []     = [[]]
permutations (x:xs) = [y | p <- permutations xs, y <- interleave p]
  where
    interleave []     = [[x]]
    interleave (y:ys) = (x:y:ys) : map (y:) (interleave ys)

        Note that neither of these is maximally lazy. The first case, the first thing this function does is pick the first element from the entire list, which is not lazy at all. In the second case we need the permutations of the tail before we can make any permutation.

        To start, note that interleave can be made more lazy. The first element of interleave yss list is [x] if yss=[] or (x:y:ys) if yss=y:ys. But both of these are the same as x:yss, so we can write

        interleave yss = (x:yss) : interleave' yss
interleave' [] = []
interleave' (y:ys) = map (y:) (interleave ys)

        The implementation in Data.List continues on this idea, but uses a few more tricks.

        It is perhaps easiest to go through the mailing list discussion. We start with David Benbennick's version, which is the same as the one I wrote above (without the lazy interleave). We already know that the first elment of permutations xs should be xs itself. So, let's put that in

        permutations xxs     = xxs : permutations' xxs
permutations' []     = []
permutations' (x:xs) = tail $ concatMap interleave $ permutations xs
  where interleave = ..

        The call to tail is of course not very nice. But if we inline the definitions of permutations and interleave we get

        permutations' (x:xs)
  = tail $ concatMap interleave $ permutations xs
  = tail $ interleave xs ++ concatMap interleave (permutations' xs)
  = tail $ (x:xs) : interleave' xs ++ concatMap interleave (permutations' xs)
  = interleave' xs ++ concatMap interleave (permutations' xs)

        Now we have

        permutations xxs     = xxs : permutations' xxs
permutations' []     = []
permutations' (x:xs) = interleave' xs ++ concatMap interleave (permutations' xs)
  where
   interleave yss = (x:yss) : interleave' yss
   interleave' [] = []
   interleave' (y:ys) = map (y:) (interleave ys)

        The next step is optimization. An important target would be to eliminate the (++) calls in interleave. This is not so easy, because of the last line, map (y:) (interleave ys). We can't immediately use the foldr/ShowS trick of passing the tail as a parameter. The way out is to get rid of the map. If we pass a parameter f as the function that has to be mapped over the result at the end, we get 

        permutations' (x:xs) = interleave' id xs ++ concatMap (interleave id) (permutations' xs)
  where
   interleave f yss = f (x:yss) : interleave' f yss
   interleave' f [] = []
   interleave' f (y:ys) = interleave (f . (y:)) ys

        Now we can pass in the tail,

        permutations' (x:xs) = interleave' id xs $ foldr (interleave id) [] (permutations' xs)
  where
   interleave  f yss    r = f (x:yss) : interleave' f yss r
   interleave' f []     r = r
   interleave' f (y:ys) r = interleave (f . (y:)) ys r

        This is starting to look like the one in Data.List, but it is not the same yet. In particular, it is not as lazy as it could be. Let's try it out:

        *Main> let n = 4
*Main> map (take n) (take (factorial n) $ permutations ([1..n] ++ undefined))
[[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1]*** Exception: Prelude.undefined

        Uh oh, only the first n elements are correct, not the first factorial n. The reason is that we still try to place the first element (the 1 in the above example) in all possible locations before trying anything else.

        Yitzchak Gale came up with a solution. Considered all ways to split the input into an initial part, a middle element, and a tail:

        [1..n] == []    ++ 1 : [2..n]
       == [1]   ++ 2 : [3..n]
       == [1,2] ++ 3 : [4..n]

        If you haven't seen the trick to generate these before before, you can do this with zip (inits xs) (tails xs). Now the permutations of [1..n] will be

        • [] ++ 1 : [2..n] aka. [1..n], or
        • 2 inserted (interleaved) somewhere into a permutation of [1], followed by [3..n]. But not 2 inserted at the end of [1], since we already go that result in the previous bullet point.
        • 3 interleaved into a permutation of [1,2] (not at the end), followed by [4..n].
        • etc.

        You can see that this is maximally lazy, since before we even consider doing something with 3, we have given all permutations that start with some permutation of [1,2]. The code that Yitzchak gave was

        permutations xs = xs : concat (zipWith newPerms (init $ tail $ tails xs)
                                                (init $ tail $ inits xs))
  where
    newPerms (t:ts) = map (++ts) . concatMap (interleave t) . permutations3
    interleave t [y]        = [[t, y]]
    interleave t ys@(y:ys') = (t:ys) : map (y:) (interleave t ys')

        Note the recursive call to permutations3, which can be a variant that doesn't have to be maximally lazy.

        As you can see this is a bit less optimized than what we had before. But we can apply some of the same tricks.

        The first step is to get rid of init and tail. Let's look at what zip (init $ tail $ tails xs) (init $ tail $ inits xs) actually is

        *Main> let xs = [1..5] in zip (init $ tail $ tails xs) (init $ tail $ inits xs)
[([2,3,4,5],[1]),([3,4,5],[1,2]),([4,5],[1,2,3]),([5],[1,2,3,4])]

        The init gets rid of the combination ([],[1..n]), while the tail gets rid of the combination ([1..n],[]). We don't want the former, because that would fail the pattern match in newPerms. The latter would fail interleave. Both are easy to fix: just add a case for newPerms [] and for interleave t [].

        permutations xs = xs : concat (zipWith newPerms (tails xs) (inits xs))
  where
    newPerms [] is = []
    newPerms (t:ts) is = map (++ts) (concatMap (interleave t) (permutations is))
    interleave t []         = []
    interleave t ys@(y:ys') = (t:ys) : map (y:) (interleave t ys')

        Now we can try to inline tails and inits. Their definition is

        tails xxs = xxs : case xxs of
  []     -> []
  (_:xs) -> tails xs

inits xxs = [] : case xxs of
  []     -> []
  (x:xs) -> map (x:) (inits xs)

        The problem is that inits is not tail recursive. But since we are going to take a permutation of the inits anyway, we don't care about the order of the elements. So we can use an accumulating parameter,

        inits' = inits'' []
  where
  inits'' is xxs = is : case xxs of
    []     -> []
    (x:xs) -> inits'' (x:is) xs

        Now we make newPerms a function of xxs and this accumulating parameter, instead of tails xxs and inits xxs.

        permutations xs = xs : concat (newPerms' xs [])
  where
    newPerms' xxs is =
      newPerms xxs is :
      case xxs of
        []     -> []
        (x:xs) -> newPerms' xs (x:is)
    newPerms [] is = []
    newPerms (t:ts) is = map (++ts) (concatMap (interleave t) (permutations3 is))

        inlining newPerms into newPerms' then gives

        permutations xs = xs : concat (newPerms' xs [])
  where
    newPerms' []     is = [] : []
    newPerms' (t:ts) is =
      map (++ts) (concatMap (interleave t) (permutations is)) :
      newPerms' ts (t:is)

        inlining and unfolding concat, and moving the final map (++ts) into interleave,

        permutations xs = xs : newPerms' xs []
  where
    newPerms' []     is = []
    newPerms' (t:ts) is =
        concatMap interleave (permutations is) ++
        newPerms' ts (t:is)
      where
      interleave []     = []
      interleave (y:ys) = (t:y:ys++ts) : map (y:) (interleave ys)

        Then finally, we can reapply the foldr trick to get rid of the (++):

        permutations xs = xs : newPerms' xs []
  where
    newPerms' []     is = []
    newPerms' (t:ts) is =
        foldr (interleave id) (newPerms' ts (t:is)) (permutations is)
      where
      interleave f []     r = r
      interleave f (y:ys) r = f (t:y:ys++ts) : interleave (f . (y:)) ys r

        Wait, I said get rid of the (++). We got rid of one of them, but not the one in interleave. For that, we can see that we are always concatenating some tail of yys to ts. So, we can unfold the calculating (ys++ts) along with the recursion of interleave, and have the function interleave' f ys r return the tuple (ys++ts, interleave f ys r). This gives

        permutations xs = xs : newPerms' xs []
  where
    newPerms' []     is = []
    newPerms' (t:ts) is =
        foldr interleave (newPerms' ts (t:is)) (permutations is)
      where
      interleave ys r = let (_,zs) = interleave' id ys r in zs
      interleave' f []     r = (ts,r)
      interleave' f (y:ys) r = 
        let (us,zs) = interleave' (f . (y:)) ys r
        in  (y:us, f (t:y:us) : zs)

        And there you have it, Data.List.permutations in all its maximally lazy optimized glory.

        Great write-up by Twan! I (@Yitz) will just add a few references:

        • The original email thread where Twan developed this algorithm, linked above by Twan, is fascinating reading.

        • Knuth classifies all possible algorithms that satisfy these criteria in Vol. 4 Fasc. 2 Sec. 7.2.1.2.

        • Twan's permutations3 is essentially the same as Knuth's "Algorithm P". As far as Knuth knows, that algorithm was first published by English church bell ringers in the 1600's.

        这篇关于Haskell中列出的这些列表是如何实现的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆