6

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

4

4 回答 4

6

除了解释问题的其他答案之外，这里是一个替代解决方案，可以推广使用，level-monad并且stream-monad可以在无限搜索空间上进行搜索（它也与 list 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)]
于 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 = 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 中）。但我认为从中吸取的关键教训是：

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

如您所见，x 和 y 将始终被评估为 1，因为 z 永远不会停止上升。
那么你的谓词不可能。

任何解决方法？

尝试“嵌套列表”理解。 

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

或可以使用激活的并行列表理解， 

>>> :set -XParallelListComp

在文档上查找

于 2013-03-19T22:04:06.240 回答
0

这是可能的，但您必须提出生成数字的顺序。以下生成您想要的数字；请注意，可以通过仅生成is和类似 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 回答