[JavaScript] 求解任意n个集合的笛卡尔积

假设我们有两个集合，A={1, 2, 3}，B={'a', 'b'}，
我们怎样求解这两个集合的笛卡尔积呢？

A × B = {(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')}

我们想到Haskell中的list comprehension正好有这种功能。

（1）list comprehension

ghci> [(x, y) | x <- [1, 2, 3], y <- ['a','b']]
ghci> [(1,'a'), (1,'b'), (2,'a'), (2,'b'), (3,'a'), (3,'b')]

（2）do-notaion

list comprehension实际上是do-notation的语法糖，

do
    x <- [1, 2, 3]
    y <- ['a','b']
    return (x, y)

（3）函数>>=

然而，do-notation也是一个语法糖，

[1, 2, 3] >>= (\x -> ['a', 'b'] >>= (\y -> return (x, y)))

可是>>=是什么呢？它是一个高阶函数，我们来看list monad的定义，

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    fail _ = []

其中，

concat :: [[a]] -> [a]
map :: (a -> b) -> [a] -> [b]

（4）我们来证明一下

[1, 2, 3] >>= (\x -> ['a', 'b'] >>= (\y -> return (x, y)))
concat $ map (\x -> ['a', 'b'] >>= (\y -> return (x, y))) [1, 2, 3]

我们先看

(\x -> ['a', 'b'] >>= (\y -> return (x, y))) 1
['a', 'b'] >>= (\y -> return (1, y))
concat $ map (\y -> return (1, y)) ['a', 'b']

我们再看

(\y -> return (1, y)) 'a'
return (1, 'a')
[(1, 'a')]

然后，后退一步

concat $ map (\y -> return (1, y)) ['a', 'b']
concat [[(1, 'a')], [(1, 'b')]]
[(1, 'a'), (1, 'b')]

再后退一步

concat $ map (\x -> ['a', 'b'] >>= (\y -> return (x, y))) [1, 2, 3]
concat [[(1, 'a'), (1, 'b')], [(2, 'a'), (2, 'b')], [(3, 'a'), (3, 'b')]]
[(1,'a'), (1,'b'), (2,'a'), (2,'b'), (3,'a'), (3,'b')]

证毕。

（5）用JavaScript来实现

先把>>=都去掉，

[1, 2, 3] >>= (\x -> ['a', 'b'] >>= (\y -> return (x, y)))
concat $ map (\x -> ['a', 'b'] >>= (\y -> return (x, y))) [1, 2, 3]
concat $ map (\x -> concat $ map (\y -> return (x, y)) ['a', 'b']) [1, 2, 3]

然后，分别实现concat和map

function concat(array) {
    return [].concat.apply([], array);
}
function map(fn, array) {
    return [].map.call(array, fn);
}

concat(map(
    x=>concat(map(
        y=>[[x,y]], 
        ['a', 'b']
    )),
    [1, 2, 3]
));

简化一下：

function flatMap(fn, array) {
    return concat(map(fn, array));
}

flatMap(
    x=>flatMap(
        y=>[[x,y]], 
        ['a', 'b']
    ),
    [1, 2, 3]
);

（6）任意n个集合的笛卡尔积

export default function cartesianProduct(sets) {
    let head = sets.shift();
    if (sets.length === 0) {
        return map(
            item => [item],
            head
        );
    }

    let tailProduct = cartesianProduct(sets);
    return flatMap(
        item => flatMap(
            items => [[item, ...items]],
            tailProduct
        ),
        head
    );
}

function concat(array) {
    return [].concat.apply([], array);
}

function map(fn, array) {
    return [].map.call(array, fn);
}

function flatMap(fn, array) {
    return concat(map(fn, array));
}

测试，

cartesianProduct([[1, 2, 3],['a', 'b']])
=== [[1, "a"], [1, "b"], [2, "a"], [2, "b"], [3, "a"], [3, "b"]]