CODEWITHSUNDEEP
haskell
Laci Feldsam
Laci Feldsam

Reputation: 119

Haskell Cartesian product of infinite amount of infinite lists

Hi I want to ask if it is possible to create a Cartesian product of Infinite amount of infinite lists.

Sequence is a good function as example what I want. But I want it to work on Infinites.

I know how to do Cartesian of two infinite lists. 

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

Also I cant figure out how to do Cartesian of any amount of infinite list

Upvotes: 2

Views: 240

Answers (1)

luqui
luqui

Reputation: 60463

First of all, cartInf does not actually work.

ghci> take 100 $ cartInf2 [1..] [1..]
[[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,10],[1,11],[1,12], 
[1,13],[1,14],[1,15],[1,16],[1,17],[1,18],[1,19],[1,20],[1,21],[1,22],[1,23], 
[1,24],[1,25],[1,26],[1,27],[1,28],[1,29],[1,30],[1,31],[1,32],[1,33],[1,34], 
...

We will never reach a point where the first element is anything but 1. As @chi recommends you can use Control.Monad.Omega or Control.Monad.WeightedSearch if you want every pair to appear in the result eventually.

Secondly, the cartesian product of infinitely many lists is not countable (as long as they have at least two elements), as proved by Cantor in 1891. Suppose we had

allBoolLists :: [[Bool]]
allBoolLists = cartesianProduct (repeat [True,False])

which would be the list of "all infinite lists of booleans". No such list can exist, because we can construct

bad :: [Bool]
bad = zipWith negateNth [0..] allBoolLists
    where
    -- negates the nth element of a list
    negateNth n xs = take n xs ++ not (xs !! n) ++ drop (n+1) xs

which differs from every element of allBoolLists -- it differs from the 0th element at position 0, the 1st element at position 1, and so on.

Upvotes: 1

Related Questions