我希望在Haskell中生成2个列表的笛卡尔积,但我无法弄清楚如何做到这一点.笛卡尔积给出了列表元素的所有组合:

xs = [1,2,3]
ys = [4,5,6]

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

这不是一个实际的家庭作业问题,与任何此类问题无关,但解决这个问题的方式可能有助于我坚持下去.

这个问题询问如何计算给定数量向量的笛卡尔乘积.由于向量的数量是预先知道的并且相当小,因此使用嵌套的for循环很容易获得解决方案.

现在假设您以您选择的语言给出了向量(或列表列表或集合等)的向量:

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ]

如果我被要求计算其笛卡尔积,那就是

[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ]

我会继续递归.例如,在快速和肮脏的python中,

def cartesianProduct(aListOfLists):
    if not aListOfLists:
        yield []
    else:
        for item in aListOfLists[0]:
            for product in cartesianProduct(aListOfLists[1:]):
                yield [item] + product

有一种简单的方法可以迭代计算它吗？

(注意:答案不需要在python中,无论如何我都知道在python中,itertools可以更好地完成工作,就像在这个问题中一样.)

给定x所有子列表具有相同长度的长度列表列表y,输出包含每个子列表中的一个项目y^x的长度x列表.

示例(x = 3,y = 2):

[ [1, 2], [3, 4], [5, 6] ]

输出(2^3 == 8不同输出):

[ [1, 3, 5], [1, 4, 5], [1, 3, 6], [1, 4, 6],
  [2, 3, 5], [2, 4, 5], [2, 3, 6], [2, 4, 6] ]

我的研究/工作

红宝石

我编写了实际代码来执行此任务,但在Ruby中,因为它是我最熟悉的语言.

def all_combinations(lst)
   lst.inject {|acc, new| acc.product(new).map(&:flatten) }
end

类型

输入是包含类型a的项的列表列表,输出也是如此.

allProduct :: [[a]] -> [[a]]

笛卡尔积,扁平化和折叠

看看我的Ruby解决方案让我觉得充分利用这些功能可能足以解决问题.问题是虽然笛卡尔积输出了一个元组列表,但我需要一个列表列表.