# [Haskell-cafe] Re: howto tuple fold to do n-ary cross product?

Luke Palmer lrpalmer at gmail.com
Sun Nov 30 18:18:59 EST 2008

On Sun, Nov 30, 2008 at 3:13 PM, Martijn van Steenbergen
<martijn at van.steenbergen.nl> wrote:
> Luke Palmer wrote:
>>
>> The other nice one problem is allowing the argument itself to be
>> infinite (you have to require all of the lists to be nonempty).
>
> I think the requirement has to be a lot stronger for that to work.
>
> If every sublist has two elements, the answer is 2^infinity lists which is
> uncountable.

Good catch.  If there are infinitely many finite lists, you can
construct a searchable set of results:

import Data.Searchable -- from infinite-search

finiteList :: [a] -> Set a
finiteList = foldr1 union . map singleton

cross :: Eq a => [[a]] -> Set a
cross = sequence . map finiteList

ghci> let cantor = cross (repeat [True,False])
ghci> fmap (take 10) \$ search cantor \$ \xs -> not (any (xs !!) [3..6])
Just [True,True,True,False,False,False,False,True,True,True]

Which is pretty much unrelated to what we were talking about.  But
it's cool to show of Martin Escardo's neat stuff.

Luke