Metraipolis › archive › dc_14cb8250d307
A Cost-Aware Probability Monad for Liquid Haskell — arXiv:2608.04886
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.04886
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T11:59:43.878Z
- SHA-256 of the archived text
2aad573b418fd008ed333a8cce51b0374a749fc82bf8eb72a10bc4559c3941c8- Stable URL of this page
https://metraipolis.com/documento/dc_14cb8250d307
How to cite
A Cost-Aware Probability Monad for Liquid Haskell — arXiv:2608.04886 — arXiv (en), https://arxiv.org/abs/2608.04886 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_14cb8250d307 (Metraipolis archive dc_14cb8250d307, sha256 2aad573b418fd008ed333a8cce51b0374a749fc82bf8eb72a10bc4559c3941c8)
BibTeX
@misc{dc14cb8250d307,
title = {A Cost-Aware Probability Monad for Liquid Haskell — arXiv:2608.04886},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.04886},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_14cb8250d307; sha256 2aad573b418fd008ed333a8cce51b0374a749fc82bf8eb72a10bc4559c3941c8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04886. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Probabilistic algorithms and data structures are widely used to obtain favourable expected performance guarantees. While their mathematical analysis is often well understood, mechanising expected-cost analyses remains challenging, requiring reasoning about probability distributions, expectations, and recursive stochastic behaviour. Existing formal approaches frequently require substantial manual proof effort, since expected costs are often encoded separately from probabilistic computations and must therefore be propagated explicitly throughout proofs. In this paper, we present a cost-aware probability monad for \LH/ that supports reasoning about probabilistic programs together with their expected costs. Our approach combines executable probabilistic programs with refinement-type-based verification and SMT-supported automation. The monad intrinsically tracks probability mass, expected values, and expected costs through refinement types, enabling many quantitative properties of probabilistic computations to be inferred compositionally from program structure. We evaluate our approach on several classical probabilistic algorithms and data structures, including meldable heaps, randomised quicksort and quickselect, randomised splay trees, random permutations, and the hiring problem. The case studies demonstrate different points along the spectrum between automated and interactive verification. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in cs.LO). Categorie arXiv: Logic in Computer Science (cs.LO). Pagina del lavoro: https://arxiv.org/abs/2608.04886 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-31T11:47:54.018Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).