Haskell：列表理解谓词顺序

Question

在网上阅读了 List Comprehensions 的 Haskell 语法后，我感觉谓词总是在最后。例如：

[(x,y) | x <- [1..10000], y <- [1..100], x==2000, odd y]

但下一行实现了相同的结果：

[(x,y) | x <- [1..10000], x==2000, y <- [1..100], odd y]

通常情况下，我会将此视为顺序无关紧要的提示，然后就可以完成了。然而，这是一个来自旧考试的问题，问题的答案是虽然结果可能相同，但它们的计算方式可能不同。

我假设这是真的，但我在网上找不到任何相关信息。 所以我的问题是：两个列表理解之间的计算有何不同？为什么？列表理解是某种我不知道的语法糖形式吗？

Answer 1

它们的不同之处在于产生多少中介results/lists。

你可以用一些 trace 来形象化 - 请注意，我对此做了一些修改以给出合理的结果 - 我还用 () 替换了 return 值以使其更清楚：

comprehension1 = [ () | x <- [1..3], trace' 'x' x, y <- [1..3], trace' 'y' y, x==2, odd y]
comprehension2 = [ () | x <- [1..3], trace' 'x' x, x==2, y <- [1..3], trace' 'y' y, odd y]

trace' :: Show a => Char -> a -> Bool
trace' c x = trace (c : '=' : show x) True

评价如下：

λ> comprehension1
x=1
y=1
y=2
y=3
x=2
y=1
[()y=2
y=3
,()x=3
y=1
y=2
y=3
]
λ> comprehension2
x=1
x=2
y=1
[()y=2
y=3
,()x=3
]

现在你注意到什么了吗？

显然，在第一个示例中，x=1,2,3 和 y=1,2,3 的每个 (x,y) 对都是在应用过滤器之前生成的。

但在第二个示例中，y仅在 x=2 时生成 - 因此您可以说它更好/性能更高

Answer 2

你可以把列表理解想象成

[(x,y) | x <- [1..10000], y <- [1..100], x==2000, odd y]

对应命令式pseudo-code

for x in [1..10000]:
    for y in [1..100];
        if x == 2000:
            if odd y:
                yield (x,y)

和

[(x,y) | x <- [1..10000], x==2000, y <- [1..100], odd y]

相当于

for x in [1..10000]:
    if x == 2000;
        for y in [1..100]:
            if odd y:
                yield (x,y)

具体来说，将列表理解传递给 mapM_ print 之类的东西在操作上与在命令式版本中将 yield 替换为 print 相同。

显然，在可能的情况下，"float" 守卫/if 出发电机/for 几乎总是更好。（罕见的例外是生成器实际上是一个空列表，并且保护条件的计算成本很高。）

Haskell：列表理解谓词顺序

Haskell: List comprehension predicate order

haskell

list-comprehension