问题描述
在Haskell中,我有这样的列表理解: sq = [(x,y,z)| x 其中v = [1 ..]
然而,当我尝试 10平方
,它只是冻结...
是否有办法处理多个无限范围?
谢谢
除了解释问题的其他解答外,下面是一个替代解决方案,推广到与和适用于无限搜索空间的搜索(它也与列表单元和,但那些无法与无限的搜索空间一起玩,就像y一样ou已经发现):
{ - #LANGUAGE MonadComprehensions# - }
模块Triples where
import Control.Monad
sq :: MonadPlus m => m(Int,Int,Int)
sq = [(x,y,z)| x 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)]
这篇关于如何在列表解析中有多个无限范围?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!