在 Haskell 中，列表理解的内部工作原理是什么？
In Haskell what are the inner workings of list comprehension?
我是 Haskell 的新手，正在看这个 post：Cartesian product of 2 lists in Haskell。
答案中有这段代码：
cartProd xs ys = [(x,y) | x <- xs, y <- ys]
这两个列表：
xs = [1,2,3]
ys = [4,5,6]
会产生
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
如果我没有看到这个结果，我会假设它会返回
[(1,4),(2,5),(3,6)]
因为它会同时遍历两个列表。
但现在 - 对于我更了解的编程语言 - 看起来像是用于遍历矩阵的双 for 循环：
for (int x = 1; x < 4; x++)
for(int y = 4; y < 7; y++)
//make tuple (x,y)
是什么导致列表理解以这种方式运行？
此 introduction 解释了列表理解的 语法 。基本上可以说每个 x <- list 都意味着一个额外的嵌套“for”循环来生成元组并且每个谓词都被简单地测试。因此表达式：
[(x,y) | x <- xs, even x, y <- ys, even 3*y-div x 2]
将以命令式语言翻译为：
for (var x : xs) {
if(even(x)) {
for(var y : ys) {
if(even(3*y-x/2)) {
yield (x,y)
}
}
}
yield 是有时与协程一起使用的关键字。此外，对于 yield 的评估是延迟完成的。例如，这可以生成 all 偶数整数：
[x|x <-[2..],even x]
列出 monad
为了从根本上理解列表理解，需要知道 Monads 是什么。每个列表理解都可以翻译成一个 list monad。例如你的例子被翻译成：
do x <- xs
(do y <- ys
return (x,y))
这又是语法糖：
xs >>= (\x -> (ys >>= \y -> return (x,y)))
monad 是函数式编程中的一个重要概念（最好阅读维基百科页面），因为它有点难以掌握。有时说 monads 就像墨西哥卷饼，....
一旦您或多或少地了解了 monad：monad 是一种类型 class，带有 return 语句和 >>= 通道语句。现在内部的 return 语句很简单：
return x = [x]
所以这意味着每次设置 x 和 y 时，您将创建一个元组 (x,y) 和 return 作为单例列表：因此 [(x,y)]。现在“绑定”运算符 >>= 需要将 ys 和 \y -> return (x,y)“粘合”在一起。这是通过将其实现为：
(>>=) xs f = concat $ map f xs
换句话说，你做一个映射并连接映射的结果。
现在如果考虑未加糖表达式的第二部分：
ys >>= \y -> return (x,y)
这意味着对于给定的 x（我们现在抽象掉），我们将把 ys 中的每个元素映射到一个元组 (x,y) 和 return 中。因此，我们将生成一个列表列表，每个列表都是一个包含元组的单例。像（如果ys=[1,2]）：
[[(x,1)],[(x,2)]]
现在>>=还会concat变成：
\x -> [(x,1),(x,2)]
到现在为止，我们已经将 x 抽象掉了（假设它是一个）。但是现在我们可以使用该表达式的第一部分：
xs >>= \x -> [(x,1),(x,2)]
如果xs=[3,5]，表示我们将再次创建列表：
[[(3,1),(3,2)],[(5,1),(5,2)]]
并在连接之后：
[(3,1),(3,2),(5,1),(5,2)]
这是我们期望的：
[(x,y)|x<-[3,5],y<-[1,2]]
引用 Haskell 报告，列表理解的评估如下：
[ e | True ] = [e]
[ e | q ] = [ e | q, True ]
[ e | b, Q ] = if b then [ e | Q ] else []
[ e | p <- l, Q ] = let ok p = [ e | Q ]
ok _ = []
in concatMap ok l
[ e | let decls, Q ] = let decls in [ e | Q ]
在你的情况下，相关部分是，因为模式 p 只是一个变量 x:
[ e | x <- l, Q ] = concatMap (\x -> [ e | Q ]) l
更具体地说，理解 [(x,y) | x <- xs, y <- ys] 被翻译成
concatMap (\x -> [(x,y) | y <- ys]) xs
根据 concatMap
的定义
concat (map (\x -> [(x,y) | y <- ys]) xs)
让我们用具体值代替 xs,ys:
concat (map (\x -> [(x,y) | y <- [4,5,6]]) [1,2,3])
正在应用map：
concat [ [(1,y) | y <- [4,5,6]]
, [(2,y) | y <- [4,5,6]]
, [(3,y) | y <- [4,5,6]] ]
评估内部列表理解：（这些可以使用上面的法则再次翻译，但我会缩短）
concat [ [(1,4),(1,5),(1,6)]
, [(2,4),(2,5),(2,6)]
, [(3,4),(3,5),(3,6)] ]
通过连接上面的列表我们得到结果，
[ (1,4),(1,5),(1,6)
, (2,4),(2,5),(2,6)
, (3,4),(3,5),(3,6) ]
请注意，GHC 还作为 Haskell 扩展实现了所谓的 并行列表理解 ，它确实按您预期的方式运行：
> :set -XParallelListComp
> [(x,y)| x<-[1,2,3] | y <-[4,5,6]]
[(1,4),(2,5),(3,6)]
在内部，他们使用 zip（或者更确切地说，zipWith）函数。
列表理解语法背后的思想来自数学set-builder notation。
在数学中，可以这样写：
{ (x, y) | x ∈ xs, y ∈ ys }
表示“形式为 (x, y) 的所有元素的集合，其中 x 是集合 xs 的一个元素，y 是集合 ys 的一个元素”。
现在我们想把这个集合构建器的想法变成编程语言的“列表构建器”语法。所以我们想要这个：
[ (x, y) | x <- xs, y <- ys ]
意思是“包含形式为 (x, y) 的所有元素的列表，其中 x 是从 xs 获得的元素，y 是从 ys 获得的元素”。
显然，如果此列表表示法生成列表 [(1,4),(2,5),(3,6)]（当 xs = [1, 2, 3] 和 ys = [4, 5, 6] 时），它就不会是所需形式的所有对：(1, 6) 是可以从 xs 获得的元素与可以从 ys 获得的元素配对，但它不在您的列表中。
所以对“是什么导致列表推导式以这种方式运行？”的真正老生常谈的答案。是编程以这种方式行事，因为提出它的人希望它以这种方式行事。
您可以通过多种不同的方式对这种行为进行编程。您可以（正如 OP 所注意到的那样）使用嵌套循环，或者您可以使用 map 和 concat 之类的函数，或者您可以将 Monad 实例用于列表等。因此，您可以翻译列表理解语法中的任何一个，以证明列表理解是“真正的单子”或“真正的嵌套循环”或其他任何东西。
但从根本上说，列表推导是组合的而不是压缩的，因为语言设计者故意选择语法来表示，以便它有点像数学中的集合构建器符号1。 “x 保持不变，而 y 递增”不仅仅是实现的一个有趣的怪癖，这个实现是 选择 专门用来做到这一点的。如果有一些替代宇宙，其中列表 monad（或嵌套循环等）对于此目的没有用，列表推导不会在该宇宙中产生不同的结果，它们将以其他方式实现以产生相同的结果。
1 列表理解语法和集合生成器符号之间存在显着差异，尽管它们看起来很相似。根本区别在于使用列表而不是集合。一个元素要么在集合中，要么不在集合中，但列表包含特定索引处的元素（包括在多个索引处包含给定元素的可能性）。
所以列表理解语法必须定义 顺序 它会产生它的元素（以及它会产生多少元素），这使得列表理解从根本上讲 enumeration，而集合构建器符号从根本上讲是关于 membership。集合生成器符号 { (x, y) | x ∈ xs, y ∈ ys } 实际上是在说“你可以通过检查 x ∈ xs 和 y ∈ ys 来回答给定的 (x, y) 是否在我们正在构建的集合中”，而列表理解 [ (x, y) | x <- xs, y <- ys ] 是说“您可以通过枚举 xs 来枚举我们正在构建的列表的元素，然后对于每个元素也枚举 ys”
我是 Haskell 的新手，正在看这个 post：Cartesian product of 2 lists in Haskell。
答案中有这段代码：
cartProd xs ys = [(x,y) | x <- xs, y <- ys]
这两个列表：
xs = [1,2,3]
ys = [4,5,6]
会产生
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
如果我没有看到这个结果，我会假设它会返回
[(1,4),(2,5),(3,6)]
因为它会同时遍历两个列表。
但现在 - 对于我更了解的编程语言 - 看起来像是用于遍历矩阵的双 for 循环：
for (int x = 1; x < 4; x++)
for(int y = 4; y < 7; y++)
//make tuple (x,y)
是什么导致列表理解以这种方式运行？
此 introduction 解释了列表理解的 语法 。基本上可以说每个 x <- list 都意味着一个额外的嵌套“for”循环来生成元组并且每个谓词都被简单地测试。因此表达式：
[(x,y) | x <- xs, even x, y <- ys, even 3*y-div x 2]
将以命令式语言翻译为：
for (var x : xs) {
if(even(x)) {
for(var y : ys) {
if(even(3*y-x/2)) {
yield (x,y)
}
}
}
yield 是有时与协程一起使用的关键字。此外，对于 yield 的评估是延迟完成的。例如，这可以生成 all 偶数整数：
[x|x <-[2..],even x]
列出 monad
为了从根本上理解列表理解，需要知道 Monads 是什么。每个列表理解都可以翻译成一个 list monad。例如你的例子被翻译成：
do x <- xs
(do y <- ys
return (x,y))
这又是语法糖：
xs >>= (\x -> (ys >>= \y -> return (x,y)))
monad 是函数式编程中的一个重要概念（最好阅读维基百科页面），因为它有点难以掌握。有时说 monads 就像墨西哥卷饼，....
一旦您或多或少地了解了 monad：monad 是一种类型 class，带有 return 语句和 >>= 通道语句。现在内部的 return 语句很简单：
return x = [x]
所以这意味着每次设置 x 和 y 时，您将创建一个元组 (x,y) 和 return 作为单例列表：因此 [(x,y)]。现在“绑定”运算符 >>= 需要将 ys 和 \y -> return (x,y)“粘合”在一起。这是通过将其实现为：
(>>=) xs f = concat $ map f xs
换句话说，你做一个映射并连接映射的结果。
现在如果考虑未加糖表达式的第二部分：
ys >>= \y -> return (x,y)
这意味着对于给定的 x（我们现在抽象掉），我们将把 ys 中的每个元素映射到一个元组 (x,y) 和 return 中。因此，我们将生成一个列表列表，每个列表都是一个包含元组的单例。像（如果ys=[1,2]）：
[[(x,1)],[(x,2)]]
现在>>=还会concat变成：
\x -> [(x,1),(x,2)]
到现在为止，我们已经将 x 抽象掉了（假设它是一个）。但是现在我们可以使用该表达式的第一部分：
xs >>= \x -> [(x,1),(x,2)]
如果xs=[3,5]，表示我们将再次创建列表：
[[(3,1),(3,2)],[(5,1),(5,2)]]
并在连接之后：
[(3,1),(3,2),(5,1),(5,2)]
这是我们期望的：
[(x,y)|x<-[3,5],y<-[1,2]]
引用 Haskell 报告，列表理解的评估如下：
[ e | True ] = [e]
[ e | q ] = [ e | q, True ]
[ e | b, Q ] = if b then [ e | Q ] else []
[ e | p <- l, Q ] = let ok p = [ e | Q ]
ok _ = []
in concatMap ok l
[ e | let decls, Q ] = let decls in [ e | Q ]
在你的情况下，相关部分是，因为模式 p 只是一个变量 x:
[ e | x <- l, Q ] = concatMap (\x -> [ e | Q ]) l
更具体地说，理解 [(x,y) | x <- xs, y <- ys] 被翻译成
concatMap (\x -> [(x,y) | y <- ys]) xs
根据 concatMap
concat (map (\x -> [(x,y) | y <- ys]) xs)
让我们用具体值代替 xs,ys:
concat (map (\x -> [(x,y) | y <- [4,5,6]]) [1,2,3])
正在应用map：
concat [ [(1,y) | y <- [4,5,6]]
, [(2,y) | y <- [4,5,6]]
, [(3,y) | y <- [4,5,6]] ]
评估内部列表理解：（这些可以使用上面的法则再次翻译，但我会缩短）
concat [ [(1,4),(1,5),(1,6)]
, [(2,4),(2,5),(2,6)]
, [(3,4),(3,5),(3,6)] ]
通过连接上面的列表我们得到结果，
[ (1,4),(1,5),(1,6)
, (2,4),(2,5),(2,6)
, (3,4),(3,5),(3,6) ]
请注意，GHC 还作为 Haskell 扩展实现了所谓的 并行列表理解 ，它确实按您预期的方式运行：
> :set -XParallelListComp
> [(x,y)| x<-[1,2,3] | y <-[4,5,6]]
[(1,4),(2,5),(3,6)]
在内部，他们使用 zip（或者更确切地说，zipWith）函数。
列表理解语法背后的思想来自数学set-builder notation。
在数学中，可以这样写：
{ (x, y) | x ∈ xs, y ∈ ys }
表示“形式为 (x, y) 的所有元素的集合，其中 x 是集合 xs 的一个元素，y 是集合 ys 的一个元素”。
现在我们想把这个集合构建器的想法变成编程语言的“列表构建器”语法。所以我们想要这个：
[ (x, y) | x <- xs, y <- ys ]
意思是“包含形式为 (x, y) 的所有元素的列表，其中 x 是从 xs 获得的元素，y 是从 ys 获得的元素”。
显然，如果此列表表示法生成列表 [(1,4),(2,5),(3,6)]（当 xs = [1, 2, 3] 和 ys = [4, 5, 6] 时），它就不会是所需形式的所有对：(1, 6) 是可以从 xs 获得的元素与可以从 ys 获得的元素配对，但它不在您的列表中。
所以对“是什么导致列表推导式以这种方式运行？”的真正老生常谈的答案。是编程以这种方式行事，因为提出它的人希望它以这种方式行事。
您可以通过多种不同的方式对这种行为进行编程。您可以（正如 OP 所注意到的那样）使用嵌套循环，或者您可以使用 map 和 concat 之类的函数，或者您可以将 Monad 实例用于列表等。因此，您可以翻译列表理解语法中的任何一个，以证明列表理解是“真正的单子”或“真正的嵌套循环”或其他任何东西。
但从根本上说，列表推导是组合的而不是压缩的，因为语言设计者故意选择语法来表示，以便它有点像数学中的集合构建器符号1。 “x 保持不变，而 y 递增”不仅仅是实现的一个有趣的怪癖，这个实现是 选择 专门用来做到这一点的。如果有一些替代宇宙，其中列表 monad（或嵌套循环等）对于此目的没有用，列表推导不会在该宇宙中产生不同的结果，它们将以其他方式实现以产生相同的结果。
1 列表理解语法和集合生成器符号之间存在显着差异，尽管它们看起来很相似。根本区别在于使用列表而不是集合。一个元素要么在集合中，要么不在集合中，但列表包含特定索引处的元素（包括在多个索引处包含给定元素的可能性）。
所以列表理解语法必须定义 顺序 它会产生它的元素（以及它会产生多少元素），这使得列表理解从根本上讲 enumeration，而集合构建器符号从根本上讲是关于 membership。集合生成器符号 { (x, y) | x ∈ xs, y ∈ ys } 实际上是在说“你可以通过检查 x ∈ xs 和 y ∈ ys 来回答给定的 (x, y) 是否在我们正在构建的集合中”，而列表理解 [ (x, y) | x <- xs, y <- ys ] 是说“您可以通过枚举 xs 来枚举我们正在构建的列表的元素，然后对于每个元素也枚举 ys”