polytree-0.1.2: README.md
# 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
```haskell
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:
```bash
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
