无限列表的笛卡儿积分haskell

Question

我有一个有限列表的函数

> kart :: [a] -> [b] -> [(a,b)]
> kart xs ys = [(x,y) | x <- xs, y <- ys]

但如何为无限列表实现它？我听说过Cantor和集合理论......

我也发现了一个类似的功能

> genFromPair (e1, e2) = [x*e1 + y*e2 | x <- [0..], y <- [0..]]

但是我不确定它是否有帮助,因为拥抱只会在没有中断的情况下发出对.

感谢帮助.

Answer 1

你的第一个定义kart xs ys = [(x,y) | x <- xs, y <- ys]相当于

kart xs ys = xs >>= (\x ->
             ys >>= (\y -> [(x,y)]))

哪里

(x:xs) >>= g = g x ++ (xs >>= g)
(x:xs) ++ ys = x : (xs ++ ys)

是顺序操作.将它们重新定义为交替操作,

(x:xs) >>/ g = g x +/ (xs >>/ g)
(x:xs) +/ ys = x : (ys +/ xs)
[]     +/ ys = ys

你的定义也应该适合无限列表:

kart_i xs ys = xs >>/ (\x ->
               ys >>/ (\y -> [(x,y)]))

测试,

Prelude> take 20 $ kart_i [1..] [100..]
[(1,100),(2,100),(1,101),(3,100),(1,102),(2,101),(1,103),(4,100),(1,104),(2,102)
,(1,105),(3,101),(1,106),(2,103),(1,107),(5,100),(1,108),(2,104),(1,109),(3,102)]

礼貌的"理性的计划者".(另见conda,condi,conde,condu).

另一种更明确的方法是创建单独的子流并将它们组合起来:

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..] [100..]
[(1,100),(2,100),(1,101),(3,100),(2,101),(1,102),(4,100),(3,101),(2,102),(1,103)
,(5,100),(4,101),(3,102),(2,103),(1,104),(6,100),(5,101),(4,102),(3,103),(2,104)]

通过对SO的一些搜索,我也找到了Norman Ramsey的答案,看似又一种生成序列的方法,将这些子流分成四个区域 - 左上角,左上角,左列和其余区域.他merge和我们+/在这里一样.

你的第二个定义,

genFromPair (e1, e2) = [x*e1 + y*e2 | x <- [0..], y <- [0..]]

等同于

genFromPair (e1, e2) = [0*e1 + y*e2 | y <- [0..]]

因为列表[0..]是无限的,所以任何其他值都没有机会x发挥作用.这是上述定义都试图避免的问题.