F# Snippets

A curated collection of functional programming patterns and advanced techniques implemented in F#

Overview

This repository showcases various functional programming concepts, from lazy evaluation and staging to type-level programming and advanced abstractions. Each snippet is self-contained and demonstrates idiomatic F# code, exploring the boundaries of what's possible in F#.

Snippets

Lazy Evaluation & Circular Programming

File	Description
LazyList.fsx	Infinite lazy lists with functional operations
Lazy fixed-point and Infinite Streams.fsx	Lazy fixed-point combinator with infinite stream examples
A Lazy fixed-point combinator.fsx	Lazy fixed-point combinator for defining recursive values
Fixed-point finding function.fsx	Classic fixed-point finding implementation
GC Friendly Fixpoint.fsx	Memory-efficient fixed-point combinator
Polyvariadic fixpoint.fsx	Fixed-point combinator with variable arity
LazyBFSTreeLabeling.fsx	Breadth-first tree labeling using circular programming
LazyGenNameLambda.fsx	Fresh name generation using circular programs
The repmin problem.fsx	Bird's classic repmin problem using circular programming
From Löb's Theorem to Spreadsheet Evaluation.fsx	Löb's theorem as a spreadsheet evaluator
From Löb's Theorem to Spreadsheet Evaluation (memoized).fsx	Memoized version of spreadsheet evaluation
Lazy Xml.fsx	Lazy XML processing
Infinite sequences.fsx	Working with infinite sequences

Continuations & Control Flow

File	Description
Delimited continuations.fsx	Shift/reset operators for delimited continuations
yin-yang puzzle.fsx	The famous Yin-Yang puzzle demonstrating first-class continuations
Eff.fsx	Algebraic effects and handlers
Eff via delimited continuations.fsx	Implementing effects using delimited continuations
Effects and Handlers.fsx	Effect system with handlers

Monads & Abstractions

File	Description
Functor - Applicative - Monad.fsx	Category theory abstractions in F#
Abstracting over 'M'.fsx	Higher-kinded type abstraction patterns
Monadic Memoization.fsx	Memoization using monadic patterns
Monadic Retry.fsx	Retry logic with monads
Monadic Trampoline.fsx	Stack-safe recursion via trampolines
Async Choice.fsx	Async workflows with choice operations
Staged Free Monads.fsx	Free monads with multi-stage programming

Multi-Stage Programming

File	Description
Staged Fixed-point combinator.fsx	Staged fixed-point combinator
Yet another staged fixed-point combinator.fsx	Alternative staged fixed-point implementation
Staged Ackermann.fsx	Staged version of the Ackermann function
Staged Parser Combinators.fsx	Parser combinators with staging
Staged Regular Expression Matcher.fsx	Staged regex matcher
Staged CPS Regular Expression Matcher.fsx	CPS-style staged regex matcher
Staged Trampoline.fsx	Staged trampoline for stack-safe recursion
Staged Monoidal Folds.fsx	Staged folding operations
Staged Reducers.fsx	Staged reducers for efficient data processing
Staged HOAS.fsx	Higher-order abstract syntax with staging
Staged typed formatting.fsx	Type-safe formatting with staging
Staged Functional Unparsing.fsx	Staged unparsing for pretty-printing
Staged Ziria Streams.fsx	Stream processing with staging
Staged Parallel Ziria Streams.fsx	Parallel stream processing with staging
Lightweight Staged Numeric code.fsx	Staged numeric computations
Stage your boilerplate.fsx	Generic programming with staging

Type-Level Programming

File	Description
HLists, Peano - Type-level computations.fsx	Heterogeneous lists and Peano arithmetic at the type level
Type-level Fold.fsx	Folding at the type level
Type-level SAT solver.fsx	SAT solver implemented at the type level
Generic Numeric Literals and Compile time Peano arithmetic.fsx	Compile-time arithmetic with Peano numbers
Type Safe Higher-order abstract syntax.fsx	Type-safe HOAS representation
Session Types.fsx	Session types for communication protocols
Equality Type.fsx	Type equality proofs

Generic Programming & Data Types

File	Description
Generic Collections, Type Classes and friends.fsx	Type class patterns and generic collections
Scrap Your Boilerplate.fsx	Generic programming à la "Scrap Your Boilerplate"
Scrap Your Boilerplate (with class).fsx	SYB using type classes
Bananas.fsx	Catamorphisms, anamorphisms, and other -morphisms
Hughes's FuncList.fsx	Hughes's functional lists with O(1) append
Hughes's CPSFuncList.fsx	CPS-style functional lists
Reducers.fsx	Rich Hickey's reducers pattern in F#

Language Implementations & Interpreters

File	Description
Church numerals.fsx	Church encoding of natural numbers
Unlambda.fsx	Interpreter for the Unlambda esoteric language
Normalisation by evaluation.fsx	Normalization by evaluation for lambda calculus
Functional style Regex engine.fsx	Regular expression engine in functional style
Type based Regex Active Patterns.fsx	Type-indexed regex active patterns
Quotations to A-Normal form.fsx	Converting F# quotations to A-normal form

Actors & Concurrency

File	Description
Actors acting as Lambdas.fsx	Actor model as lambda calculus
Clojure's Atoms.fsx	Clojure-style atoms in F#
Clojure atom memoization example.fsx	Memoization using atoms
Dining philosophers (Joinads).fsx	Classic dining philosophers using joinads

Puzzles & Applications

File	Description
Countdown.fsx	The countdown numbers game solver
Eternity2.fsx	Eternity II puzzle solver
Life.fsx	Conway's Game of Life
Evens and Odds via Z3.fsx	Using Z3 solver for even/odd problems
Norvig's Spelling Corrector.fsx	Peter Norvig's spelling corrector in F#
Erik Lippert's Comma Quibbling.fsx	Comma quibbling problem solution

Utilities & Miscellaneous

File	Description
n-ary Seq.map.fsx	n-ary version of Seq.map
n-ary Seq.map (Numerals).fsx	n-ary Seq.map using Church numerals
Y(n) Polyvariadic fixpoint.fsx	Polyvariadic Y combinator
YIntensional.fsx	Intensional Y combinator
Functional Unparsing SQL.fsx	SQL pretty-printing using functional unparsing
Loop Unrolling.fsx	Compile-time loop unrolling
A simple Quine.fsx	A self-reproducing program

Getting Started

Prerequisites

• .NET SDK (F# included)
• A text editor or IDE with F# support (VS Code with Ionide, Visual Studio, or JetBrains Rider)

Running Examples

Most snippets are self-contained F# script files (.fsx) that can be executed directly:

dotnet fsi "src/FSharpSnippets/Church numerals.fsx"

Or load them interactively in F# Interactive:

dotnet fsi
> #load "src/FSharpSnippets/Church numerals.fsx";;

References

• Using Circular Programs for Higher-Order Syntax
• From Löb's Theorem to Spreadsheet Evaluation
• Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming
• Delimited Continuations in Operating Systems
• Lightweight Modular Staging

License

See LICENSE for details.