# precog/matryoshka architecture

> Architecture diagram of the GitHub repository precog/matryoshka, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-10-02). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/precog/matryoshka
- Repository: https://github.com/precog/matryoshka

## Overview

Matryoshka is a Scala library for generalized folds, unfolds, refolds, and traversals over fixed-point data structures. A user defines a one-layer algebra or coalgebra, chooses a recursive representation, and applies a recursion scheme to compute or transform a result. The graph preserves the documented fixed-point variants, pattern functors, and optional ScalaCheck support. Relationships among unsampled modules are omitted unless documented or visible in the supplied source index; dashed links mark documented capabilities whose implementation path was not sampled.

Main entry points: [`core/shared/src/main/scala/matryoshka/Birecursive.scala`](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Birecursive.scala) (Combined schemes), [`core/shared/src/main/scala/matryoshka/Delay.scala`](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Delay.scala) (Delayed instances), [`core/shared/src/main/scala/matryoshka/Recursive.scala`](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Recursive.scala) (Folds and traversals), [`core/shared/src/main/scala/matryoshka/package.scala`](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/package.scala) (Algebras and coalgebras)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_schemes["Recursion schemes"]
  node_algebras["Algebras and coalgebras<br/>[package.scala]"]
  node_recursive["Folds and traversals<br/>[Recursive.scala]"]
  node_corecursive["Unfolds<br/>[Corecursive.scala]"]
  node_birecursive["Combined schemes<br/>[Birecursive.scala]"]
  node_transformations["Transformations and refolds<br/>[package.scala]"]
  node_recursive_t["RecursiveT<br/>[RecursiveT.scala]"]
  node_corecursive_t["CorecursiveT<br/>[CorecursiveT.scala]"]
  node_birecursive_t["BirecursiveT<br/>[BirecursiveT.scala]"]
end

subgraph group_representations["Fixed-point types"]
  node_fix["Fix<br/>[Fix.scala]"]
  node_mu["Mu<br/>[Mu.scala]"]
  node_nu["Nu<br/>[Nu.scala]"]
  node_cofree["Cofree<br/>[cofree.scala]"]
  node_free["Free<br/>[free.scala]"]
end

subgraph group_patterns["Patterns and utilities"]
  node_delay["Delayed instances<br/>[Delay.scala]"]
  node_equal_t["EqualT<br/>[EqualT.scala]"]
  node_show_t["ShowT<br/>[ShowT.scala]"]
  node_merge["Merge<br/>[Merge.scala]"]
  node_and_maybe["AndMaybe<br/>[AndMaybe.scala]"]
  node_coenv["CoEnv<br/>[CoEnv.scala]"]
  node_diff["Diff<br/>[Diff.scala]"]
  node_envt["EnvT<br/>[EnvT.scala]"]
  node_listf["ListF<br/>[ListF.scala]"]
end

subgraph group_generators["ScalaCheck support"]
  node_arbitrary["Arbitrary instances<br/>[arbitrary.scala]"]
  node_cogen["Cogen instances<br/>[cogen.scala]"]
  node_shrink["Shrink instances<br/>[shrink.scala]"]
end

node_user(("Library user"))
node_result(("Computed result"))

node_user -->|"defines operations"| node_algebras
node_user -->|"chooses representation"| node_fix
node_algebras -->|"folds with"| node_recursive
node_algebras -->|"unfolds with"| node_corecursive
node_recursive -->|"computes result"| node_result
node_user -.->|"may apply"| node_transformations
node_user -.->|"may apply"| node_birecursive
node_birecursive -->|"extends"| node_recursive
node_birecursive -->|"extends"| node_corecursive
node_birecursive_t -->|"extends"| node_recursive_t
node_birecursive_t -->|"extends"| node_corecursive_t
node_recursive_t -->|"supports workaround"| node_diff
node_recursive_t -.->|"supports workaround"| node_and_maybe
node_fix -->|"implements instances"| node_birecursive
node_mu -->|"implements instances"| node_birecursive
node_nu -->|"implements instances"| node_birecursive
node_cofree -->|"uses representation"| node_envt
node_free -->|"uses representation"| node_coenv
node_birecursive -->|"uses merge"| node_merge
node_diff -->|"defers instances"| node_delay
node_coenv -->|"defers instances"| node_delay
node_envt -->|"defers instances"| node_delay
node_listf -->|"uses recursive API"| node_recursive
node_equal_t -->|"uses delayed instances"| node_delay
node_show_t -->|"uses delayed instances"| node_delay
node_user -.->|"optionally generates"| node_arbitrary
node_user -.->|"optionally generates"| node_cogen
node_user -.->|"optionally generates"| node_shrink

