Cartesian product of two or more lists: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,162: / Line 1,162: @@
 For the n-ary Cartesian product over a list of lists:
 <lang JavaScript>(() => {
+    const main = () => {
-    // n-ary Cartesian product of a list of lists
+        // n-ary Cartesian product of a list of lists.
-    // cartProdN :: [[a]] -> [[a]]
+        // cartProdN :: [[a]] -> [[a]]
-    const cartProdN = lists =>
+        const cartProdN = foldr(
-        foldr((as, xs) =>
+            xs => as =>
-            bind(xs, x => bind(as, a => [x.concat(a)])), [
+            bind(as)(
-                []
+                x => bind(xs)(
-            ], lists);
+                    a => [[a].concat(x)]
+                )
+            )
+        )([[]]);
-    // GENERIC FUNCTIONS ------------------------------------------------------
+        // TEST -------------------------------------------
+        return intercalate('\n\n')([
+            map(show)(
+                cartProdN([
+                    [1776, 1789],
+                    [7, 12],
+                    [4, 14, 23],
+                    [0, 1]
+                ])
+            ).join('\n'),
+            show(cartProdN([
+                [1, 2, 3],
+                [30],
+                [50, 100]
+            ])),
+            show(cartProdN([
+                [1, 2, 3],
+                [],
+                [50, 100]
+            ]))
+        ])
+    };
+    // GENERIC FUNCTIONS ----------------------------------
     // bind ::  [a] -> (a -> [b]) -> [b]
-    const bind = (xs, f) => [].concat.apply([], xs.map(f));
+    const bind = xs => f => xs.flatMap(f);
-    // foldr (a -> b -> b) -> b -> [a] -> b
+    // foldr :: (a -> b -> b) -> b -> [a] -> b
-    const foldr = (f, a, xs) => xs.reduceRight(f, a);
+    const foldr = f => a => xs => {
+        let v = a,
+            i = xs.length;
+        while (i--) v = f(xs[i])(v);
+        return v;
+    };
     // intercalate :: String -> [a] -> String
-    const intercalate = (s, xs) => xs.join(s);
+    const intercalate = s => xs => xs.join(s);
     // map :: (a -> b) -> [a] -> [b]
-    const map = (f, xs) => xs.map(f);
+    const map = f => xs => xs.map(f);
     // show :: a -> String
     const show = x => JSON.stringify(x);
+    return main();
-    // unlines :: [String] -> String
-    const unlines = xs => xs.join('\n');
-    // TEST -------------------------------------------------------------------
-    return intercalate('\n\n', [unlines(map(show, cartProdN([
-            [1776, 1789],
-            [7, 12],
-            [4, 14, 23],
-            [0, 1]
-        ]))),
-        show(cartProdN([
-            [1, 2, 3],
-            [30],
-            [50, 100]
-        ])),
-        show(cartProdN([
-            [1, 2, 3],
-            [],
-            [50, 100]
-        ]))
-    ])
 })();</lang>
 {{Out}}