Skip to main content Link Search Menu Expand Document (external link)
effect-libs

Tree overview

Heterogeneous trees: each node is either a leaf carrying a value of type B or a non-leaf carrying a value of type A and a forest of child trees.

Mental model

  • Type<A, B> is a discriminated union of {@link “./TreeLeaf.js” MTreeLeaf.Type<B>} and
    {@link “./TreeNonLeaf.js” MTreeNonLeaf.Type<A, B>}.
  • A “tree” with a single leaf is just a leaf — perfectly valid. When the API must guarantee a non-leaf root, take MTreeNonLeaf.Type<A, B> directly.
  • {@link unfold} and {@link unfoldAndFold} build trees iteratively from a seed plus an unfold function returning either a leaf payload (Result.fail) or a non-leaf payload with child seeds (Result.succeed). Cycle detection is opt-in via a seed Equivalence.

Common tasks

  • Discriminate: {@link isLeaf}, {@link isNonLeaf}
  • Build: {@link unfold}, {@link unfoldAndFold}
  • Read values: {@link value}
  • Compare: {@link makeEquivalence}
  • Fold: {@link fold}, {@link reduce}, {@link reduceRight}, {@link unfoldAndFold}
  • Map / extend: {@link map}, {@link mapAccum}, {@link extendDown}, {@link extendUp}

Quickstart

Example (Build a tree from a seed and sum its leaves)

import { Result, pipe } from "effect"
import * as MTree from "@parischap/effect-lib/Tree/Tree"

const buildAndSum = pipe(
  3,
  MTree.unfoldAndFold({
    unfold: (n: number) => (n <= 0 ? Result.fail(0) : Result.succeed(["node" as const, [n - 1, n - 1]] as const)),
    foldNonLeaf: (_value, children) => children.reduce((a, b) => a + b, 1),
    foldLeaf: (n) => n
  })
)
console.log(buildAndSum) // count of non-leaf nodes

Table of contents

Constructors

unfold

Builds a tree by repeatedly applying an unfold function to seeds.

  • Non-recursive; uses a queue to process all nodes.
  • The unfold function returns either a leaf value (Failure) or a non-leaf value with child seeds (Success).
  • Optionally detects cycles using an equivalence on seeds.
  • When a cycle is detected, cycleSource is passed as some to allow modification.

Example (Build tree from seed)

import { pipe } from "effect"
import * as Result from "effect/Result"
import * as MTree from "@parischap/effect-lib/Tree/Tree"

const tree = MTree.unfold<number, string, number>((n) =>
  n === 0 ? Result.fail("leaf") : Result.succeed(["node", [n - 1]])
)(3)

Signature

export declare const unfold: {
  <S, A, B>(f: (seed: S) => Result.Result<MTypes.Pair<A, ReadonlyArray<S>>, B>): MTypes.OneArgFunction<S, Type<A, B>>
  <S, A, B>(
    f: (seed: S, cycleSource: Option.Option<NoInfer<A>>) => Result.Result<MTypes.Pair<A, ReadonlyArray<S>>, B>,
    seedEquivalence: Equivalence.Equivalence<S>
  ): MTypes.OneArgFunction<S, Type<A, B>>
}

unfoldAndFold

Builds a tree and simultaneously folds it in bottom-up order.

  • Combines tree construction and folding for efficiency.
  • Leaf nodes are folded using foldLeaf; non-leaf nodes using foldNonLeaf with accumulated children.
  • Returns the final folded value (bottom-up aggregation).
  • Optionally detects cycles using seed equivalence.

Example (Build and fold tree)

import * as Result from "effect/Result"
import * as MTree from "@parischap/effect-lib/Tree/Tree"

const result = MTree.unfoldAndFold({
  unfold: (n) => (n === 0 ? Result.fail(1) : Result.succeed(["parent", [n - 1]])),
  foldLeaf: (val) => val,
  foldNonLeaf: (val, children) => val.length + children[0]
})(2)

Signature

