5

私は現在、Learn You a Haskell for Great Good! を進めています。、そして第 2 章の最後から 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

2 つの単純なリスト内包表記を考えてみましょう。

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

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

それらはほとんど同じですが、2 番目のケースでは、b範囲は から1までであり、からまでaではありません。それらが何に等しいかを考えてみましょう。要点を明確にするために、値をフォーマットしました。13

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そのリストから可能なすべての値と等しくし ましょう。
    • の各値についてabそのリストから考えられるすべての値を とします。
      • (a,b)出力リストの要素です

または、言い換えると、「 のすべての可能な値について、 のすべての可能な値をa計算(a,b)しますb。」結果の順序を見ると、次のようになります。

  1. 最初の 3 つの要素でaは、 は に等しく1、 のすべての値と対になっていることがわかりますb
  2. 次の 3 つの要素でaは、 は に等しく2、 のすべての値が表示されますb
  3. 最後に、最後の 3 つの要素について、aは に等しく、3のすべての値が表示されますb

2 番目のケースでは、ほとんど同じことが起こります。しかし、最初a選択されるため、それに依存できます。したがって:b

  1. まず、aは に等しく1、 のすべての可能な値と対になっていることがわかりますbb <- [1..a]ですから、それは を意味するので、b <- [1..1]選択肢は 1 つしかありません。
  2. 1 つの要素の後、aは に等しくなり2、 のすべての可能な値と対になっていることがわかりますb。これは を意味するb <- [1..2]ので、2 つの結果が得られます。
  3. 最後に、aに等しい3ので、b <- [1..3];を選択します。これにより、3 つの結果の完全なセットが得られます。

つまり、リスト内包表記は順序付けに依存しているため、それを利用できます。それを確認する 1 つの方法は、これらのリスト内包表記をネストされたリスト内包表記に変換することを想像することです。

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

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

正しい振る舞いをするためにはa <- [1..3]、外に出なければなりません。これにより、bs が s よりも速く変化することが保証されaます。そして、うまくいけば、どのようbに に依存できるかが明確になりaます。別の翻訳 (基本的にHaskell 2010 Report で使用されているもの) は次のようになります。

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)このように書かれているのを見ると、進行中の「ネストされたループ」タイプの構造を明確にするのに役立つかもしれないと思ったので、これについて言及するだけであり、 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 に答える