Variants as Trees - vilinski/nemerle GitHub Wiki

Variants as Trees

Category: Defining Types
Description: Variants are excellent for representing tree structures.
Code:

using System;
using System.Console;
using Nemerle;
using System.Linq;

variant Tree[T]
{
  | Node { value : T; left : Tree[T]; right : Tree[T];}
  | Tip
}
  
using Tree;

def tree = Node(4, Node(2, Node(1, Tip(), Tip()), Node(6, Tip(), Tip())), Node(6, Node(5, Tip(), Tip()), Node(7, Tip(), Tip())));
//      4
//  2       6
// 1 3     5 7
// InOrder : Tree[T] -> list[T]
def InOrder(t)
{
  | Node(x, left, right) => InOrder(left) + [x] + InOrder(right) 
  | Tip                  => [] 
}
// Height : Tree[T] -> int 
def Height(t)
{
  | Node(_, left, right) => 1 + Math.Max(Height(left), Height(right)) 
  | Tip                  => 0
}
    
WriteLine($"The tree in order = $(InOrder(tree))");
WriteLine($"The height of the tree = $(Height(tree))")

Execution Result:

The tree in order = [1, 2, 6, 4, 5, 6, 7]
The height of the tree = 3