export declare const unfoldAndFold: {
  <A, B, S = A, C = B>(opts: {
    readonly unfold: (
      seed: S,
      cycleSource: Option.Option<NoInfer<A>>
    ) => Result.Result<MTypes.Pair<A, ReadonlyArray<S>>, B>
    readonly foldNonLeaf: (value: A, children: ReadonlyArray<C>) => C
    readonly foldLeaf: (value: B) => C
    readonly seedEquivalence: Equivalence.Equivalence<S>
  }): MTypes.OneArgFunction<S, C>
  <A, B, S = A, C = B>(opts: {
    readonly unfold: (seed: S) => Result.Result<MTypes.Pair<A, ReadonlyArray<S>>, B>
    readonly foldNonLeaf: (value: A, children: ReadonlyArray<C>) => C
    readonly foldLeaf: (value: B) => C
  }): MTypes.OneArgFunction<S, C>
}

Equivalences

makeEquivalence

Returns an equivalence on Type<A, B> derived from an equivalence on A (non-leaf values) and one on B (leaf values).

  • Two trees are equivalent iff they have the same shape and corresponding values match under the supplied equivalences.

Example

import { Equivalence } from "effect"
import * as MTree from "@parischap/effect-lib/Tree/Tree"
import * as MTreeLeaf from "@parischap/effect-lib/Tree/TreeLeaf"
import * as MTreeNonLeaf from "@parischap/effect-lib/Tree/TreeNonLeaf"

const eq = MTree.makeEquivalence(Equivalence.string, Equivalence.number)
const tree1 = MTreeNonLeaf.make({
  value: "root",
  forest: [MTreeLeaf.make(1), MTreeLeaf.make(2)]
})
const tree2 = MTreeNonLeaf.make({
  value: "root",
  forest: [MTreeLeaf.make(1), MTreeLeaf.make(2)]
})
console.log(eq(tree1, tree2)) // true

Signature

export declare const makeEquivalence: <A, B>(
  aEquivalence: Equivalence.Equivalence<A>,
  bEquivalence: Equivalence.Equivalence<B>
) => Equivalence.Equivalence<Type<A, B>>

Getters

value

Returns the value field of self. Result type is A | B because self may be a leaf (carrying B) or a non-leaf (carrying A).

Signature

export declare const value: <A, B>(self: Type<A, B>) => A | B

Guards

isLeaf

Tests whether u is a leaf node.

  • Acts as a type guard narrowing the input to MTreeLeaf.Type<B>.

Signature

export declare const isLeaf: <A, B>(u: Type<A, B>) => u is MTreeLeaf.Type<B>

isNonLeaf

Tests whether u is a non-leaf node.

  • Acts as a type guard narrowing the input to MTreeNonLeaf.Type<A, B>.

Signature

export declare const isNonLeaf: <A, B>(u: Type<A, B>) => u is MTreeNonLeaf.Type<A, B>

Models

Type (type alias)

Type of a Tree

Signature

export type Type<A, B> = MTreeLeaf.Type<B> | MTreeNonLeaf.Type<A, B>

Module markers

moduleTag

Module tag

Signature

export declare const moduleTag: "@parischap/effect-lib/Tree/"

Utils

extendDown

Extends a tree in top-down order, transforming each node to a new value.

  • More powerful than {@link map}—receives the entire node (not just its value).
  • Processes tree top-down: root first, then children level-by-level.
  • Functions receive the node itself and its level for context-aware transformation.
  • Use when transformation depends on position in tree or sibling relationships.

Example (Extend down: tag by level)

import * as MTree from "@parischap/effect-lib/Tree/Tree"
import * as MTreeLeaf from "@parischap/effect-lib/Tree/TreeLeaf"
import * as MTreeNonLeaf from "@parischap/effect-lib/Tree/TreeNonLeaf"

const tree = MTreeNonLeaf.make({
  value: "root",
  forest: [MTreeLeaf.make("leaf")]
})
const extended = MTree.extendDown({
  fNonLeaf: (node, level) => `${node.value}@${level}`,
  fLeaf: (leaf, level) => `${leaf.value}@${level}`
})(tree)

Signature

