Haskell 中无限列表的笛卡尔积 [英] Cartesian product of infinite lists in Haskell
问题描述
我有一个用于有限列表的函数
I have a function for finite lists
> kart :: [a] -> [b] -> [(a,b)]
> kart xs ys = [(x,y) | x <- xs, y <- ys]
但是如何为无限列表实现它?我听说过康托尔和集合论.
but how to implement it for infinite lists? I have heard something about Cantor and set theory.
我还发现了一个类似的功能
I also found a function like
> genFromPair (e1, e2) = [x*e1 + y*e2 | x <- [0..], y <- [0..]]
但我不确定它是否有帮助,因为 Hugs 只提供配对而不会停止.
But I'm not sure if it helps, because Hugs only gives out pairs without ever stopping.
感谢您的帮助.
推荐答案
你的第一个定义,kart xs ys = [(x,y) |x <- xs, y <- ys]
,等价于
Your first definition, kart xs ys = [(x,y) | x <- xs, y <- ys]
, is equivalent to
kart xs ys = xs >>= (x ->
ys >>= (y -> [(x,y)]))
哪里
(x:xs) >>= g = g x ++ (xs >>= g)
(x:xs) ++ ys = x : (xs ++ ys)
是顺序操作.将它们重新定义为交替操作,
are sequential operations. Redefine them as alternating operations,
(x:xs) >>/ g = g x +/ (xs >>/ g)
(x:xs) +/ ys = x : (ys +/ xs)
[] +/ ys = ys
并且您的定义也应该适用于无限列表:
and your definition should be good to go for infinite lists as well:
kart_i xs ys = xs >>/ (x ->
ys >>/ (y -> [(x,y)]))
测试,
Prelude> take 20 $ kart_i [1..] [101..]
[(1,101),(2,101),(1,102),(3,101),(1,103),(2,102),(1,104),(4,101),(1,105),(2,103)
,(1,106),(3,102),(1,107),(2,104),(1,108),(5,101),(1,109),(2,105),(1,110),(3,103)]
由 理性策划者"提供 /a>.(另见conda、condi、conde、condu). 另一种更明确的方法是创建单独的子流并将它们组合起来: another way, more explicit, is to create separate sub-streams and combine them: 这实际上产生了完全相同的结果.但是现在我们可以更好地控制如何组合子流.我们可以更加倾斜: this actually produces exactly the same results. But now we have more control over how we combine the sub-streams. We can be more diagonal: 所以现在我们得到 通过一些搜索SO我还发现了一个Norman Ramsey 的回答 似乎是另一种生成序列的方法,将这些子流分为四个区域 - 左上角,顶行,左列,递归其余列.他的 With some searching on SO I've also found an answer by Norman Ramsey with seemingly yet another way to generate the sequence, splitting these sub-streams into four areas - top-left tip, top row, left column, and recursively the rest. His 你的第二个定义, 相当于只是 因为列表 Because the list 这篇关于Haskell 中无限列表的笛卡尔积的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!kart_i2 xs ys = foldr g [] [map (x,) ys | x <- xs]
where
g a b = head a : head b : g (tail a) (tail b)
kart_i3 xs ys = g [] [map (x,) ys | x <- xs]
where -- works both for finite
g [] [] = [] -- and infinite lists
g a b = concatMap (take 1) a
++ g (filter (not . null) (take 1 b ++ map (drop 1) a))
(drop 1 b)
Prelude> take 20 $ kart_i3 [1..] [101..]
[(1,101),(2,101),(1,102),(3,101),(2,102),(1,103),(4,101),(3,102),(2,103),(1,104)
,(5,101),(4,102),(3,103),(2,104),(1,105),(6,101),(5,102),(4,103),(3,104),(2,105)]
merge
和我们这里的+/
是一样的.merge
there is the same as our +/
here.genFromPair (e1, e2) = [x*e1 + y*e2 | x <- [0..], y <- [0..]]
genFromPair (e1, e2) = [0*e1 + y*e2 | y <- [0..]]
[0..]
是无限的,所以 x
的任何其他值都没有机会发挥作用.这是以上定义都想避免的问题.[0..]
is infinite there's no chance for any other value of x
to come into play. This is the problem that the above definitions all try to avoid.