如何在列表解析中有多个无限范围？ [英] How to have multiple infinite ranges in list comprehensions?

问题描述

在Haskell中，我有这样的列表理解：

  sq = [（x，y，z）| x <-v，y <-v，z <-v，x * x + y * y == z * z，x < y，y< z] 
其中v = [1 ..] 
  

然而，当我尝试 10平方，它只是冻结...
是否有办法处理多个无限范围？

谢谢

解决方案

除了解释问题的其他解答外，下面是一个替代解决方案，推广到与 level-monad 和 stream-monad 适用于无限搜索空间的搜索（它也与列表单元和 logict ，但那些无法与无限的搜索空间一起玩，就像y一样ou已经发现）：

  { - ＃LANGUAGE MonadComprehensions＃ - } 
 
模块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>取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）] 
 code> 

或者：



  *三元组> ：m + Control.Monad.Levels 
 * Triples Control.Monad.Levels>采取5 $ bfs sq  - 更大的内存要求
 [（3,4,5），（6,8,10），（5,12,13），（9,12,15），（8， 15,17）] 
 * Triples Control.Monad.Levels> 5 $ idfs sq  - 恒定空间，较慢，懒
 [（3,4,5），（5,12,13），（6,8,10），（7,24,25）， （8,15,17）] 
  




In haskell I have a list comprehension like this:

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

However when I try take 10 sq, it just freezes... Is there a way to handle multiple infinite ranges?

Thanks

解决方案

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

这篇关于如何在列表解析中有多个无限范围？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！