🌳 effect-tree

A Typescript library for working with immutable trees.

1. Synopsis
2. About
3. Quick Start
   1. Install
   2. Import
   3. Create
   4. Draw
   5. Operate
4. Dependencies
5. Not Ready Yet
6. See Also
7. Related

Synopsis

import {from, of, drawTree} from 'effect-tree'

console.log(
  drawTree.doubleSpaceThin(
    from('Hello', from('World', of('🌳')))
  )
)

Prints:

─┬Hello
 │
 └─┬World
   │
   └──🌳

About

1. The basic immutable generic data structure for encoding generic eager trees with 0-n child nodes per branch, also called Rose Trees and everything you need to efficiently query and operate on them.
2. Stack-safe folds/unfolds, a zipper for efficient traversal and update, and a library of operations on trees, from counting to zipping and zipping associatively.
3. Encode/decode trees into indented strings à la YAML, nested arrays, edge lists, path list of leaves, and Prüfer codes. Read directories into trees and build directories from trees of paths.
4. Instances for @effect/typeclass with law tests.
5. Draw themeable trees on the terminal with support for multiline labels and build your own layouts.
6. Testing helpers: Customizable arbitraries and functions to enumerate labeled trees.

You can find API documentation here.

Read here for more info on features, or just jump to the pretty pictures and proceed to running the examples.

Quick Start

Install

pnpm install effect-tree

Import

Everything can be imported from the top level entry-point effect-tree:

import {type Tree, from, append, of, drawTree, Codec} from 'effect-tree'

const myLeaf = of('🍁')
console.log(drawTree.unlines(myLeaf))
// ─🍁

const helloThere: Tree<string> = from('hello', of('there'))
const world: Tree<string> = append(helloThere, of('world'))

const encoded = Codec.Indented.encode(world)
console.log(encoded.join('\n'))
// hello
//   there
//   world

Create

You can create leaves and branches with functions like of and from that return the type Tree, functions like branch and leaf that return Branch and Leaf, or use one of the many combinators available to build a tree in several steps.

You can unfold trees in various ways, decode trees from some encoded form, summon the n^th tree from the enumeration of all ordered labeled trees, or generate random trees:

import {Arbitrary, type Tree, Codec, branch, leaf, nAryTree} from 'effect-tree'
import fc from 'fast-check'

// Manually
const myBranch = branch('1.', [leaf('2.1'), leaf('2.2')])

// Unfolding. Tree nodes will be set to node depth.
const myTernaryTree: Tree<number> = nAryTree({degree: 3, depth: 3})

// Decode from nested arrays.
const decodedTree: Tree<number> = Codec.Arrays.decode([1, [2, 3, [4, [5, 6]]]])

// Get the The 400,000,000,000,000th (4×10¹⁴) labeled tree with 16 nodes:
const enumeratedTree = Codec.Prufer.getNthTree(4n * 10n ** 14n, 16)

// Generate a tree using “fast-check”
const randomTree = fc.sample(
  Arbitrary.Tree.getArbitrary(fc.integer({min: 0, max: 10_000}), {
    branchBias: 1 / 4,
    maxDepth: 3,
    maxChildren: 5,
  }),
  {numRuns: 1, seed: 42},
)

Draw

Draw themed trees to the terminal and compose custom layouts.

import {binaryTree, drawTree} from 'effect-tree'
import {pipe} from 'effect'

//                           A variant of “drawTree” that renders
//                           numeric trees into a string
//                                         ┊
//                             ╭┄┄┄┄┄┄┄┄┄┄┄┴┄┄┄┄┄┄┄┄┄┄┄╮
console.log(pipe(3, binaryTree, drawTree.number.unlines))
//┬1
//├┬2
//│├─3
//│└─3
//└┬2
// ├─3
// └─3

Operate

For example with a zipper:

import {leaf, binaryTree, drawTree, Zipper} from 'effect-tree'
import {pipe} from 'effect'

console.log(
  pipe(
    3,
    binaryTree,
    Zipper.fromTree,
    Zipper.head,
    Zipper.head,
    Zipper.replace(leaf(42)),
    Zipper.toTree,
    drawTree.unixRound.number.unlines,
  ),
)
// ─1
//  ├─2
//  │ ├─42 ← replaced
//  │ ╰─3
//  ╰─2
//    ├─3
//    ╰─3

Dependencies

1. effect
2. @effect/typeclass
3. effect-ts-folds
4. tty-strings

Not Ready Yet

1. More examples in API documentation.
2. Effect.Schema codec.
3. Folds for collecting tree metrics.
4. A lazy version where the Branch.forest field is not an array but a stream.
5. Playground.

See Also

1. API Documentation
2. Examples README
3. Codecs module README
4. Draw module README
5. List of features

Related

1. fp-ts tree
2. recursion schemes
3. effect-ts-laws is used for law testing.