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.

Answer 2

TL;DR: Your pseudocode is broken. One way to fix it is

reduceTree :: (b -> a -> b) -> b -> T a -> b
reduceTree f acc (Node val []) = f acc val
reduceTree f acc (Node val ts) = 
    Data.List.foldl (\acc tree -> reduceTree f acc tree) (f acc val) ts

This means that your Javascript should have been

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),
      f(accumulator,tree)  // referring to `tree` only for its stored node value, yes?
    );
    return childrenResult;
  }
}

Presumably Javascript's reduce on lists is a left fold (according to Wikipedia it is so).

It performs pre-order tree traversal, and is equivalent to the tfoldl function at the bottom of this post. Implementing map with it doesn't quite work though,

tmap f t = reduceTree (\acc val -> Node (f val) ???) ??? t

because the types are not right for the Node :: a -> [T a] -> T a, which can't be made to fit the reducer type above, b -> a -> b (it needs the type a -> [b] -> b).

This is because this kind of linear folding is essentially flattening the structure, treating it as a linear sequence.

Some extraneous elaborations follow.

---

Haskell has it the exact same way as the reduceTree function in Aadit's answer.

John Hughes in his famous paper "Why Functional Programming Matters" had it almost the same way too, as

foldTree :: (a -> b -> r) -> (r -> b -> b) -> b -> Tree a -> r 
foldTree f g z (Node x t) = f x . foldr g z . map (foldTree f g z) $ t

He used an equivalent, but a bit more verbose formulation, which he called redtree, for "reduce tree". It holds that

foldTree f g z = reduceTree (\a rs -> f a (foldr g z rs)) 

so the two are pretty much equivalent. Then,

map h = reduceTree (Node . h) 
      = reduceTree (\a rs -> Node (h a) rs) 
      = foldTree (Node . h) (:) [] 

The absence of "zero" i.e. initial accumulator value comes from the absence of second clause in the data definition, data T a = Node a [T a] as opposed to List a = Nil | Cons a (List a), for the lists.

The fold's reducer function for the latter takes either Nil or Cons a r to r, hence it must have the "zero" i.e. defult value supplied to it; and for the former it takes Node a [r] to r, so there's no Nil case to handle (cf. recursion-schemes).

---

Following a hint from user Bergi in the comments, the Haskell package containers defines a Foldable instance for this type,

data T a = Node a [T a]

whose equivalent of foldr (with flipped arguments, for convenience), is

tfoldr :: (a -> b -> b) -> T a -> b -> b 
tfoldr f (Node x ts) z = f x $ Data.List.foldr ($) z [tfoldr f t | t <- ts]

indeed threading through the state / accumulator! It can be also written as

tfoldr :: (a -> b -> b) -> T a -> b -> b 
tfoldr f (Node x ts) z = f x . Data.List.foldr (.) id [tfoldr f t | t <- ts] $ z

whichever is easier for you to implement. This is implementing the post-order tree traversal; for the usual pre-order traversal use

tfoldl :: (a -> b -> b) -> T a -> b -> b
tfoldl f (Node x ts) z = Data.List.foldr (>>>) id [tfoldl f t | t <- ts] $ f x z
                 -- // = tfoldl f tn (... (tfoldl f t2 (tfoldl f t1 (f x z))) ...)

where (f >>> g) x = g (f x), or

tfoldl :: (b -> a -> b) -> T a -> b -> b
tfoldl f (Node x ts) z = Data.List.foldr (>>>) id [tfoldl f t | t <- ts] $ f z x
                 -- // = tfoldl f tn (... (tfoldl f t2 (tfoldl f t1 (f z x))) ...)

which is equivalent to the code at the start of this post, up to the order of arguments.

• see also: Variations of folds on Haskell Trees