Jump to content

Tree traversal: Difference between revisions

Tree traversal (view source)

Revision as of 19:35, 22 September 2021

1,291 bytes removed ,  2 years ago
→‎JS ES6: Updated primitives, tidied
(→‎JS ES6: Updated primitives, tidied)
Line 5,904:
{{Trans|Python}}
<lang JavaScript>(() => {
'"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.flat()];
 
// inorder :: a -> [[a]] -> [a]
const inorder = x =>
xs => lengthBoolean(xs.length) ? (
[...xs[0], x, ...concat(xs.slice(1).flat()]
) : [x];
 
// postorder :: a -> [[a]] -> [a]
const postorder = x =>
xs => [...concat(xs.flat(), x];
 
// levelOrder :: Tree a -> [a]
const levelOrder = tree =>
concatMaplevels(maptree).flat(root))(;
 
takeWhile(length)(
iterate(concatMap(nest))(
[tree]▼
)▼
)▼
);▼
 
// ------------------------TEST------------------------
// rootmain :: TreeIO a -> a()▼
const main = () => {
const tree = Node(1)([
Line 5,961 ⟶ 5,946:
// task: 'Visualize a tree'
console.log([
'" ┌ 4 ─ 7'",
'" ┌ 2 ┤'",
'" │ └ 5'",
'" 1 ┤'",
'" │ ┌ 8'",
'" └ 3 ─ 6 ┤'",
'" └ 9'"
].join('"\n'"));
 
[preorder, inorder, postorder]
.forEach(f => console.log(
fjustifyRight(11)(" => console.log")(`${f.name}:`),
justifyRightfoldTree(11f)(' ')(f.name + ':'),
foldTree(f)(tree
tree▼
)▼
)
));
 
console.log(
'`levelOrder:', ${levelOrder(tree)}`
);
};
 
// -----------------GENERIC----- FUNCTIONSTREES ----------------------
 
// Node :: a -> [Tree a] -> Tree a
Line 5,993 ⟶ 5,976:
// more child trees.
xs => ({
type: '"Node'",
root: v,
nest: xs || []
});
 
// concat :: [[a]] -> [a]
// concat :: [String] -> String
const concat = xs =>
0 < xs.length ? (▼
xs.every(x => 'string' === typeof x) ? (
''
) : []
).concat(...xs) : xs;
 
// concatMapfoldTree :: (a -> [b] -> b) -> [Tree a] -> [b]
const concatMapfoldTree = f => {
xs// =>The xscatamorphism on trees.flatMap(f); A summary
▲ // value obtained by a depth-first fold.
▲ const foldTreego = ftree => f(
▲ )tree.root
▲ )(
▲ xtree.nest.map(go)
▲ });
 
▲ )return go;
// iterate :: (a -> a) -> a -> Gen [a]
};▼
const iterate = f =>
 
function*(x) {
 
let v = x;
// levels :: Tree a -> while (true) {[[a]]
const levels = tree => yield(v);{
// A list of lists, grouping the v = f(v);root
// values of each }level of the tree.
▲ const go = x(a, node) => f(x.root)({
▲ const [h, ...t] = 0 < xsa.length ? (a : [
▲ [tree]
▲ tree => { ];
 
▲ return )[
▲ [node.root, tree...h],
...node.nest.reduceRight(go, t)
▲ )];
};
 
▲ return go([], tree);
};▼
 
 
// --------------------- GENERIC ---------------------
 
// justifyRight :: Int -> Char -> String -> String
Line 6,025 ⟶ 6,021:
// The string s, preceded by enough padding (with
// the character c) to reach the string length n.
c => s => n > Boolean(s.length) ? (
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 ---
Hout
9,659

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/119538"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information