如何在列表推导中计算相关范围？

Question

我正在通过学习你是一个很好的Haskell!,我对第2章中倒数第二个例子感到困惑.

作为一种生成表示所有直角三角形的三元组的方法,其中所有边都是小于或等于10的整数,他给出了这个定义:

rightTriangles = [ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2] 

我特别困惑的是这个事实b被绑定到一个范围从1到1的列表c,并且类似于a.如果我的理解是正确的,c将评估它所绑定的列表中的所有值,但我仍然看不到该c范围中使用的值(例如,所有值c,仅第一个c等)

如果不是太多,逐步解释这个评估的方式会很好.:)

提前致谢!

Answer 1

让我们考虑两个更简单的列表推导:

ex1 = [(a,b) | a <- [1..3], b <- [1..3]]

ex2 = [(a,b) | a <- [1..3], b <- [1..a]]

他们几乎是相同的,但是在第二种情况下,b范围从1到a,不能1到3.让我们考虑一下它们的相同之处; 我已经以这样一种方式格式化他们的价值观.

ex1 = [ (1,1), (1,2), (1,3)
      , (2,1), (2,2), (2,3)
      , (3,1), (3,2), (3,3) ]

ex2 = [ (1,1),
      , (2,1), (2,2),
      , (3,1), (3,2), (3,3) ]

在第一个例子中,列表理解绘制从元件的每一个可能的组合[1..3]和[1..3].但是既然我们谈论的是列表而不是集合,那么它所做的顺序非常重要.因此,在更详细的,是什么ex1 真正的意思是这样的:

• 让它a等于列表中的每个可能值.
  • 对于每个值a,让其b列表中的每个可能值.
    • (a,b) 是输出列表的元素

或者,改写:"为每个可能的价值a,计算(a,b)每个可能的价值b." 如果你看一下结果的顺序,就会发生这种情况:

1. 对于前三个元素,a等于1,我们看到它与每个值配对b.
2. 对于接下来的三个元素,a等于2,我们看到的每一个值b.
3. 最后,对于最后三个元素,a等于3并且我们看到了每个值b.

在第二种情况下,发生了同样的事情.但因为先a挑选,可以依靠它.从而:b

1. 首先,a等于1,我们看到它与每个可能的价值配对b.因为b <- [1..a],这意味着b <- [1..1],所以只有一个选择.
2. 在一个元素之后,a等于2,我们看到与每个可能的值配对b.现在这意味着b <- [1..2],所以我们得到两个结果.
3. 最后,a等于3,所以我们正在挑选b <- [1..3]; 这给了我们三套完整的结果.

换句话说,因为列表推导依赖于排序,所以您可以利用它.一种看待这种情况的方法是想象将这些列表推导转换为嵌套列表推导:

ex1 = concat [ [(a,b) | b <- [1..3]] | a <- [1..3] ]

ex2 = concat [ [(a,b) | b <- [1..a]] | a <- [1..3] ]

为了获得正确的行为,a <- [1..3]必须走在外面; 这确保了bs的变化速度比as 快.它希望能够明确如何b依赖a.另一种翻译(基本上是Haskell 2010报告中使用的翻译)将是:

ex1 = concatMap (\a -> [(a,b) | b <- [1..3]]) [1..3]
    = concatMap (\a -> concatMap (\b -> [(a,b)]) [1..3]) [1..3]

ex2 = concatMap (\a -> [(a,b) | b <- [1..a]]) [1..3]
    = concatMap (\a -> concatMap (\b -> [(a,b)]) [1..a]) [1..3]

同样,这使得嵌套非常明确,即使很难遵循.需要记住的是,如果a要首先进行选择,它必须位于已翻译表达式的外部,即使它位于列表理解的内部.那么完整,正式的翻译rightTriangles就是

rightTriangles =
  concatMap (\c ->
    concatMap (\b ->
      concatMap (\a ->
        if a^2 + b^2 == c^2
          then [(a,b,c)]
          else []
      ) [1..b]
    ) [1..c]
  ) [1..10]

作为旁注,另一种写作方式rightTriangles如下:

import Control.Monad (guard)

rightTriangles = do c <- [1..10]
                    b <- [1..c]
                    a <- [1..b]
                    guard $ a^2 + b^2 == c^2
                    return (a,b,c)

你可能还没有使用过do符号,当然也没有使用符号IO,所以我不是说你应该理解这一点.但是你可以阅读这些x <- list行来说"for each xin list",所以把它读作嵌套循环:

rightTriangles = do
  c <- [1..10]             -- For each `c` from `1` to `10`, ...
  b <- [1..c]              -- For each `b` from `1` to `c`, ...
  a <- [1..b]              -- For each `a` from `1` to `b`, ...
  guard $ a^2 + b^2 == c^2 -- If `a^2 + b^2 /= c^2`, then `continue` (as in C);
  return (a,b,c)           -- `(a,b,c)` is the next element of the output list.

请注意,在此解释中,continue仅跳到最内层循环的下一次迭代.你也可以把它写成

rightTriangles = do c <- [1..10]
                    b <- [1..c]
                    a <- [1..b]
                    if a^2 + b^2 == c^2
                      then return (a,b,c)
                      else [] -- or `mzero`

最后一行说"如果a^2 + b^2 == c^2,添加(a,b,c)到输出列表;否则,不添加任何内容".我只提到这一点,因为我认为看到它以这种方式编写可能有助于使"嵌套循环"类型的结构清晰,而不是因为你应该完全理解do- 阅读第2章" 了解你的哈斯克尔" :-)

Answer 2

看到你有命令式编程的经验,一个简短的答案是:类似于这个for嵌套(伪代码):

for(c = 1; c <= 10; c++) {
    for(b = 1; b <= c; b++) {
        for(a = 1; a <= b; a++) {
            if(a ^ 2 + b ^ 2 == c ^ 2) {
                list.append((a, b, c));
            }
        }
    }
}