click node_algebras "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/package.scala"
click node_recursive "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Recursive.scala"
click node_corecursive "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Corecursive.scala"
click node_birecursive "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Birecursive.scala"
click node_transformations "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/package.scala"
click node_recursive_t "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/RecursiveT.scala"
click node_corecursive_t "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/CorecursiveT.scala"
click node_birecursive_t "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/BirecursiveT.scala"
click node_fix "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/Fix.scala"
click node_mu "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/Mu.scala"
click node_nu "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/Nu.scala"
click node_cofree "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/cofree.scala"
click node_free "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/free.scala"
click node_delay "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Delay.scala"
click node_equal_t "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/EqualT.scala"
click node_show_t "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/ShowT.scala"
click node_merge "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Merge.scala"
click node_and_maybe "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/AndMaybe.scala"
click node_coenv "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/CoEnv.scala"
click node_diff "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/Diff.scala"
click node_envt "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/EnvT.scala"
click node_listf "https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/ListF.scala"
click node_arbitrary "https://github.com/precog/matryoshka/blob/master/scalacheck/shared/src/main/scala/matryoshka/scalacheck/arbitrary.scala"
click node_cogen "https://github.com/precog/matryoshka/blob/master/scalacheck/shared/src/main/scala/matryoshka/scalacheck/cogen.scala"
click node_shrink "https://github.com/precog/matryoshka/blob/master/scalacheck/shared/src/main/scala/matryoshka/scalacheck/shrink.scala"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_algebras,node_recursive,node_corecursive,node_birecursive,node_transformations,node_recursive_t,node_corecursive_t,node_birecursive_t,node_user toneBlue
class node_fix,node_mu,node_nu,node_cofree,node_free toneAmber
class node_delay,node_equal_t,node_show_t,node_merge,node_and_maybe,node_coenv,node_diff,node_envt,node_listf toneMint
class node_arbitrary,node_cogen,node_shrink toneRose
class node_result toneIndigo
```

## Components

### Recursion schemes

- [Algebras and coalgebras](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/package.scala): `core/shared/src/main/scala/matryoshka/package.scala`
- [Folds and traversals](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Recursive.scala): `core/shared/src/main/scala/matryoshka/Recursive.scala`
- [Unfolds](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Corecursive.scala): `core/shared/src/main/scala/matryoshka/Corecursive.scala`
- [Combined schemes](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Birecursive.scala): `core/shared/src/main/scala/matryoshka/Birecursive.scala`
- [Transformations and refolds](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/package.scala): `core/shared/src/main/scala/matryoshka/package.scala`
- [RecursiveT](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/RecursiveT.scala): `core/shared/src/main/scala/matryoshka/RecursiveT.scala`
- [CorecursiveT](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/CorecursiveT.scala): `core/shared/src/main/scala/matryoshka/CorecursiveT.scala`
- [BirecursiveT](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/BirecursiveT.scala): `core/shared/src/main/scala/matryoshka/BirecursiveT.scala`

### Fixed-point types

- [Fix](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/Fix.scala): `core/shared/src/main/scala/matryoshka/data/Fix.scala`
- [Mu](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/Mu.scala): `core/shared/src/main/scala/matryoshka/data/Mu.scala`
- [Nu](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/Nu.scala): `core/shared/src/main/scala/matryoshka/data/Nu.scala`
- [Cofree](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/cofree.scala): `core/shared/src/main/scala/matryoshka/data/cofree.scala`
- [Free](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/data/free.scala): `core/shared/src/main/scala/matryoshka/data/free.scala`

### Patterns and utilities

- [Delayed instances](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Delay.scala): `core/shared/src/main/scala/matryoshka/Delay.scala`
- [EqualT](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/EqualT.scala): `core/shared/src/main/scala/matryoshka/EqualT.scala`
- [ShowT](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/ShowT.scala): `core/shared/src/main/scala/matryoshka/ShowT.scala`
- [Merge](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/Merge.scala): `core/shared/src/main/scala/matryoshka/Merge.scala`
- [AndMaybe](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/AndMaybe.scala): `core/shared/src/main/scala/matryoshka/patterns/AndMaybe.scala`
- [CoEnv](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/CoEnv.scala): `core/shared/src/main/scala/matryoshka/patterns/CoEnv.scala`
- [Diff](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/Diff.scala): `core/shared/src/main/scala/matryoshka/patterns/Diff.scala`
- [EnvT](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/EnvT.scala): `core/shared/src/main/scala/matryoshka/patterns/EnvT.scala`
- [ListF](https://github.com/precog/matryoshka/blob/master/core/shared/src/main/scala/matryoshka/patterns/ListF.scala): `core/shared/src/main/scala/matryoshka/patterns/ListF.scala`

### ScalaCheck support

- [Arbitrary instances](https://github.com/precog/matryoshka/blob/master/scalacheck/shared/src/main/scala/matryoshka/scalacheck/arbitrary.scala): `scalacheck/shared/src/main/scala/matryoshka/scalacheck/arbitrary.scala`
- [Cogen instances](https://github.com/precog/matryoshka/blob/master/scalacheck/shared/src/main/scala/matryoshka/scalacheck/cogen.scala): `scalacheck/shared/src/main/scala/matryoshka/scalacheck/cogen.scala`
- [Shrink instances](https://github.com/precog/matryoshka/blob/master/scalacheck/shared/src/main/scala/matryoshka/scalacheck/shrink.scala): `scalacheck/shared/src/main/scala/matryoshka/scalacheck/shrink.scala`

### Other components

- **Library user**
- **Computed result**

## Connections

- Library user → Algebras and coalgebras: defines operations
- Library user → Fix: chooses representation
- Algebras and coalgebras → Folds and traversals: folds with (evidence: `core/shared/src/main/scala/matryoshka/package.scala`)
- Algebras and coalgebras → Unfolds: unfolds with (evidence: `core/shared/src/main/scala/matryoshka/package.scala`)
- Folds and traversals → Computed result: computes result
- Library user → Transformations and refolds: may apply
- Library user → Combined schemes: may apply
- Combined schemes → Folds and traversals: extends (evidence: `core/shared/src/main/scala/matryoshka/Birecursive.scala`)
- Combined schemes → Unfolds: extends (evidence: `core/shared/src/main/scala/matryoshka/Birecursive.scala`)
- BirecursiveT → RecursiveT: extends (evidence: `core/shared/src/main/scala/matryoshka/BirecursiveT.scala`)
- BirecursiveT → CorecursiveT: extends (evidence: `core/shared/src/main/scala/matryoshka/BirecursiveT.scala`)
- RecursiveT → Diff: supports workaround (evidence: `core/shared/src/main/scala/matryoshka/RecursiveT.scala`)
- RecursiveT → AndMaybe: supports workaround
- Fix → Combined schemes: implements instances (evidence: `core/shared/src/main/scala/matryoshka/data/Fix.scala`)
- Mu → Combined schemes: implements instances (evidence: `core/shared/src/main/scala/matryoshka/data/Mu.scala`)
- Nu → Combined schemes: implements instances (evidence: `core/shared/src/main/scala/matryoshka/data/Nu.scala`)
- Cofree → EnvT: uses representation (evidence: `core/shared/src/main/scala/matryoshka/patterns/EnvT.scala`)
- Free → CoEnv: uses representation (evidence: `core/shared/src/main/scala/matryoshka/data/free.scala`)
- Combined schemes → Merge: uses merge (evidence: `core/shared/src/main/scala/matryoshka/Birecursive.scala`)
- Diff → Delayed instances: defers instances (evidence: `core/shared/src/main/scala/matryoshka/patterns/Diff.scala`)
- CoEnv → Delayed instances: defers instances (evidence: `core/shared/src/main/scala/matryoshka/patterns/CoEnv.scala`)
- EnvT → Delayed instances: defers instances (evidence: `core/shared/src/main/scala/matryoshka/patterns/EnvT.scala`)
- ListF → Folds and traversals: uses recursive API (evidence: `core/shared/src/main/scala/matryoshka/patterns/ListF.scala`)
- EqualT → Delayed instances: uses delayed instances (evidence: `core/shared/src/main/scala/matryoshka/EqualT.scala`)
- ShowT → Delayed instances: uses delayed instances (evidence: `core/shared/src/main/scala/matryoshka/ShowT.scala`)
- Library user → Arbitrary instances: optionally generates
- Library user → Cogen instances: optionally generates
- Library user → Shrink instances: optionally generates
