5

我目前正在通过Learn You a Haskell for Great Good！，我对第 2 章中的倒数第二个例子感到困惑。

作为一种生成三元组的方法，所有直角三角形的所有边都是小于或等于 10 的整数，他给出了以下定义：

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

我特别困惑的b是绑定到范围从 1 到 的列表的事实c，并且与a. 如果我的理解是正确的，c将评估它绑定到的列表中的所有值，但我仍然看不到该c范围内正在使用哪个值（例如 的所有值c，只有第一个c等）

如果不是太多，逐步解释如何评估会很棒。:)

提前致谢！

4

2 回答 2

13

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

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

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

它们几乎相同，但在第二种情况下，b范围从1to a，不是1to 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要首先选择 of，它必须位于已翻译表达式的外部，即使它位于列表推导式的内部。完整的，正式的翻译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)到输出列表；否则，不添加任何内容。” 我之所以提到这一点，是因为我认为以这种方式编写它可能有助于使“嵌套循环”类型的结构变得清晰，而不是因为您在阅读Learn You A Haskelldo的第 2 章时应该完全理解 -notation :-)

于 2012-09-03T00:18:42.370 回答
6

看到你有命令式编程的经验，一个简短的回答是：类似于这个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));
            }
        }
    }
}
于 2012-09-02T23:35:06.980 回答