Map an arbitrary n-ary Tree with fold

Question

I want to have some general purpose tools for dealing with trees. I'm using JavaScript, so there's little I can impose, and I'm using existing data structures that I can't change. I managed to define the following:

reduceTree :: (T a -> [T a]) -> (b -> T a -> b) -> b -> T a -> b
reduceTree(getChildren, f, accumulator, tree)

(I'm using Haskell type signatures because they're easier to read)

This getChildren function is required because my tree is arbitrary, and I know nothing about how it is constructed.

reduceTree works well. But I would like to have a mapTree function too, preferably reusing my reduceTree function, but I'm stuck. Something is amiss but I can't figure out what.

Edit

My reduceTree implementation:

export function reduceTree(getChildren, f, accumulator, tree) {
  const children = getChildren(tree);
  if (!children || children.length === 0) {
    return f(accumulator, tree)
  } else {
    const childrenResult = children.reduce(
      (accumulator, subTree) => reduceTree(getChildren, f, accumulator, subTree),
      accumulator
    );
    return f(childrenResult, tree)
  }
}

It was tested and works.

(My pseudo Haskell implementation I used to construct/prove the javascript above:

reduceTree f a (Node val []) = f a val
reduceTree f a (Node val xs) = f (fold (reduceTree f) acc) val

)

Answer 1

I see that your tree data structure is defined as follows:

data T a = Node a [T a]

If that's the case then the fold for your tree data structure would be:

reduceTree :: (a -> [b] -> b) -> T a -> b
reduceTree f = let g (Node a xs) = f a (map g xs) in g

You can now define mapTree using reduceTree as follows:

mapTree :: (a -> b) -> T a -> T b
mapTree f = reduceTree (Node . f)

Converting it all to JavaScript:

const Node = (a, xs) => ({a, xs});

const reduceTree = (f, node) => {
    const g = node => f(node.a, node.xs.map(g));
    return g(node);
};

const mapTree = (f, node) => reduceTree((a, xs) => Node(f(a), xs), node);

const tree = Node(2, [ Node(3, [ Node(11, [])
                               , Node(13, []) ])
                     , Node(5, [])
                     , Node(7, [ Node(17, [])
                               , Node(19, []) ]) ]);

console.log(mapTree(x => 2 * x, tree));

Hope that helps.