假設(shè)我們有兩個集合蝴悉，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）函數(shù)>>=

然而，do-notation也是一個語法糖抱完，

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

可是>>=是什么呢贼陶？它是一個高階函數(shù)，我們來看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來實現(xiàn)

先把>>=都去掉撮胧，

[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]

然后，分別實現(xiàn)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"]]