export declare const extendDown: <A, B, C, D>({
  fNonLeaf,
  fLeaf
}: {
  readonly fNonLeaf: (tree: Type<NoInfer<A>, NoInfer<B>>, level: number) => C
  readonly fLeaf: (leaf: MTreeLeaf.Type<NoInfer<B>>, level: number) => D
}) => MTypes.OneArgFunction<Type<A, B>, Type<C, D>>

extendUp

Extends a tree in bottom-up order, transforming each node to a new value.

  • More powerful than {@link map}—receives the entire node (not just its value).
  • Processes tree bottom-up: leaves first, then non-leaves up to root.
  • Children are processed before their parent.
  • Functions receive the node itself and its level for context-aware transformation.
  • Use when transformation depends on processing children first.

Example (Extend up: aggregate child count)

import * as MTree from "@parischap/effect-lib/Tree/Tree"
import * as MTreeLeaf from "@parischap/effect-lib/Tree/TreeLeaf"
import * as MTreeNonLeaf from "@parischap/effect-lib/Tree/TreeNonLeaf"

const tree = MTreeNonLeaf.make({
  value: "root",
  forest: [MTreeLeaf.make("a"), MTreeLeaf.make("b")]
})
const extended = MTree.extendUp({
  fNonLeaf: (node, level) => node.forest.length,
  fLeaf: (leaf, level) => 0
})(tree)

Signature

export declare const extendUp: <A, B, C, D>({
  fNonLeaf,
  fLeaf
}: {
  readonly fNonLeaf: (tree: Type<NoInfer<A>, NoInfer<B>>, level: number) => C
  readonly fLeaf: (leaf: MTreeLeaf.Type<NoInfer<B>>, level: number) => D
}) => MTypes.OneArgFunction<Type<A, B>, Type<C, D>>

fold

Folds a tree into a summary value in bottom-up order.

  • Processes leaves first, then combines results upward.
  • Use to aggregate or transform tree data recursively.
  • foldLeaf handles terminal nodes; foldNonLeaf combines parent values with folded children.
  • Each function receives a level parameter for depth-aware logic.

Example (Fold tree to sum)

import * as MTree from "@parischap/effect-lib/Tree/Tree"
import * as MTreeLeaf from "@parischap/effect-lib/Tree/TreeLeaf"
import * as MTreeNonLeaf from "@parischap/effect-lib/Tree/TreeNonLeaf"

const tree = MTreeNonLeaf.make({
  value: 10,
  forest: [MTreeLeaf.make(5), MTreeLeaf.make(3)]
})
const sum = MTree.fold({
  foldLeaf: (n) => n,
  foldNonLeaf: (n, children) => n + children.reduce((a, b) => a + b, 0)
})(tree)
console.log(sum) // 18

Signature

export declare const fold: <A, B, C>({
  foldNonLeaf: fNonLeaf,
  foldLeaf: fLeaf
}: {
  readonly foldNonLeaf: (a: NoInfer<A>, bs: ReadonlyArray<C>, level: number) => C
  readonly foldLeaf: (a: NoInfer<B>, level: number) => C
}) => MTypes.OneArgFunction<Type<A, B>, C>

map

Maps a tree, transforming both leaf and non-leaf values.

  • Use to apply transformations to all node values.
  • Non-leaf values transformed via fNonLeaf; leaf values via fLeaf.
  • Both functions receive the node’s level (0 at root) for depth-aware logic.
  • Returns a new tree with transformed values (structure unchanged).

Example (Map tree values)

import * as MTree from "@parischap/effect-lib/Tree/Tree"
import * as MTreeLeaf from "@parischap/effect-lib/Tree/TreeLeaf"
import * as MTreeNonLeaf from "@parischap/effect-lib/Tree/TreeNonLeaf"

const tree = MTreeNonLeaf.make({
  value: "node",
  forest: [MTreeLeaf.make(5), MTreeLeaf.make(3)]
})
const mapped = MTree.map({
  fNonLeaf: (val) => val.toUpperCase(),
  fLeaf: (num) => num * 2
})(tree)

Signature

export declare const map: <A, B, C, D>({
  fNonLeaf,
  fLeaf
}: {
  readonly fNonLeaf: (a: NoInfer<A>, level: number) => C
  readonly fLeaf: (b: NoInfer<B>, level: number) => D
}) => MTypes.OneArgFunction<Type<A, B>, Type<C, D>>

