Matryoshka
A Scala library providing generalized recursion schemes and traversals for fixed point data structures.
What is Matryoshka?
Matryoshka is a Scala library that implements generalized recursion schemes—such as folds, unfolds, and traversals—for fixed point data structures. It allows developers to abstract recursion away from business logic, enabling modular and composable transformations on recursive types like trees and lists. The library is based on academic research in functional programming and category theory.
Scala developers working with complex recursive data structures, such as compilers, interpreters, or data transformation pipelines, who want to apply formal recursion schemes for cleaner, more maintainable code.
Matryoshka provides a comprehensive, type-safe implementation of recursion schemes in Scala, reducing boilerplate and errors associated with manual recursion. It integrates with popular functional libraries like Scalaz and Cats, offering a robust alternative to ad-hoc recursive functions.
Overview
Generalized recursion schemes and traversals for Scala.
Use Cases
Best For
- Implementing compilers or interpreters with nanopass architectures
- Transforming abstract syntax trees (ASTs) in functional languages
- Writing reusable folds and unfolds for complex nested data
- Applying catamorphisms and anamorphisms to tree-like structures
- Generalizing recursive algorithms using type classes
- Learning and applying formal recursion schemes from academic papers
Not Ideal For
- Projects using imperative or object-oriented Scala without functional libraries like Cats or Scalaz
- Simple recursive tasks where manual recursion is straightforward and doesn't justify the abstraction overhead
- Teams with tight deadlines or limited experience in category theory and recursion schemes
- Environments stuck on Scala versions below 2.12 that cannot support partial unification
Pros & Cons
Pros
Implements a wide range of schemes like cata, ana, para, and histo, enabling expressive and reusable transformations for complex recursive data structures, as detailed in the cheat-sheet and academic references.
Integrates seamlessly with Scala's type system and libraries like Cats/Scalaz through type classes such as Recursive and Corecursive, ensuring compile-time safety and reducing errors in recursive logic.
Separates recursion from business logic using algebras and coalgebras, making code more maintainable and composable, as demonstrated in the example where eval algebra is applied independently of the fixed point type.
Based on well-researched concepts from functional programming papers, supporting generalized forms like G-algebras and Elgot algebras for advanced use cases, which is highlighted in the generalization section.
Cons
Requires specific Scala compiler settings like '-Ypartial-unification' or a plugin for SI-2712 fix, adding initial setup complexity that can hinder quick adoption.
Assumes deep familiarity with advanced FP concepts like fixed points, comonads, and monads, making it inaccessible for developers without a background in recursion schemes or category theory.
The README admits that direct implementations (e.g., cata) might perform better than generalized versions, and benchmarks are lacking, posing risks for performance-critical applications.
With only Quasar listed as a user and reliance on academic papers for guidance, the library has a niche community and fewer practical examples compared to mainstream alternatives.
Frequently Asked Questions
Found a gem we're missing?
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.