无限列表的笛卡尔积haskell [英] cartesian product of infinite lists haskell
问题描述
我有一个有限清单的函数
>卡丁车:: [a] - > [b] - > [（a，b）]
> kart xs ys = [（x，y）| x < - xs，y < - ys]
但是如何实现无限列表？我听说过关于Cantor和set theory的一些信息。？
我还发现了一个函数，例如
pre > > genFromPair（e1，e2）= [x * e1 + y * e2 | x < - [0 ..]，y < - [0 ..]]
但我不确定它是否有帮助，因为拥抱只会在不中断的情况下给出配对。
感谢您的帮助。
kart xs ys = xs>> =（\ x - >
ys>> =（\ y - > [（x，y）]））
其中
（x：xs）> ;> = g = gx ++（xs>> = g）
（x：xs）++ ys = x：（xs ++ ys）
是顺序操作。将它们重新定义为交替操作，
（x：xs）>> / g = gx + /（xs>> ; / g）
（x：xs）+ / ys = x：（ys + / xs）
[] + / ys = ys
并且您的定义应该适用于无限列表：
<$ c $（$ x $>> /（\ x - >
ys>> /（\ y - > [（x，y）]））
$ b $ p $前奏> （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）]
礼貌The Reasoned Schemer。 （另见 conda，condi，conde，condu ）。
另一种更明确的方法是创建单独的子流并合并它们：
kart_i2 xs ys = foldr g [] [map（x，）ys | x < - xs]
其中
gab =头部a：头部b：g（尾部a）（尾部b）
这实际上会产生完全相同的结果。但是现在我们对如何组合子流有更多的控制权。我们可以更对角线：
kart_i3 xs ys = g [] [map（x，）ys | x < - xs]
其中 - 适用于有限
g [] [] = [] - 和无限列表
gab = concatMap（取1）a
++ g（filter（not.null）（take 1 b ++ map（drop 1）a））
（drop 1 b）
，现在我们得到
Prelude> （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）]
有些在搜索上我还发现一个诺曼拉姆齐的回答看似又有另一种方法来生成序列，将这些子流分成四个区域 - 左上角，上排，左列和其余部分。他的合并与我们的 + / 在这里相同。
你的第二个定义是，
genFromPair（e1，e2）= [ x * e1 + y * e2 | x < - [0 ..]，y < - [0 ..]]
是相当于只要
genFromPair（e1，e2）= [0 * e1 + y * e2 | y < - [0 ..]]
因为列表 [0 ..] 是无限的，任何其他值 x 都没有机会进场。 是上述定义都试图避免的问题。
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..]]
But I'm not sure if it helps, because hugs only gives out pairs without interrupting.
Thanks for help.
Your first definition, kart xs ys = [(x,y) | x <- xs, y <- ys], is equivalent to
kart xs ys = xs >>= (\x ->
ys >>= (\y -> [(x,y)]))
where
(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)]))
testing,
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)]
courtesy of "The Reasoned Schemer". (see also 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)
so that now we get
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)]
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.
Your second definition,
genFromPair (e1, e2) = [x*e1 + y*e2 | x <- [0..], y <- [0..]]
is equivalent to just
genFromPair (e1, e2) = [0*e1 + y*e2 | y <- [0..]]
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屋！
