How to reverse a tree in TypeScript the Functional way

Trees are the single most important data structure in computer science, after lists. Just about everything you do in your programming career will be related to trees. For example JSON objects, xml, html DOM are tree structures. Object oriented JavaScript developers when they enter the realm of functional programming quickly learn how to use map, and reduce in order to replace traditional for loops. What they do not learn is that Trees also have a map and reduce methods. In this article we are going to display the functional way to reverse a Binary Tree .

if we have a tree that look like this

     6
   /   \     
  3     4            
 / \   / \
7   3 8   1

we want to define a function Reverse that will give us as a result this tree

     6
   /   \
  4     3
 / \   / \
1   8 3   7

we are going to start from a ECMAScript Tree structure

now we can represent the first Tree with an objects like this:

     6
   /   \     
  3     4            
 / \   / \
7   3 8   1
new Node(new Node(new Leaf(7),3,new Leaf(3)), 6, new Node(new Leaf(8),4,new Leaf(1)));

Defining Pattern matching on Trees

The first thing we are going to define is a very simple matchWith method on the tree structure.

abstract class Tree<T> {
        abstract MatchWith<T1>(pattern: {
          leaf: (v: T) => T1;
          node: (left: Tree<T>, v: T, right: Tree<T>) => T1;
        }): T1;
      }
      
      class Node1<T> extends Tree<T> {
       
        MatchWith<T1>(pattern: {
          leaf: (v: T) => T1;
          node: (left: Tree<T>, v: T, right: Tree<T>) => T1;
        }): T1 {
          return pattern.node(this.Left, this.Value, this.Right);
        }
      }
      
      class Leaf<T> extends Tree<T> {
      
        MatchWith<T1>(pattern: {
          leaf: (v: T) => T1;
          node: (left: Tree<T>, v: T, right: Tree<T>) => T1;
        }): T1 {
          return pattern.leaf(this.Value);
        }
      }

This takes as an argument an object:

pattern: {
          leaf: (v: T) => T1;
          node: (left: Tree<T>, v: T, right: Tree<T>) => T1;
        }

and allows us to distinguish between Node and Leaf[this is called pattern matching]. This is the functional equivalent of Polymorhism and allow us to add methods without modifying the Types.

And that’s it !!!!! we are done. We can now define any type of recursive method on this tree. So how we are going to define Reverse recursively.

Take a look at the following Fiddle

all the magic happens here:

1. If you are on a leaf just return the leaf :Leaf: v => new Leaf(v)

2. If you are on a node just call reverse on the Left and Right Nodes and then just return a node with those reversed new nodes : new Node(right.reverse(), v, left.reverse())

[by the way this method of recursive definition is called structural induction]

https://leanpub.com/functional-programming-in-Ts-with-categories