Haskell中无限列表上的燕尾迭代
我想迭代2个(或3个)无限列表，并找到满足条件的“最小”对，如下所示：
until pred [(a,b,c) | a<-as, b<-bs, c<-cs]
where pred (a,b,c) = a*a + b*b == c*c
as = [1..]
bs = [1..]
cs = [1..]以上操作不会走得太远，因为a == b == 1在整个程序运行过程中都是如此。有没有一个很好的方法来解决这个问题，比如构建无限序列[(1,1,1),(1,2,1),(2,1,1),(2,1,2),(2,2,1),(2,2,2),(2,2,3),(2,3,2),..]？
奖励:可以推广到n-tuple吗？
回答 9
Stack Overflow用户
发布于 2013-09-20 00:34:22
有一个monad可以做到这一点Omega
Prelude> let as = each [1..]
Prelude> let x = liftA3 (,,) as as as
Prelude> let x' = mfilter (\(a,b,c) -> a*a + b*b == c*c) x
Prelude> take 10 $ runOmega x'
[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15),(12,9,15),(8,15,17),(15,8,17)]使用它的应用特性，您可以将其泛化为任意元组：
quadrupels = (,,,) <$> as <*> as <*> as <*> as -- or call it liftA4但：当然，这本身并不能消除重复。它只会给你适当的对角化。也许您可以将monad comprehensions与类似Thomas的方法一起使用，或者只是使用另一个mfilter通道(在本例中，仅限于b /= c )。
Stack Overflow用户
发布于 2013-09-19 22:42:17
列表理解是解决这类问题的很好(而且简明)的方法。首先，你知道你想要所有可能满足a^2 + b^2 = c^2的(a,b,c)组合-一个有用的观察是(只考虑正数) a <= c && b <= c总是这样的。
因此，为了生成我们的候选列表，我们可以说c的范围从1到无穷大，而a和b的范围从1到c。
[(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c]]为了得到解决方案，我们只需要添加您想要的方程式作为保护：
[(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c], a*a+b*b == c*c]这很低效，但输出是正确的：
[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15)...有比盲测试更有原则的方法可以解决这个问题。
Stack Overflow用户
发布于 2013-09-19 22:10:17
{-这取决于什么是“最小”。但是这里有一个“最小”概念的解决方案，如果首先比较元组的最大值。数字，然后是它们的总和。(当我在注释中写入文本时，您可以将我的整个答案复制并粘贴到文件中。)
我们稍后将需要nub。-}
import Data.List (nub){-仅供说明:具有2元组的简单情况。-}
-- all the two-tuples where 'snd' is 'n'
tuples n = [(i, n) | i <- [1..n]]
-- all the two-tuples where 'snd' is in '1..n'
tuplesUpTo n = concat [tuples i | i <- [1..n]]{-要获得所有结果，您需要将每个元组的翻转插入到流中。但让我们稍后再做，并首先进行推广。
构建任意长度的元组有些困难，所以我们将使用列表。如果它们的长度是'k‘，我称它们为’kList‘。-}
-- just copied from the tuples case, only we need a base case for k=1 and
-- we can combine all results utilizing the list monad.
kLists 1 n = [[n]]
kLists k n = do
rest <- kLists (k-1) n
add <- [1..head rest]
return (add:rest)
-- same as above. all the klists with length k and max number of n
kListsUpTo k n = concat [kLists k i | i <- [1..n]]
-- we can do that unbounded as well, creating an infinite list.
kListsInf k = concat [kLists k i | i <- [1..]]{-下一步是循环这些列表，因为到目前为止，最大的数字总是在最后。所以我们只看所有的旋转来得到所有的结果。无可否认，在这里使用nub很笨拙，您可以改进这一点。但是如果没有它，所有元素都相同的列表就会重复k次。-}
rotate n l = let (init, end) = splitAt n l
in end ++ init
rotations k l = nub [rotate i l | i <- [0..k-1]]
rotatedKListsInf k = concatMap (rotations k) $ kListsInf k{-剩下的就是将这些列表转换成元组。这有点尴尬，因为每个n元组都是一个单独的类型。当然，这很简单。-}
kListToTuple2 [x,y] = (x,y)
kListToTuple3 [x,y,z] = (x,y,z)
kListToTuple4 [x,y,z,t] = (x,y,z,t)
kListToTuple5 [x,y,z,t,u] = (x,y,z,t,u)
kListToTuple6 [x,y,z,t,u,v] = (x,y,z,t,u,v){-一些测试：
*Main> take 30 . map kListToTuple2 $ rotatedKListsInf 2
[(1,1),(1,2),(2,1),(2,2),(1,3),(3,1),(2,3),(3,2),(3,3),(1,4),(4,1),(2,4),(4,2),(3,4),
(4,3),(4,4),(1,5),(5,1),(2,5),(5,2),(3,5),(5,3),(4,5),(5,4),(5,5),(1,6),(6,1),
(2,6), (6,2), (3,6)]
*Main> take 30 . map kListToTuple3 $ rotatedKListsInf 3
[(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,2,1),(2,1,2),(2,2,2),(1,1,3),(1,3,1),
(3,1,1),(1,2,3),(2,3,1),(3,1,2),(2,2,3),(2,3,2),(3,2,2),(1,3,3),(3,3,1),(3,1,3),
(2,3,3),(3,3,2),(3,2,3),(3,3,3),(1,1,4),(1,4,1),(4,1,1),(1,2,4),(2,4,1),(4,1,2)]编辑：我意识到有一个bug:当然，仅仅旋转有序列表是不够的。解决方案必须是这样的：
rest <- concat . map (rotations (k-1)) $ kLists (k-1) n在kLists中，但随后会出现一些重复输出的问题。我想你可以弄明白这一点。;-) -}
https://stackoverflow.com/questions/18896172
复制相似问题
腾讯云开发者
