我想迭代 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 元组？
有一个单子，欧米茄。
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 理解与 Thomas 之类的方法一起使用，或者只是另一种方法mfilter（在这种情况下限制为b /= c）。
列表推导是解决此类问题的好方法（且简洁）。首先，您知道您希望所有(a,b,c)可能满足的组合a^2 + b^2 = c^2- 一个有用的观察是（仅考虑正数）它总是会出现a <= c && b <= c.
为了生成我们的候选列表，我们可以说crange from1到 infinity whilea和brange from one to 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)...
除了盲测之外，还有更多原则性的方法可以解决这个问题。
{- 这取决于什么是“最小的”。但是，如果首先比较元组的最大值，则这是“最小”概念的解决方案。数量，然后按它们的总和。（当我在评论中写下文本时，您可以将我的整个答案复制并粘贴到文件中。）
我们稍后会需要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)]
编辑： 我意识到有一个错误：仅仅轮换有序列表当然是不够的。解决方案必须在某个地方
rest <- concat . map (rotations (k-1)) $ kLists (k-1) n
中kLists，但随后出现重复输出的一些问题。我猜你可以弄清楚。;-) -}
这实际上取决于您所说的“最小”是什么意思，但我假设您想找到一个关于其最大元素的数字元组 - 所以(2,2)小于(1,3)（而标准的 Haskell 排序是字典顺序的）。
有包data-ordlist，它的目的是精确地处理有序列表。它的功能mergeAll（和mergeAllBy）允许您将在每个方向上排序的二维矩阵组合成一个有序列表。
首先让我们在元组上创建一个所需的比较函数：
import Data.List (find)
import Data.List.Ordered
compare2 :: (Ord a) => (a, a) -> (a, a) -> Ordering
compare2 x y = compare (max2 x, x) (max2 y, y)
where
max2 :: Ord a => (a, a) -> a
max2 (x, y) = max x y
然后使用mergeAll我们创建一个函数，该函数接受一个比较器、一个组合函数（两个参数必须是单调的）和两个排序列表。它使用该函数组合两个列表中的所有可能元素，并生成一个结果排序列表：
mergeWith :: (b -> b -> Ordering) -> (a -> a -> b) -> [a] -> [a] -> [b]
mergeWith cmp f xs ys = mergeAllBy cmp $ map (\x -> map (f x) xs) ys
使用此函数，生成根据最大值排序的元组非常简单：
incPairs :: [(Int,Int)]
incPairs = mergeWith compare2 (,) [1..] [1..]
它的前 10 个元素是：
> take 10 incPairs
[(1,1),(1,2),(2,1),(2,2),(1,3),(2,3),(3,1),(3,2),(3,3),(1,4)]
当我们（例如）寻找平方和等于 65 的第一对时：
find (\(x,y) -> x^2+y^2 == 65) incPairs
我们得到正确的结果(4,7)（与(1,8)使用字典顺序相反）。
这个答案是针对未知谓词的更一般的问题。如果谓词已知，则可能有更有效的解决方案，就像其他人已经列出了基于您不需要为给定 c 迭代所有 Int 的知识的解决方案一样。
在处理无限列表时，您需要执行广度优先搜索解决方案。列表推导仅提供深度优先搜索，这就是为什么您永远无法在原始代码中找到解决方案。
counters 0 xs = [[]]
counters n xs = concat $ foldr f [] gens where
gens = [[x:t | t <- counters (n-1) xs] | x <- xs]
f ys n = cat ys ([]:n)
cat (y:ys) (x:xs) = (y:x): cat ys xs
cat [] xs = xs
cat xs [] = [xs]
main = print $ take 10 $ filter p $ counters 3 [1..] where
p [a,b,c] = a*a + b*b == c*c
counters为指定数字范围（包括无限范围）中的值生成所有可能的计数器。
首先，我们获得一个有效计数器组合的生成器列表——对于每个允许的数字，将其与所有允许的较小计数器组合组合。这可能会导致生成器产生无限数量的组合。因此，我们需要从每个生成器中平均借用。
gens生成器列表也是如此。将其视为以一位数字开头gens !! 0的所有计数器的列表：是以 开头的所有计数器的列表1，以 开头gens !! 1的所有计数器的列表2，等等。
为了均匀地从每个生成器借用，我们可以转置生成器列表 - 这样我们将获得生成器的第一个元素列表，然后是生成器的第二个元素列表，等等。
由于生成器列表可能是无限的，我们无法转置生成器列表，因为我们可能永远无法查看任何生成器的第二个元素（对于无限数量的数字，我们将拥有无限数量的生成器） . 因此，我们“对角地”枚举生成器中的元素——从第一个生成器中获取第一个元素；然后从第一个生成器中获取第二个元素，从第二个生成器中获取第一个元素；然后从第一个生成器中获取第三个元素，从第二个生成器中获取第二个元素，从第三个生成器中获取第一个元素，等等。这可以通过使用函数折叠生成器列表来完成，该函数f将两个列表压缩在一起 - 一个列表是生成器，另一个是已经压缩的生成器-，[]:到头。这几乎是zipWith (:) ys ([]:n)- 不同之处在于如果 n 或 ys 比另一个短，我们不会删除另一个列表的其余部分。请注意，折叠zipWith (:) ys n将是转置。
如果“最小”定义为 x+y+z，我认为这是最简单的解决方案，因为在积分值毕达哥拉斯三角形空间中找到第一个解决方案后，无限列表中的下一个解决方案会更大。
take 1 [(x,y,z) | y <- [1..], x <- [1..y], z <- [1..x], z*z + x*x == y*y]
-> [(4,5,3)]
它有一个很好的特性，即它只返回每个对称唯一的解决方案一次。x 和 z 也是无限的，因为 y 是无限的。
这不起作用，因为 x 的序列永远不会结束，因此您永远不会得到 y 的值，更不用说 z。最右边的生成器是最内层的循环。
take 1 [(z,y,x)|z <- [1..],y <- [1..],x <- [1..],x*x + y*y == z*z]
这是另一种解决方案，可能是“最小”的另一个稍微不同的想法。我的命令只是“所有最大元素为 N 的元组都排在所有最大元素为 N+1 的元组之前”。我写了对和三元组的版本：
gen2_step :: Int -> [(Int, Int)]
gen2_step s = [(x, y) | x <- [1..s], y <- [1..s], (x == s || y == s)]
gen2 :: Int -> [(Int, Int)]
gen2 n = concatMap gen2_step [1..n]
gen2inf :: [(Int, Int)]
gen2inf = concatMap gen2_step [1..]
gen3_step :: Int -> [(Int, Int, Int)]
gen3_step s = [(x, y, z) | x <- [1..s], y <- [1..s], z <- [1..s], (x == s || y == s || z == s)]
gen3 :: Int -> [(Int, Int, Int)]
gen3 n = concatMap gen3_step [1..n]
gen3inf :: [(Int, Int, Int)]
gen3inf = concatMap gen3_step [1..]
你不能真正将它推广到 N 元组，但只要你保持同质，如果你使用数组，你就可以推广它。但我不想把我的大脑绑在那个结上。
对于这个答案，我将采用“最小”来指代元组中数字的总和。
要按顺序列出所有可能的对，您可以首先列出总和为 2 的所有对，然后列出总和为 3 的所有对，依此类推。在代码中
pairsWithSum n = [(i, n-i) | i <- [1..n-1]]
xs = concatMap pairsWithSum [2..]
Haskell 没有在不使用 Template Haskell 的情况下处理 n 元组的功能，因此要概括这一点，您必须切换到列表。
ntuplesWithSum 1 s = [[s]]
ntuplesWithSum n s = concatMap (\i -> map (i:) (ntuplesWithSum (n-1) (s-i))) [1..s-n+1]
nums n = concatMap (ntuplesWithSum n) [n..]
抱歉，我做haskell已经有一段时间了，所以我将用文字来描述它。
正如我在评论中指出的那样。不可能在无限列表中找到最小的任何东西，因为总会有一个更小的东西。
您可以做的是，采用基于流的方法获取列表并返回仅包含“有效”元素的列表，即满足条件的位置。让我们调用这个函数triangle
然后，您可以在某种程度上使用take n (triangle ...)这些n元素计算三角形列表，并从中找到最小值。