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]

但是如何为无限列表实现它呢?我听说过有关Cantor和设定理论的信息.

but how to implement it for infinite lists? I have heard something about Cantor and set theory.

我还发现了类似的功能

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

但是我不确定是否有帮助，因为拥抱只会给出配对而不会中断.

But I'm not sure if it helps, because hugs only gives out pairs without interrupting.

感谢您的帮助.

推荐答案

您的第一个定义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)

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

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

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

another way, more explicit, is to create separate sub-streams and combine them:

kart_i2 xs ys = foldr g [] [map (x,) ys | x <- xs]
  where
     g a b = head a : head b : g (tail a) (tail b)

这实际上产生完全相同的结果.但是现在我们可以更好地控制子流的组合方式.我们可以对角线更多:

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:

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 ，我还发现了

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 the rest. His 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的任何其他值都没有机会发挥作用. 这是以上定义都试图避免的问题.

Because the list [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.

这篇关于Haskell中无限列表的笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！