我正在努力理解如何在 Haskell 中读取 concat

Question

连接代码：

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

我不明白它是如何被阅读的。 xss 如何拆分为 xs 和 x？还是我看错了？

例如，给定：

concat [[1,2,3],[4],[5]]

[1,2,3,4,5]是如何实现的？

Answer 1

在列表理解中，a <- b 位表示“对于 b 中的每个 a”。

所以在你的情况下，xs <- xss 应该读作“for each xs in xss”，然后 x <- xs 应该读作“for each x in xs”，这也是有效的，因为 xs 本身是一个列表，因为 xss 是列表的列表。

因此随着列表理解的展开，xs 首先绑定到 [1,2,3]，然后绑定到 [4]，然后绑定到 [5]，并且在 [5] 的每次迭代中=14=]、x 绑定到 1、2、3，然后绑定到 4，最后绑定到 5。

Answer 2

如果非要和命令式编程做比较，我们可以想到

[ expr | x1 <- list1 , x2 <- list2 , ....]

作为一个嵌套的 for 循环，将 expr 产生的值累加到一个列表中，如下所示：

result = []
for x1 in list1:
  for x2 in list2:
    ...
    result.append(expr)

在你的情况下，我们有

result = []
for xs in xss:
  for x in xs:
    result.append(x)

所以，当 xss = [[1,2,3],[4],[5]] 我们有：

xs = [1,2,3]
- x = 1 附加到结果中
- x = 2 附加到结果中
- x = 3 附加到结果中
xs = [4]
- x = 4 附加到结果中
xs = [5]
- x = 5 附加到结果中

因此最后的结果是[1,2,3,4,5].

这个比较不是一个完全忠实的描述，因为它没有考虑惰性，并且 Haskell 并没有像上面那样通过将数据附加到可变列表来真正计算最终列表。也许 Python 的 yield 和生成器会更接近。尽管如此，上面的比较应该说明了基本机制。

Answer 3

有了明显的身份，

[ E | P <- (xs ++ ys), Q ]  ===  [ E | P <- xs, Q ] ++ [ E | P <- ys, Q ]

[ x | xs <- [E], x <- xs ]  ===  [ x | x <- E ]

[ x | x <- [E] ]  ===  [E]

我们可以跟着代码走，

concat        [[1,2,3],     [4], [5]]
 = {- by definition of `concat` -}
   [x | xs <- [[1,2,3],     [4], [5]], x <- xs]
 = {- by definition of `++`     -}
   [x | xs <- [[1,2,3]] ++ [[4], [5]], x <- xs]
 = {- by the first identity     -}
   [x | xs <- [[1,2,3]], x <- xs] ++ [x | xs <- [[4], [5]],  x <- xs]
 = {- by the second identity    -}
   [x | x <-   [1,2,3]          ] ++ [x | xs <- [[4], [5]],  x <- xs]
 = {- by definition of `++`     -}
   [x | x <-   [1,2,3]          ] ++ [x | xs <- [[4]] ++ [[5]], x <- xs]
 = {- by the first identity     -}
   [x | x <-   [1,2,3]] ++ [x | xs <- [[4]], x <- xs] ++ [x | xs <- [[5]], x <- xs]
 = {- by the second identity    -}
   [x | x <-   [1,2,3]] ++ [x | x <-   [4]          ] ++ [x | x <-   [5]          ]
 = {- and by the third          -}
   [x | x <-   [1,2,3]] ++ [            4           ] ++ [            5           ]
 = {- repeating as before       -}
   [x | x <- [1]] ++ [x | x <- [2]] ++ [x | x <- [3]] ++ [4] ++ [     5           ]
 = {- by the third identity     -}
   [          1 ] ++ [          2 ] ++ [          3 ] ++ [4] ++ [     5           ]
 = {- by definition of `++`     -}
   [          1   ,             2   ,             3   ,   4  ,        5           ]

因此concat，当应用于列表的列表时，具有“打开”并消除其中内部括号的效果。

在这个过程中我们还发现了另一个身份，

[ x | x <- Q ]  ===  Q

从上面的那些和 ++ 的属性得出，其中

[A,B,C,...,Z]  ===  [A] ++ [B] ++ [C] ++ ... ++ [Z]

另请参阅：

An introduction to the theory of lists。技术专着 PRG-56，R.S。伯德 1986.

我正在努力理解如何在 Haskell 中读取 concat

I am struggling to understand how concat is read in Haskell

haskell

list-comprehension

list

concatenation