haskell - 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,(notknown Yet)]， [2，(尚未知)]，[3，(尚未知)]。那么为什么最后我们会得到以 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

换句话说，选择n列表中的元素意味着选择某个元素，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不是“尚不知道”。它是已知的，它只是给定列表的尾部。当 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]] 。