Cartesian product of infinite lists in Haskell

by

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

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

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 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.

More Related Contents:

  1. Haskell finding mean of cubes of odd members Any ideas? [closed]
  2. Histogram in Haskell [closed]
  3. What is Haskell’s Stream Fusion
  4. Using return vs. not using return in the list monad
  5. Decrementing ranges in Haskell
  6. Zip with default value instead of dropping values?
  7. Replace individual list elements in Haskell?
  8. Using Haskell’s map function to calculate the sum of a list
  9. Need to partition a list into lists based on breaks in ascending order of elements (Haskell)
  10. Merging two lists in Haskell
  11. Haskell Monad – How does Monad on list work?
  12. Is there a function to flatten a nested list of elements?
  13. Understanding a recursively defined list (fibs in terms of zipWith)
  14. Removing duplicates from a list in Haskell without elem
  15. Removing syntactic sugar: List comprehension in Haskell
  16. Counting unique elements in a list
  17. Unsequence Monad function within Haskell
  18. Grouping a list into lists of n elements in Haskell
  19. How to check a list contains substring from other list using scala?
  20. prolog change show answer to print into list
  21. Elixir lists interpreted as char lists
  22. Prolog – count repetitions in list
  23. Combining (cbind) vectors of different length
  24. How to flatten a list to a list without coercion?
  25. How can I delete duplicates in a Dart List? list.distinct()?
  26. Get elements from list of lists
  27. Extract list of attributes from list of objects in python
  28. Scala’s ‘::’ operator, how does it work?
  29. List.shuffle() in Dart?
  30. Splitting a list of items into two lists of odd and even indexed items

Leave a Comment