[DSRP Evidence](https://dsrpevidence.org/)

# Compositional Generator Equivalence

## Details

**Authors** Vandikas et al.

**Year** 2026

**Publisher** Proceedings of the ACM on Programming Languages (ICFP)

**Discipline** Computer Science & AI

[Read it at the publisher](https://doi.org/10.1145/3828695) 
10.1145/3828695

## In authors' words

### What they found (results)

The authors prove that Hedgehog's standard generator semantics is non-compositional, that any sound-and-complete compositional semantics for it must collapse to the fine-grained sampling semantics, and introduce a restricted language, Hedgehog->, that does admit a genuinely compositional semantics, implemented and evaluated in Haskell.

## Commentary

### In short

Whether a generator's whole behavior can be soundly justified from a coarse composition of its parts, versus needing the fine-grained whole, is a parts-whole systems question, and the proof turns on a hard line between the two granularities of semantics.

**Patterns it shows** D, S

**Added** 2026-08-22

**How to cite this** Vandikas et al. (2026). Compositional Generator Equivalence. Proceedings of the ACM on Programming Languages (ICFP).