6

haskellには、次のようなリスト内包表記があります。

sq = [(x,y,z) | x <- v, y <- v, z <- v, x*x + y*y == z*z, x < y, y < z]
    where v = [1..]

しかし、試してみるとtake 10 sq、フリーズするだけです...複数の無限の範囲を処理する方法はありますか？

ありがとう

4

4 に答える 4

6

In addition to the other answers explaining the problem, here is an alternative solution, generalized to work with level-monad and stream-monad that lend themselves for searches over infinite search spaces (It is also compatible with the list monad and logict, but those won't play nicely with infinite search spaces, as you already found out):

{-# LANGUAGE MonadComprehensions #-}

module Triples where

import Control.Monad

sq :: MonadPlus m => m (Int, Int, Int)
sq = [(x, y, z) | x <- v, y <- v, z <- v, x*x + y*y == z*z, x < y, y < z]
    where v = return 0 `mplus` v >>= (return . (1+))

Now, for a fast breadth first search:

*Triples> :m +Control.Monad.Stream
*Triples Control.Monad.Stream> take 10 $ runStream sq
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20),(7,24,25),
(15,20,25),(10,24,26),(20,21,29)]

Alternatively:

*Triples> :m +Control.Monad.Levels
*Triples Control.Monad.Levels> take 5 $ bfs sq   -- larger memory requirements
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17)]
*Triples Control.Monad.Levels> take 5 $ idfs sq  -- constant space, slower, lazy
[(3,4,5),(5,12,13),(6,8,10),(7,24,25),(8,15,17)]
于 2013-03-20T00:47:10.547 に答える
5

concatMapリスト内包表記は、関数のネストされたアプリケーションに変換されます。

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f xs = concat (map f xs)

concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss

-- Shorter definition:
--
-- > concat = foldr (++) []

あなたの例はこれと同等です：

sq = concatMap (\x -> concatMap (\y -> concatMap (\z -> test x y z) v) v) v
    where v = [1..]
          test x y z = 
              if x*x + y*y == z*z
              then if x < y
                   then if y < z
                        then [(x, y, z)]
                        else []
                   else []
              else []

これは基本的に「ネストされたループ」アプローチです。リストのすべての要素を の値として試すまで、最初に を試しx = 1, y = 1, z = 1、次に に移動します。そうして初めて、 との組み合わせを試すことができます。x = 1, y = 1, z = 2zy = 2

しかし、もちろん問題はわかります。リストは無限であるため、 を試す値が不足することはありませんz。したがって、この組み合わせ(3, 4, 5)は無限に多くの他の組み合わせの後にしか発生しません。これが、コードが永遠にループする理由です。

これを解決するには、よりスマートな方法でトリプルを生成する必要があります。これにより、考えられるあらゆる組み合わせに対して、ジェネレーターが有限数のステップの後にそれに到達するようになります。このコードを調べてください (トリプルではなく、ペアのみを処理します)。

-- | Take the Cartesian product of two lists, but in an order that guarantees
-- that all combinations will be tried even if one or both of the lists is 
-- infinite:
cartesian :: [a] -> [b] -> [(a, b)]
cartesian [] _ = []
cartesian _ [] = []
cartesian (x:xs) (y:ys) = 
    [(x, y)] ++ interleave3 vertical horizontal diagonal
        where 
          -- The trick is to split the problem into these four pieces:
          --
          -- |(x0,y0)| (x0,y1) ... horiz
          -- +-------+------------
          -- |(x1,y0)| .
          -- |   .   |  .
          -- |   .   |   .
          -- |   .   |    . 
          --   vert         diag
          vertical = map (\x -> (x,y)) xs
          horizontal = map (\y -> (x,y)) ys
          diagonal = cartesian xs ys


interleave3 :: [a] -> [a] -> [a] -> [a]
interleave3 xs ys zs = interleave xs (interleave ys zs)

interleave :: [a] -> [a] -> [a]
interleave xs [] = xs
interleave [] ys = ys
interleave (x:xs) (y:ys) = x : y : interleave xs ys

このコードを理解するには (そして、私が失敗した場合は修正してください!) 、無限集合の数え方に関するこのブログ エントリを見てください。特に 4 番目の図を見てください。この関数は、その「ジグザグ」に基づくアルゴリズムです!

これを使用して単純なバージョンを試しましたsq。ほぼ瞬時に見つかります(3,4,5)が、他の組み合わせに到達するには非常に時間がかかります（少なくともGHCIでは）。しかし、ここから得られる重要な教訓は次のとおりだと思います。

  1. リスト内包表記は、ネストされた無限リストではうまく機能しません。
  2. リスト内包表記をいじるのに時間をかけすぎないでください。map、 、 などの関数でできることはすべてfilter、リスト ライブラリconcatMapには他にも便利な関数がたくさんあるので、そちらに集中してください。
于 2013-03-20T00:39:43.630 に答える
1

述語が満たされないため、コードがフリーズします。
なんで ？

理解する述語のない例を見てみましょう。 

>>> let v = [1..] in take 10 $ [ (x, y, z) | x <- v,  y <- v, z <- v ] 
[(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(1,1,6),(1,1,7),(1,1,8),(1,1,9),(1,1,10)]

ご覧のとおり、z の上昇が止まらないため、x と y は常に 1 と評価されます。
次に、述語はできません。

回避策はありますか?

「ネストされたリスト」の理解を試してください。 

>>> [[ fun x y | x <- rangeX, predXY] | y  <- rangeY, predY ]

または、次を使用してアクティブ化できる並列リスト内包表記、 

>>> :set -XParallelListComp

ドキュメントの検索

于 2013-03-19T22:04:06.240 に答える
0

これは可能ですが、番号を生成する順序を考え出す必要があります。以下は、必要な数値を生成します。テストは、 are および 同様に for (一度決定され、バインドされている) のみを生成することでx < y置き換えることができることに注意してください。y>xzxy

[(x, y, z) | total <- [1..]
           , x <- [1..total-2]
           , y <- [x..total-1]
           , z <- [total - x - y]
           , x*x + y*y == z*z]
于 2013-03-19T21:40:16.883 に答える