декартово произведение бесконечных списков Haskell

Question

У меня есть функция для конечных списков

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

, но как реализовать его для бесконечных списков? Я слышал кое-что о Канторе и теории множеств ...?

Я также обнаружил функцию как

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

любезно "The Reasoned Schemer". (см. также 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) 

это на самом деле производит точно такие же результаты. Но теперь у нас больше контроля над тем, как мы объединяем подпотоки. Мы можем 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)] 

С некоторыми searching on SO я также нашел в answer by 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 вступить в игру. Это является проблемой, которую все вышеизложенные определения стараются избежать.

Answer 2

Prelude> let kart = (\xs ys -> [(x,y) | ls <- map (\x -> map (\y -> (x,y)) ys) xs, (x,y) <- ls]) 
Prelude> :t kart 
kart :: [t] -> [t1] -> [(t, t1)] 
Prelude> take 10 $ kart [0..] [1..] 
[(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(0,10)] 
Prelude> take 10 $ kart [0..] [5..10] 
[(0,5),(0,6),(0,7),(0,8),(0,9),(0,10),(1,5),(1,6),(1,7),(1,8)]