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

[Luke Palmer]

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