[Paper] Functional Program Synthesis with Higher-Order Functions and Recursion Schemes

Source: arXiv - 2511.23354v1

Overview

This paper introduces two new genetic‑programming (GP) techniques—HOTGP and Origami—that can automatically generate pure, typed functional programs (Haskell code) from input‑output examples. By leveraging strong type information, higher‑order functions, and recursion‑scheme templates, the authors dramatically shrink the search space, making synthesis competitive with state‑of‑the‑art tools and even large language models (LLMs).

Key Contributions

• HOTGP: A GP system that works directly with Haskell’s type system, supporting higher‑order functions, lambda abstractions, and parametric polymorphism.
• Origami: A novel GP algorithm that synthesizes programs by filling in the “holes” of well‑known recursion schemes (e.g., folds, unfolds, catamorphisms).
• AC/DC Search Procedure: An adaptive exploration strategy for Origami that boosts success rates across all benchmark families.
• Empirical Benchmarking: Demonstrates that Origami solves more problems than any prior GP method, achieving 100 % success on 18 % of the PSB2 benchmark suite and outperforming Copilot (an LLM‑based synthesizer) in overall win‑rate.
• First GP Approach to Reach 100 % Success on Any PSB2 Problem: Sets a new baseline for functional program synthesis.

Methodology

1. Typed Functional Grammar – HOTGP builds candidate programs using a grammar that respects Haskell’s type rules. Types prune invalid programs early, so the evolutionary search never wastes time on ill‑typed candidates.
2. Higher‑Order Building Blocks – The system can insert functions like map, filter, or user‑defined combinators as first‑class citizens, allowing compact representations of complex behavior.
3. Recursion Schemes as Templates – Origami treats common recursion patterns (e.g., foldr, unfoldr, para) as fixed scaffolds. Only the small “hole” functions (the algebra) need to be discovered, turning a huge search problem into a tiny one.
4. AC/DC (Adaptive Crossover / Directed Culling) – During evolution, AC/DC dynamically adjusts crossover operators to favor promising sub‑trees and discards low‑fitness individuals more aggressively, improving convergence speed.
5. Evaluation – Both systems are tested on standard functional synthesis benchmarks (PSB2, SRBench, etc.) and compared against leading GP frameworks and LLM‑based synthesizers like Copilot.

Results & Findings

• HOTGP matches or exceeds the success rates of existing GP tools on most benchmarks while handling richer language features (higher‑order, polymorphic types).
• Origami (v2 with AC/DC) solves 100 % of the problems in several benchmark groups, the highest count among all GP approaches.
• On the full PSB2 suite, Origami attains a 100 % success rate on 18 % of the problems—the only method to do so.
• Compared to Copilot, Origami wins more benchmark instances overall, showing that a well‑engineered GP system can still compete with modern LLMs in functional synthesis.
• The AC/DC enhancement yields a significant jump in success percentages across the board (e.g., from ~60 % to >80 % on medium‑difficulty tasks).

Practical Implications

• Automated Refactoring & Boilerplate Generation – Developers can use HOTGP/Origami to synthesize small pure functions (e.g., data‑transform pipelines) from example inputs, reducing manual coding effort.
• Domain‑Specific Language (DSL) Prototyping – By providing type signatures and example behaviours, teams can quickly generate DSL combinators without hand‑crafting recursion logic.
• Education & Onboarding – New Haskell learners can experiment with example‑driven synthesis to see how higher‑order patterns emerge, accelerating learning of functional idioms.
• Integration with CI Pipelines – The algorithms could be wrapped as a service that attempts to auto‑complete missing implementations during code reviews, flagging cases where synthesis fails for human attention.
• Competitive Edge over LLMs – For security‑sensitive or highly typed codebases, a type‑driven GP approach guarantees type‑correctness by construction, something that LLMs only approximate.

Limitations & Future Work

• Scalability to Large Codebases – While recursion‑scheme templates shrink the search space, synthesizing large, multi‑module programs remains out of reach.
• Dependence on Rich Type Annotations – The approach assumes accurate, expressive type signatures; ambiguous or missing types degrade performance.
• Limited to Pure Functional Subset – Side‑effects, monadic I/O, and concurrency constructs are not handled in the current version.
• Search Overhead – Despite AC/DC improvements, the evolutionary process can still be computationally intensive for very deep recursion schemes.

Future research directions include extending the grammar to cover monadic patterns, hybridizing GP with neural guidance (e.g., using LLMs to propose candidate holes), and scaling the system to handle real‑world codebases through modular synthesis and incremental learning.

Authors

• Matheus Campos Fernandes

Paper Information

• arXiv ID: 2511.23354v1
• Categories: cs.NE
• Published: November 28, 2025
• PDF: Download PDF