如何在列表解析中有多個無限範圍？

Question

在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，它只是凍結... 有沒有辦法來處理多個無限的範圍？

感謝

Answer 1

這是可能的，但你必須要拿出在其中生成的數字的順序。以下產生你想要的數字;注意：x < y測試可以通過生成唯一y這是z>x和類似的（這是確定的，一旦x和y綁定）來代替：

[(x, y, z) | total <- [1..] 
      , x <- [1..total-2] 
      , y <- [x..total-1] 
      , z <- [total - x - y] 
      , x*x + y*y == z*z] 

Answer 2

你的代碼凍結，因爲你的謂語將永遠不會得到滿足。
爲什麼？

讓我們舉一個沒有任何謂詞的例子來理解。

>>> 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)] 

正如你所看到的，x和y總會被評估爲1，因爲z永遠不會停止上升。
然後你的謂詞不能。

任何解決方法？

嘗試「嵌套列表」的理解。

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

或並行列表解析其可以使用被激活，

>>> :set -XParallelListComp 

查找在doc

Answer 3

列表解析被翻譯成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 (++) [] 

你的例子是等價的t對此：

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 = 2等等，直到它將所有列表元素都作爲z的值;只有這樣才能繼續嘗試與y = 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 

要理解這個代碼（並修復它，如果我搞砸了！）看this blog entry on how to count infinite sets，並在第四卦特別-功能是基於那個「曲折」的算法！

我剛剛試過你的sq這個簡單版本;它幾乎立即找到(3,4,5)，但是需要很長時間才能到達任何其他組合（至少在GHCI中）。但我認爲，要從中取得的主要經驗教訓是：

1. 列表解析對嵌套的無限列表不起作用。
2. 不要花太多時間玩弄列表解析。他們所能做的一切，像map,filter和concatMap這樣的功能都可以做，而且the list library還有很多其他有用的功能，所以請將精力集中在這一點上。

Answer 4

除了其他的答案解釋的問題，這裏是一個替代的解決方案，推廣與level-monad和stream-monad是借給自己超過無限的搜索空間的搜索工作（這也是與列表單子和logict兼容，但那些不會無限的搜索空間發揮很好，因爲你已經發現了）：

{-# 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+)) 

現在，對於一個快速廣度優先搜索：

*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)] 

或者：

*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)]