Traversable instance for rose trees

require("@babel/polyfill"); const { IntSum, Arr, implement, Functor, Apply, Chain, Foldable, Traversable } = require("@masaeedu/fp"); const RoseTree__ = (() => { // Constructors const Node = l => c => ({ label: l, children: c }); // Traversable const traverse = A => f => ({ label, children }) => A.lift2(Node)(f(label))(Arr.traverse(A)(traverse(A)(f))(children)); // Monad const of = x => Node(x)([]); const chain = f => ({ label: l, children: c }) => { const { label: l_, children: c_ } = f(l); return Node(l_)(Arr.append(c_)(Arr.map(chain(f))(c))); }; return { Node, traverse, of, chain }; })(); // free stuff :) const RoseTree_ = implement(Functor)( implement(Foldable)(implement(Traversable)(RoseTree__)) ); // split it over two lines for clarity. ... |> implement(Chain) |> implement(Apply) solves this problem const RoseTree = implement(Apply)(implement(Apply)(implement(Chain)(RoseTree_))); const { Node, sequence, map, fold, chain, of, lift2 } = RoseTree; // notation: x -> [...ys] is a rose tree with label x and children ys // you could also just look through the results in the inspector const tests = [ map(x => x * 10)(Node(1)([Node(2)([]), Node(3)([])])), // => 10 -> [(20 -> []), (30 -> [])] sequence(Arr)(Node([10, 11])([Node([1])([]), Node([42, 55])([])])), // => [ // (10 -> [(1 -> []), (42 -> [])]), // (10 -> [(1 -> []), (55 -> [])]), // (11 -> [(1 -> []), (42 -> [])]), // (11 -> [(1 -> []), (55 -> [])]), // ], fold(IntSum)(Node(22)([Node(18)([Node(2)([])])])), // => 42 lift2(a => b => a + b)(of(10))(of(20)), // => 30 -> [] chain(x => Node("foo")([of(x), of(x)]))(Node("bar")([of("baz")])), // => input: "bar" -> ["baz" -> []] // >>= // x => "foo" -> [x -> [], (x -> [])] // => result: "foo" -> [ // "bar" -> [], // "bar" -> [], // "foo" -> ["baz" -> [], "baz" -> []] // ] ];