Functional Programming & Lambda Calculus with Haskell - Expanded Projects
Functional Programming & Lambda Calculus with Haskell - Expanded Projects
A Project-Based Deep Dive into the Foundations of Computation
This directory contains comprehensive, expanded learning guides for each project in the Functional Programming & Lambda Calculus curriculum. Each project guide includes deep theoretical foundations, solution architecture, implementation guidance, and real-world connections.
Overview
Lambda calculus is not just a programming technique—it’s the mathematical theory of computation itself. Created by Alonzo Church in the 1930s, it predates computers and proved that functions alone are sufficient to express any computation.
Haskell is the purest practical embodiment of these ideas. Unlike languages that bolt on functional features, Haskell is lambda calculus extended with a type system, lazy evaluation, and syntactic sugar.
Project Index
Phase 1: Lambda Calculus Foundations
| # | Project | Difficulty | File |
|---|---|---|---|
| 1 | Pure Lambda Calculus Interpreter | Advanced | P01-pure-lambda-calculus-interpreter.md |
| 2 | Church Encodings | Advanced | P02-church-encodings.md |
| 3 | Reduction Visualizer | Advanced | P03-reduction-visualizer.md |
Phase 2: Type Systems
| # | Project | Difficulty | File |
|---|---|---|---|
| 4 | Simply Typed Lambda Calculus + Type Inference | Expert | P04-simply-typed-lambda-calculus-type-inference.md |
Phase 3: Haskell Fundamentals
| # | Project | Difficulty | File |
|---|---|---|---|
| 5 | Algebraic Data Types and Pattern Matching | Intermediate | P05-algebraic-data-types-pattern-matching.md |
| 6 | The Functor-Applicative-Monad Hierarchy | Expert | P06-functor-applicative-monad-hierarchy.md |
Phase 4: Practical Haskell
| # | Project | Difficulty | File |
|---|---|---|---|
| 7 | Parser Combinator Library | Advanced | P07-parser-combinator-library.md |
| 8 | Lazy Evaluation Demonstrator | Expert | P08-lazy-evaluation-demonstrator.md |
| 9 | Monad Transformers from Scratch | Expert | P09-monad-transformers-from-scratch.md |
| 10 | Property-Based Testing Framework | Advanced | P10-property-based-testing-framework.md |
Phase 5: Advanced Topics
| # | Project | Difficulty | File |
|---|---|---|---|
| 11 | Lenses and Optics Library | Expert | P11-lenses-and-optics-library.md |
| 12 | Free Monad DSL | Master | P12-free-monad-dsl.md |
| 13 | Category Theory Visualizer | Expert | P13-category-theory-visualizer.md |
Phase 6: Language Implementation
| # | Project | Difficulty | File |
|---|---|---|---|
| 14 | Lisp Interpreter in Haskell | Advanced | P14-lisp-interpreter-in-haskell.md |
| 15 | Compile Functional Language to LLVM/C | Master | P15-compile-functional-language-to-llvm.md |
Learning Path Recommendations
For Beginners to Functional Programming
Start with Projects 5 → 6 → 1 → 2 to build intuition before diving into theory.
For Those with FP Experience
Start with Projects 1 → 2 → 4 to deepen theoretical understanding.
For Practical Application
Focus on Projects 7 → 10 → 9 → 11 for immediately useful skills.
For Compiler/Language Enthusiasts
Work through Projects 1 → 4 → 14 → 15 sequentially.
Core Concepts Covered
| Concept Area | Projects | What You’ll Understand |
|---|---|---|
| Lambda Calculus | 1, 2, 3 | Variables, abstraction, application, reduction, Church encodings, fixed points |
| Type Systems | 4 | Hindley-Milner inference, algebraic data types, parametric polymorphism |
| Higher-Order Functions | 5, 6 | Functions as values, currying, composition, point-free style |
| Laziness | 8 | Thunks, infinite data structures, call-by-need evaluation |
| Type Classes | 6, 9, 11 | Ad-hoc polymorphism, Functor, Applicative, Monad, and beyond |
| Category Theory | 13 | Functors, natural transformations, monads as mathematical objects |
| Effects | 9, 12 | IO, State, Reader, Writer, monad transformers |
| Parsing | 7 | Combinator-based parsing, grammar representation |
| Testing | 10 | Property-based testing, generators, shrinking |
| Language Implementation | 14, 15 | Interpreters, compilers, code generation |
Essential Resources
Books
- “Haskell Programming from First Principles” by Allen & Moronuki - Best introduction
- “Learn You a Haskell for Great Good!” by Miran Lipovača - Fun and visual
- “Programming in Haskell” by Graham Hutton - Academic but practical
- “Types and Programming Languages” by Benjamin Pierce - Type theory bible
- “Category Theory for Programmers” by Bartosz Milewski - CT for coders
- “Haskell in Depth” by Vitaly Bragilevsky - Real-world Haskell
- “Optics By Example” by Chris Penner - Deep dive into lenses
Papers
- “A Tutorial Introduction to the Lambda Calculus” - Raúl Rojas
- “Monadic Parsing in Haskell” - Hutton & Meijer
- “QuickCheck: A Lightweight Tool for Random Testing” - Claessen & Hughes
- “Why Free Monads Matter” - Gabriel Gonzalez
Online Resources
Project Difficulty Legend
| Level | Description | Prerequisites |
|---|---|---|
| Intermediate | Comfortable with basic Haskell | Basic syntax, recursion |
| Advanced | Solid Haskell foundation | Type classes, monads |
| Expert | Deep understanding required | Advanced type system features |
| Master | Research-level complexity | All previous levels |
“A monad is just a monoid in the category of endofunctors, what’s the problem?”
After completing these projects, you’ll actually understand what that means.