无限列表的Haskell笛卡尔乘积

Question

嗨，我想问，是否有可能创建无限数量的无限列表的笛卡尔乘积。

序列是一个很好的函数，作为我想要的例子。但我希望它能在Infinites上工作。

我知道如何做两个无限列表的笛卡尔。

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

我也不知道如何对任意数量的无限列表做笛卡尔分析。

Answer 1

首先，cartInf实际上并不工作。

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

我们永远不会达到第一个元素不是1的地步。正如@chi建议的那样，如果你希望每一对最终都出现在结果中，你可以使用Control.Monad.Omega或Control.Monad.WeightedSearch。

其次，无限多个列表的笛卡尔乘积是不可数的(只要它们至少有两个元素)，就像proved by Cantor in 1891一样。假设我们有

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

这将是“布尔值的所有无限列表”的列表。这样的列表不能存在，因为我们可以构造

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

它与allBoolLists的每个元素都不同--它与位置0的第0个元素、位置1的第一个元素不同，依此类推。