在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时，它只是冻结…有办法处理多个无限范围吗?
谢谢
除了解释问题的其他答案之外，这里还有一个替代解决方案，推广到level-monad和stream-monad，它们可以在无限搜索空间上进行搜索(它也与列表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)]
列表推导式被转换为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 = 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
要理解这段代码(如果我弄乱了，请修复它!)，请查看这篇关于如何计算无限集的博客文章，特别是第四个图-该函数是基于"之字形"的算法!
我只是尝试了一个简单的版本，你的sq使用这个;它几乎立即找到(3,4,5)，但随后需要很长时间才能找到任何其他组合(至少在GHCI中)。但我认为从中吸取的关键教训是:
- 列表推导式对于嵌套的无限列表不能很好地工作。
- 不要花太多时间在列表推导上。它们所能做的一切，像
map、filter和concatMap这样的函数都能做——此外，列表库中还有许多其他有用的函数，所以集中精力吧。
你的代码冻结了，因为你的谓词永远不会被满足。
为什么?
让我们举一个没有任何谓词的例子来理解。
>>> 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
查找文档
这是可能的，但是您必须提出一个生成数字的顺序。下面的代码生成你想要的数字;请注意，x < y测试可以被替换为只生成>x的y, z也是类似的(一旦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]