mapAccum

Maps a tree with an accumulator in a top-down pass.

  • Use to transform both structure and values while threading state through the tree.
  • Leaf and non-leaf nodes processed separately with separate folding functions.
  • Level parameter indicates depth (0 at root).
  • Accumulator is passed down through the tree traversal.

Example (Map with accumulator)

import * as MTree from "@parischap/effect-lib/Tree/Tree"
import * as MTreeLeaf from "@parischap/effect-lib/Tree/TreeLeaf"
import * as MTreeNonLeaf from "@parischap/effect-lib/Tree/TreeNonLeaf"

const tree = MTreeNonLeaf.make({
  value: "root",
  forest: [MTreeLeaf.make(1), MTreeLeaf.make(2)]
})
const result = MTree.mapAccum({
  accum: 0,
  fNonLeaf: (s, val) => [s + 1, val.toUpperCase()],
  fLeaf: (s, val) => val * 10
})(tree)

Signature

export declare const mapAccum: <S, A, B, C, D>({
  accum,
  fNonLeaf,
  fLeaf
}: {
  readonly accum: S
  readonly fNonLeaf: (s: S, a: NoInfer<A>, level: number) => MTypes.Pair<S, C>
  readonly fLeaf: (s: S, b: NoInfer<B>, level: number) => D
}) => MTypes.OneArgFunction<Type<A, B>, Type<C, D>>

reduce

Reduces a tree to a summary value, processing children left to right.

  • Top-down traversal accumulating a result value.
  • Functions applied in order: non-leaf first, then each child in left-to-right order.
  • Each function receives the accumulator, node value, and depth level.
  • Use for aggregating properties or collecting information from the tree.

Example (Reduce tree)

import * as MTree from "@parischap/effect-lib/Tree/Tree"
import * as MTreeLeaf from "@parischap/effect-lib/Tree/TreeLeaf"
import * as MTreeNonLeaf from "@parischap/effect-lib/Tree/TreeNonLeaf"

const tree = MTreeNonLeaf.make({
  value: 1,
  forest: [MTreeLeaf.make(2), MTreeLeaf.make(3)]
})
const sum = MTree.reduce({
  z: 0,
  fNonLeaf: (acc, val) => acc + val,
  fLeaf: (acc, val) => acc + val
})(tree)
console.log(sum) // 6

Signature

export declare const reduce: <A, B, Z>({
  z,
  fNonLeaf,
  fLeaf
}: {
  readonly z: Z
  readonly fNonLeaf: (z: Z, a: NoInfer<A>, level: number) => Z
  readonly fLeaf: (z: Z, b: NoInfer<B>, level: number) => Z
}) => MTypes.OneArgFunction<Type<A, B>, Z>

reduceRight

Reduces a tree to a summary value, processing children right to left.

  • Top-down traversal accumulating a result value.
  • Functions applied in order: non-leaf first, then each child in right-to-left order.
  • Each function receives the accumulator, node value, and depth level.
  • Similar to {@link reduce} but with reversed child processing order.

Example (Reduce tree right-to-left)

import * as MTree from "@parischap/effect-lib/Tree/Tree"
import * as MTreeLeaf from "@parischap/effect-lib/Tree/TreeLeaf"
import * as MTreeNonLeaf from "@parischap/effect-lib/Tree/TreeNonLeaf"

const tree = MTreeNonLeaf.make({
  value: "A",
  forest: [MTreeLeaf.make("B"), MTreeLeaf.make("C")]
})
const result = MTree.reduceRight({
  z: "",
  fNonLeaf: (acc, val) => acc + val,
  fLeaf: (acc, val) => acc + val
})(tree)
console.log(result) // "ACB"

Signature

export declare const reduceRight: <A, B, Z>({
  z,
  fNonLeaf,
  fLeaf
}: {
  readonly z: Z
  readonly fNonLeaf: (z: Z, a: NoInfer<A>, level: number) => Z
  readonly fLeaf: (z: Z, b: NoInfer<B>, level: number) => Z
}) => MTypes.OneArgFunction<Type<A, B>, Z>