HackerPapers

arXiv:2005.08856math.CO

How to generate random lambda terms?

Maciej Bendkowski

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

We survey several methods of generating large random lambda-terms, focusing on their closed and simply-typed variants. We discuss methods of exact- and approximate-size generation, as well as methods of achieving size-uniform and non-uniform outcome distributions.

arXiv comments
Fixed typo in the S-combinator
Journal reference
DOI
Subjects
math.COCombinatorics cs.DSData Structures and Algorithms cs.LOLogic in Computer Science cs.SESoftware Engineering

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Aug 2024 to Aug 2024.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Discovering algorithms by enumerating terms in Haskell 1 comment

    • Maciej Bendkowski has some related work [1] on generating random lambda terms, but was unable to overcome what he calls the asymptotic sparsity problem: Sampling simply-typed terms seems notoriously more challenging than sampling closed ones. Even rejection sampling, whenever…

      bmc7505View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.