Natural Program Synthesis in Haskell: Leveraging Refinement Types for Readable and Scalable Code Generation
摘要
We present a novel programming-by-example (PBE) approach that synthesizes natural and human-readable code by integrating higher-order functions with standard and third-party libraries in Haskell. This technique leverages refinement types to efficiently prune the search space, ensuring scalability while preserving soundness. Using Liquid Haskell, we extend support for complex data structures, enabling the synthesis of reusable and idiomatic code. Our evaluation demonstrates the tool’s versatility across lists, trees, maps, and domain-specific languages, including musical scores. The results highlight that our method generates concise, interpretable programs, bridging the gap between formal verification and practical usability in functional programming.