99 个 Haskell 个问题中的第 26 个 - 为什么结果包含多个具有相同标题的列表？

Question

我想弄清楚 99 Haskell problems 问题 26 的解决方案之一是如何工作的。解决方法如下：

combination :: Int -> [a] -> [[a]]
combination 0 _ = [ [] ]
combination i xs = [ y:ys | y:xs' <- tails xs, ys <- combination (i-1) xs']

我不明白为什么会有多个列表具有相同的头部。对我来说，使用tails xs生成的y:ys中的y部分只能用来组成一个列表。

示例：

combination 2 [1,2,3]

首先，我们从 tails xs 中取出 y 部分，这给了我们三个列表：[1,(not known yet)]、[2,(not known yet)]、[3,(not known yet)]。那么最后怎么会得到多个以1为头的结果呢？

我也不明白为什么列表[3]不会出现在结果中？它肯定会作为标题出现在 tails xs 生成的列表之一中。我不想在单独的问题中提出这个问题 - 我希望没关系。

Answer 1

列表解析在某种程度上定义了嵌套循环。因此，在定义中

combinations n xs =

我们可以阅读代码

        [ y:ys | y:t <- tails xs, ys <- combinations (n-1) t]

为

        for each (y:t) in (tails xs)
            for each ys in (combinations (n-1) t) 
                produce (y:ys) as a new element of the resulting list

换句话说，to pick n elements from a list 意味着选择某个元素，以及列表中它后面的 n-1 个元素。

此定义的不确定性通过生成所有可能解决方案的列表来表示，作为结果。我们仅选择 元素右侧 的 n-1 元素，以仅生成在排列下唯一的解决方案。

我们以xs = [1,2,3]为例。 tails [1,2,3] 产生什么？

当然是 [[1,2,3], [2,3], [3], []]。现在，这相当于

[ r | r <- [[1,2,3], [2,3], [3], []] ]

这意味着，从该列表中抽取的 r 连续采用其元素的值。 r 是一个 无可辩驳的 模式； (y:t) 是一个可反驳的模式，即它将无法匹配 [] 元素：

[ (y,t) | (y:t) <- tails [1,2,3]]
  =>  [(1,[2,3]), (2,[3]), (3,[])]

所以你看，t不是"not known yet"。它是已知的，它只是给定列表的尾部。而当y匹配3时，t匹配[].

此外，

[ (y,q) | (y:t) <- tails [1,2,3], q <- [10,20]]
 =>  [(1,10), (1,20), (2,10), (2,20), (3,10), (3,20)]

这足以说明问题，希望能够解决您的第一个问题：对于每个匹配的 (y:t) 模式，q 是从 [10,20] 中提取的，即它也采用中的值列表（这里，[10,20]）连续，对于每个 y，就好像在 嵌套循环 .

中一样

对于您 combinations 2 [1,2,3] 的示例，我们有

  combinations 2 [1,2,3]
=
  for each (y,t) in [ (1,[2,3]), (2,[3]), (3,[]) ]
      for each ys in (combinations 1 t)
          produce (y:ys)
=
  for y = 1, t = [2,3]
      for each ys in (combinations 1 [2,3]) produce (1:ys) , and then
  for y = 2, t = [3]
      for each ys in (combinations 1 [3])   produce (2:ys) , and then
  for y = 3, t = []
      for each ys in (combinations 1 [])    produce (3:ys)

combinations 1 [] 是 []，因为 tails [] 是 [[]] 并且模式匹配 (y:t) 与 [] 作为生成器的一部分 (y:t) <- [[]] 会失败；所以第三行 for 行 _{不会产生任何解决方案（解决方案的头部会有 3 - 因为没有更多的元素从右边选择第二个元素，因为我们需要整体选择 2 个元素；3 确实参与了其他解决方案的尾部，它也应该如此）。}

第二个 for 行显然只产生一个解，[2,3]。第一个 for 行产生什么？

      for each ys in (combinations 1 [2,3]) produce (1:ys)

combinations 1 只取一个元素，所以它产生 [2] 和 [3]；所以第一行 for 产生两个解决方案，[1,2] 和 [1,3]。或者更详细地说，

      combinations 1 [2,3] 
    =
      for y = 2, t = [3]
          for each ys in (combinations 0 [3]) produce (2:ys) , and then
      for y = 3, t = []
          for each ys in (combinations 0 [])  produce (3:ys)

和 combinations 0 总是产生一个空列表的解决方案（一个以空列表作为唯一元素的单例列表，[ [] ]，表示从列表中选取 0 个元素的解决方案).

总的来说，返回了三个解决方案的列表，[[1,2], [1,3], [2,3]]。

Answer 2

这里要注意的核心问题是问题的递归性质。

我们如何从列表中选择 i 项？

如果列表为空，则没有组合。所以这不是一个有趣的案例。
如果列表不为空 - 我们可以为组合选择第一项，也可以不选择
- 如果我们选择它，我们仍然需要从列表的其余部分中选择 i-1 项
- 如果我们不选择它，我们仍然需要从列表的其余部分中选择 i 个项目

正在做：

[ y:ys | y:xs' <- tails xs, ys <- combination (i-1) xs']

查看 xs 的所有尾部，即 查看为 [=11] 选择 第一个 元素的所有可能性=]组合.
选择第一个元素，如上所述，我们现在有 i-1 个项目，因此，我们需要将该元素连接到 i-1 个项目与其余项目的组合。

99 个 Haskell 个问题中的第 26 个 - 为什么结果包含多个具有相同标题的列表？

26 of 99 Haskell problems - why the result contains multiple lists with the same head?

recursion

combinations

haskell

list-comprehension