Purely functional lazy non-deterministic programming

Sebastian Fischer, Oleg Kiselyov, Chung Chieh Shan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Citations (Scopus)


Functional logic programming and probabilistic programming have demonstrated the broad benefits of combining laziness (non-strict evaluation with sharing of the results) with non-determinism. Yet these benefits are seldom enjoyed in functional programming, because the existing features for non-strictness, sharing, and nondeterminism in functional languages are tricky to combine. We present a practical way to write purely functional lazy non-deterministic programs that are efficient and perspicuous. We achieve this goal by embedding the programs into existing languages (such as Haskell, SML, and OCaml) with high-quality implementations, by making choices lazily and representing data with non-deterministic components, by working with custom monadic data types and search strategies, and by providing equational laws for the programmer to reason about their code. Copyrightc 2009 ACM.

Original languageEnglish
Title of host publicationICFP'09 - Proceedings of the 2009 ACM SIGPLAN International Conference on Functional Programming
Number of pages12
Publication statusPublished - 2009
Event2009 ACM SIGPLAN International Conference on Functional Programming, ICFP'09 - Edinburgh, United Kingdom
Duration: 2009 Aug 312009 Sept 2

Publication series

NameProceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP


Conference2009 ACM SIGPLAN International Conference on Functional Programming, ICFP'09
Country/TerritoryUnited Kingdom


  • Call-time choice
  • Continuations
  • Monads
  • Side effects


Dive into the research topics of 'Purely functional lazy non-deterministic programming'. Together they form a unique fingerprint.

Cite this