polytree

A polymorphic rose tree with different types for node labels and leaf values.

Overview

The polytree library provides Tree f a b and TreeForest f a b data types where:

• f is a polymorphic container type (list, vector, etc.)
• a is the type of node labels
• b is the type of leaf values

This design allows for flexible tree representations where internal nodes and leaves can have different types, and the choice of container affects performance characteristics.

Key Features

Data Types

• Tree f a b - A tree with labels of type a at nodes and values of type b at leaves
• TreeForest f a b - A forest (collection) of trees and leaves
• Type aliases: Tree', TreeList, TreeList', Tree1, Tree1'

Type Class Instances

Comprehensive instances for:

• Standard classes: Eq, Ord, Show (with lifted variants Eq1, Eq2, etc.)
• Functors: Bifunctor, Functor
• Applicatives: Apply, Applicative (operates over leaves with Monoid/Semigroup on labels)
• Foldables: Bifoldable, Foldable, Bifoldable1, Foldable1
• Traversables: Bitraversable, Traversable, Bitraversable1, Traversable1
• Lens integration: Wrapped, Plated, and custom optics

Optics

Four-level classy optics hierarchy:

• GetX - Read-only access via Getter
• HasX - Read-write access via Lens'
• ReviewX - Construction via Review
• AsX - Full prism access via Prism'

Available for both Tree and TreeForest types.

Utility Functions

• Construction: makeTree, makeChild, makeLeaves, makeChildren, singleton
• Unfolding: unfoldTree, unfoldTreeM
• Traversal: dfs (depth-first), bfs (breadth-first)
• Analysis: countNodes, countLeaves, levels
• Transformation: pruneLeaves
• Conversion: baseTree (to/from Data.Tree.Tree)

Example Usage

import Data.PolyTree
import Control.Lens

-- Create a tree with string labels and integer leaves
tree :: TreeList String Int
tree = Tree "root" 
         (TreeForest 
           [ Left 42                    -- A leaf
           , makeChild "child1" [Left 10, Left 20]  -- A subtree
           , makeChild "child2" []      -- An empty subtree
           ])

-- Traverse leaves
>>> toListOf treeLeaves tree
[42,10,20]

-- Map over leaves
>>> fmap (*2) tree
Tree "root" (TreeForest [Left 84,Right (Tree "child1" (TreeForest [Left 20,Left 40])),Right (Tree "child2" (TreeForest []))])

-- Depth-first traversal
>>> dfs tree
Left "root" :| [Right 42,Left "child1",Right 10,Right 20,Left "child2"]

-- Breadth-first traversal
>>> bfs tree
Left "root" :| [Right 42,Left "child1",Left "child2",Right 10,Right 20]

-- Unfold a tree
>>> unfoldTree (\n -> (n, if n > 0 then [Right (n-1)] else [])) 3
Tree 3 (TreeForest [Right (Tree 2 (TreeForest [Right (Tree 1 (TreeForest [Right (Tree 0 (TreeForest []))]))]))])

-- Use applicative instance (operates over leaves with Monoid on labels)
>>> Tree "a" (TreeForest [Left (+1)]) <*> Tree "b" (TreeForest [Left 5])
Tree "ab" (TreeForest [Left 6])

Design Decisions

Why Different Types for Nodes and Leaves?

Many tree algorithms distinguish between internal nodes (which have structural/organizational data) and leaves (which have payload data). For example:

• Decision trees: nodes contain split criteria, leaves contain predictions
• Expression trees: nodes contain operators, leaves contain values
• File systems: nodes are directories, leaves are files

Why Polymorphic Container?

The f parameter allows you to choose the container type:

• [] for simple lists (default, most flexible)
• Vector for efficient random access
• NonEmpty for non-empty forests (with Foldable1/Traversable1 instances)
• Identity for single-child trees

Why Not Biapplicative?

While Bifunctor, Bifoldable, and Bitraversable instances are possible, Biapply and Biapplicative instances are not implementable due to the recursive Either-based structure. The combination of a tree of functions with a single value has no canonical semantics.

Testing

The library includes comprehensive doctests (115 examples). Run with:

cabal test

Related Work

• Data.Tree from containers - Standard rose tree (single type for all nodes)
• Data.Tree.Class - Type class approach to trees
• This library's approach: Separate types for nodes/leaves with polymorphic container