4

私はhttp://learnyouahaskell.com/starting-outで（優れた）Haskellチュートリアルに従っており、直角三角形の例を試しています。

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

これを実行すると、予想どおりに取得します。

> triangles 
[(4,3,5),(3,4,5),(8,6,10),(6,8,10)]

代わりに、無限リストを使用してみます。

> let triangles = [(a,b,c) | c <- [1..], b <- [1..], a <- [1..], a^2 + b^2 == c^2]

しかし、私がそれを試してみると、次のようになります。

> take 2 triangles

...プログラムは実行され、出力なしで実行されます。私は何が間違っているのですか？Haskellsの怠惰により、最初の2つの三角形が見つかり、停止するのではないかと思いました。

4

2 に答える 2

9

さて、ここでは怠惰は問題ではありません。これは、リスト内の変数を反復する順序です。

基本的に何が起こるかです：

  1. cは1にバインドされています
  2. bは1にバインドされています
  3. aは1にバインドされています
  4. 方程式がチェックされます
  5. aは2にバインドされています
  6. 方程式がチェックされます
  7. aは3にバインドされています
  8. 方程式がチェックされます

そしてそれは永遠に続きます。

したがって、ジェネレータは、の値の反復とバインドを継続します。これは、停止してインクリメントまたは変更aする必要があることを認識していないためです。bc

したがって、よりバランスの取れた方法でタプルを生成する必要があります。

たとえば、次の方法を使用できます。

triplesN :: Int -> [(Int, Int, Int)]
triplesN n = [(i, j, n - i - j) | i <- [1..n - 2], 
                                  j <- [1..n - i - 1], i>=j, 
                                  let k = n - i - j,   j>=k]

isTriangle (a, b, c) = a^2 == b^2 + c^2

triangles = filter isTriangle $ concatMap triplesN [1..]

tripleN合計ですべての順序付けられたトリプルを生成しますn。この関数をすべての自然数にマッピングすることにより、実際にはすべての順序対のストリームを取得します。そして最後に、三角形であるトリプルのみをフィルタリングします。

行うことによって：

take 10 triangles

我々が得る：

[(5,4,3),(10,8,6),(13,12,5),(15,12,9),(17,15,8),(20,16,12),(25,24,7),(25,20,15),(26,24,10),(29,21,20)]

于 2012-11-15T11:19:04.647 に答える
6

sigfpeのブログにあるAMonadforCombinatorialSearchの記事を読むことに興味があるかもしれません。

彼は、ペナルティリストまたはPListと呼ばれる新しいモナドを定義します。これは、リストモナドに似ていますが、より複雑なソリューションに対するペナルティの概念もあります。PListsを組み合わせる場合、結果が生成される順序は、最小のペナルティ->最大のペナルティの順序です。

あなたの例では、整数に関連付けられたペナルティは整数のサイズと等しくなる可能性があり、タプルに関連付けられたペナルティはその要素のペナルティの合計です。したがって、タプル(3,4,5)には3 + 4 + 5 = 12の(5,12,13)ペナルティがあり、タプルには5 + 12 + 13=30のペナルティがあります。

リストモナドでは、生成されるタプルの順序は次のとおりです。

(1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,1,5) ...

そして、あなたは形ではないタプルを見ることは決してありません(1,1,x)。PListモナドを使用すると、生成されるタプルは次のようになります。

(1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,1,3), (1,3,1), (3,1,1), (1,2,2) ...

すべての「小さい」タプルが「大きい」タプルの前に生成されます。

あなたの特定の問題にとって、この解決策はやり過ぎですが、より複雑な問題で非常に役立つ可能性があります。

于 2012-11-15T12:18:07.717 に答える