Tree traversal: Difference between revisions

Content added Content deleted

Inline

@@ Line 5,904: / Line 5,904: @@
 {{Trans|Python}}
 <lang JavaScript>(() => {
-    'use strict';
+    "use strict";
-    // foldTree :: (a -> [b] -> b) -> Tree a -> b
-    const foldTree = f =>
-        // The catamorphism on trees. A summary
-        // value obtained by a depth-first fold.
-        tree => {
-            const go = x => f(x.root)(
-                x.nest.map(go)
-            );
-            return go(tree);
-        };
     // preorder :: a -> [[a]] -> [a]
     const preorder = x =>
-        xs => [x, ...concat(xs)];
+        xs => [x, ...xs.flat()];
     // inorder :: a -> [[a]] -> [a]
     const inorder = x =>
-        xs => length(xs) ? (
+        xs => Boolean(xs.length) ? (
-            [...xs[0], x, ...concat(xs.slice(1))]
+            [...xs[0], x, ...xs.slice(1).flat()]
         ) : [x];
     // postorder :: a -> [[a]] -> [a]
     const postorder = x =>
-        xs => [...concat(xs), x];
+        xs => [...xs.flat(), x];
     // levelOrder :: Tree a -> [a]
     const levelOrder = tree =>
-        concatMap(map(root))(
+        levels(tree).flat();
-            takeWhile(length)(
-                iterate(concatMap(nest))(
-                    [tree]
-                )
-            )
-        );
     // ------------------------TEST------------------------
+    // main :: IO ()
     const main = () => {
         const tree = Node(1)([
@@ Line 5,961: / Line 5,946: @@
         // task: 'Visualize a tree'
         console.log([
-            '       ┌ 4 ─ 7',
+            "       ┌ 4 ─ 7",
-            '   ┌ 2 ┤',
+            "   ┌ 2 ┤",
-            '   │   └ 5',
+            "   │   └ 5",
-            ' 1 ┤',
+            " 1 ┤",
-            '   │       ┌ 8',
+            "   │       ┌ 8",
-            '   └ 3 ─ 6 ┤',
+            "   └ 3 ─ 6 ┤",
-            '           └ 9'
+            "           └ 9"
-        ].join('\n'));
+        ].join("\n"));
         [preorder, inorder, postorder]
-        .forEach(
+        .forEach(f => console.log(
-            f => console.log(
+            justifyRight(11)(" ")(`${f.name}:`),
-                justifyRight(11)(' ')(f.name + ':'),
+            foldTree(f)(
-                foldTree(f)(
+                tree
-                    tree
-                )
             )
-        );
+        ));
         console.log(
-            'levelOrder:', levelOrder(tree)
+            `levelOrder: ${levelOrder(tree)}`
-        )
+        );
     };
-    // -----------------GENERIC FUNCTIONS------------------
+    // ---------------------- TREES ----------------------
     // Node :: a -> [Tree a] -> Tree a
@@ Line 5,993: / Line 5,976: @@
         // more child trees.
         xs => ({
-            type: 'Node',
+            type: "Node",
             root: v,
             nest: xs || []
         });
-    // concat :: [[a]] -> [a]
-    // concat :: [String] -> String
-    const concat = xs =>
-< xs.length ? (
-            xs.every(x => 'string' === typeof x) ? (
-                ''
-            ) : []
-        ).concat(...xs) : xs;
-    // concatMap :: (a -> [b]) -> [a] -> [b]
+    // foldTree :: (a -> [b] -> b) -> Tree a -> b
-    const concatMap = f =>
+    const foldTree = f => {
-        xs => xs.flatMap(f);
+        // The catamorphism on trees. A summary
+        // value obtained by a depth-first fold.
+        const go = tree => f(
+            tree.root
+        )(
+            tree.nest.map(go)
+        );
+        return go;
-    // iterate :: (a -> a) -> a -> Gen [a]
+    };
-    const iterate = f =>
-        function*(x) {
-            let v = x;
-            while (true) {
+    // levels :: Tree a -> [[a]]
-                yield(v);
+    const levels = tree => {
-                v = f(v);
+        // A list of lists, grouping the root
-            }
+        // values of each level of the tree.
+        const go = (a, node) => {
+            const [h, ...t] = 0 < a.length ? a : [
+                []
+            ];
+            return [
+                [node.root, ...h],
+                ...node.nest.reduceRight(go, t)
+            ];
         };
+        return go([], tree);
+    };
+    // --------------------- GENERIC ---------------------
     // justifyRight :: Int -> Char -> String -> String
@@ Line 6,025: / Line 6,021: @@
         // The string s, preceded by enough padding (with
         // the character c) to reach the string length n.
-        c => s => n > s.length ? (
+        c => s => Boolean(s) ? (
             s.padStart(n, c)
-        ) : s;
+        ) : "";
-    // length :: [a] -> Int
-    const length = xs =>
-        // Returns Infinity over objects without finite
-        // length. This enables zip and zipWith to choose
-        // the shorter argument when one is non-finite,
-        // like cycle, repeat etc
-        (Array.isArray(xs) || 'string' === typeof xs) ? (
-            xs.length
-        ) : Infinity;
-    // map :: (a -> b) -> [a] -> [b]
-    const map = f =>
-        // The list obtained by applying f to each element of xs.
-        // (The image of xs under f).
-        xs => (Array.isArray(xs) ? (
-            xs
-        ) : xs.split('')).map(f);
-    // nest :: Tree a -> [a]
-    const nest = tree => tree.nest;
-    // root :: Tree a -> a
-    const root = tree => tree.root;
-    // takeWhile :: (a -> Bool) -> Gen [a] -> [a]
-    const takeWhile = p => xs => {
-        const ys = [];
-        let
-            nxt = xs.next(),
-            v = nxt.value;
-        while (!nxt.done && p(v)) {
-            ys.push(v);
-            nxt = xs.next();
-            v = nxt.value
-        }
-        return ys;
-    };
     // MAIN ---