Functional programming: a reading path to think in functions
This curriculum builds deep functional programming mastery across three tightly sequenced stages. Starting from intermediate ground, it first sharpens core FP intuition in accessible languages, then ascends into type-driven and category-theoretic thinking with Haskell and Scala, and finally tackles advanced abstractions like monads, functors, and purely functional data structures that apply across all FP languages.
Core FP Intuition
IntermediateSolidify the foundational vocabulary of functional programming — pure functions, immutability, higher-order functions, and recursion — using approachable, multi-language examples before committing to a strongly-typed FP language.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (SICP: 5–6 weeks, ~30 pages/day; Clojure: 3–4 weeks, ~50 pages/day)
- Pure functions and referential transparency: functions that always return the same output for the same input with no side effects
- Immutability and persistent data structures: why immutable values prevent bugs and enable safe concurrent code
- Higher-order functions: functions that take or return other functions, enabling abstraction and composition
- Recursion and tail-call optimization: replacing loops with recursive thinking, and understanding TCO for efficiency
- First-class functions and lambda expressions: treating functions as values that can be passed, stored, and composed
- Function composition and partial application: building complex operations from simple, reusable pieces
- Lazy evaluation and sequences: deferring computation and working with infinite or large data structures efficiently
- Practical FP patterns in Clojure: map, filter, reduce, and how they embody functional thinking in real code
- What is a pure function, and why does referential transparency matter for reasoning about code?
- How do immutable data structures prevent bugs, and what trade-offs do they introduce compared to mutable state?
- What is a higher-order function, and how do map, filter, and reduce exemplify this concept?
- How does recursion replace iteration in functional programming, and when is tail-call optimization necessary?
- What is function composition, and how does it enable building complex programs from simple, reusable pieces?
- How do lazy sequences in Clojure allow you to work with infinite or very large data sets without loading everything into memory?
- SICP Chapter 1: Implement the square-root algorithm using Newton's method (Exercise 1.6–1.8) to practice pure functions and recursion without mutation
- SICP Chapter 2: Build a rational-number arithmetic system using data abstraction and higher-order functions to internalize immutable data representation
- Clojure: Rewrite a simple imperative algorithm (e.g., factorial, Fibonacci) using recursion and then optimize with tail-call recursion using recur
- Clojure: Use map, filter, and reduce on a real dataset (e.g., a list of maps representing people or transactions) to filter, transform, and aggregate data functionally
- Clojure: Write a function that returns a function (e.g., a multiplier factory or a validator builder) to practice higher-order functions and partial application
- Clojure: Create a lazy sequence using lazy-seq that generates an infinite series (e.g., Fibonacci, powers of 2) and consume only the first N elements
Next up: This stage equips you with the vocabulary and intuition to recognize functional patterns across languages; the next stage will deepen this by introducing a strongly-typed FP language where these concepts are enforced by the compiler, making the trade-offs and benefits concrete.
The canonical text for thinking computationally in a functional style. It builds deep intuition for recursion, higher-order functions, and abstraction that every later book in this path assumes.
Grounds FP concepts — immutability, lazy sequences, pure functions — in a modern Lisp running on the JVM, making the ideas concrete and immediately practical before moving to typed FP.
Typed Functional Programming
IntermediateUnderstand how a strong static type system amplifies FP design: algebraic data types, pattern matching, type classes, and the discipline of programming with types as specifications.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (alternating between books: 2–3 weeks on Hutton, then 2–3 weeks on Chiusano, with overlap for reinforcement)
- Algebraic Data Types (ADTs): sum types and product types as a foundation for modeling domain logic precisely
- Pattern matching: exhaustive matching and how the compiler enforces correctness through type-driven decomposition
- Type classes and ad-hoc polymorphism: designing abstractions (Eq, Ord, Functor, Monad) that work across multiple types
- The type system as a specification language: using types to encode invariants and constraints that prevent runtime errors
- Monads and do-notation: sequencing computations while maintaining type safety and purity
- Lazy evaluation in Haskell: how non-strict semantics interact with functional design and type safety
- Scala's hybrid approach: blending object-oriented and functional paradigms through type classes and implicit parameters
- Composing functions with types: function composition, higher-order functions, and type inference as design tools
- How do algebraic data types (sum and product types) allow you to encode domain constraints at compile time, and why is this safer than using primitive types?
- Explain pattern matching and why exhaustiveness checking by the compiler is a powerful guarantee in typed FP.
- What is a type class, and how does it enable ad-hoc polymorphism? Give examples from Haskell (Eq, Ord, Functor) and Scala.
- How do monads use the type system to enforce sequencing and composition of effectful computations while maintaining purity?
- Compare Haskell's lazy evaluation model with Scala's strict evaluation: how does each affect functional design and type safety?
- How can you use types as specifications to prevent invalid states in your program? Provide a concrete example with an ADT.
- Design and implement a domain model (e.g., a shopping cart, a game state, or a workflow) using ADTs in Haskell; ensure your types make invalid states unrepresentable.
- Write pattern-matching functions in Haskell that handle all cases of a multi-constructor ADT; deliberately omit a case and observe the compiler warning.
- Implement custom type class instances (Eq, Ord, Show) for your own ADTs in Haskell; then use these instances in higher-order functions.
- Refactor imperative-style code into monadic style using do-notation in Haskell (e.g., IO, Maybe, or a custom monad); observe how the type signature guides composition.
- Port a Haskell ADT-based solution to Scala using case classes and sealed traits; implement pattern matching and type classes (via implicit instances) to achieve similar safety.
- Write a small library or utility in Scala that uses implicit type classes (e.g., a custom Monoid or Serializer) and compose functions using them; compare with Haskell's explicit type class syntax.
Next up: This stage equips you with the discipline of designing systems where types encode correctness; the next stage will deepen this into advanced abstractions (functors, applicatives, monad transformers) and show how to scale typed FP to larger, real-world applications.
The clearest, most concise introduction to Haskell's type system and FP mechanics. Reading it first establishes the typed-FP vocabulary needed for every book that follows.
Teaches FP from first principles inside Scala, deriving abstractions like functors and monads by hand. Its exercise-driven approach turns type-class thinking from theory into muscle memory.
Advanced Abstractions & Category Theory
ExpertMaster the deep abstractions that unify FP across languages — monads, applicatives, functors, and foldable structures — and understand their mathematical foundations well enough to apply and invent them.
▸ Study plan for this stage
Pace: 12–16 weeks, ~40–50 pages/day with 2–3 days/week dedicated to exercises and implementation projects
- Functors, Applicatives, and Monads as abstractions for composing computations with context (Real World Haskell & Haskell Programming from First Principles)
- Monad laws and how they enable predictable, composable code; practical monads like Maybe, Either, IO, and State (Real World Haskell & Haskell Programming from First Principles)
- Category Theory foundations: objects, morphisms, functors, natural transformations, and adjunctions as the mathematical bedrock of FP abstractions (Category Theory for Programmers)
- Foldable and Traversable typeclasses for abstracting over recursive data structure traversal (Haskell Programming from First Principles)
- Purely functional data structures: persistent/immutable trees, queues, and sequences with O(1) or O(log n) operations (Purely Functional Data Structures)
- Amortized analysis and banker's method for reasoning about performance in functional settings (Purely Functional Data Structures)
- How category-theoretic concepts (limits, colimits, Yoneda lemma) unify disparate FP patterns and enable language-agnostic reasoning (Category Theory for Programmers)
- What are the three monad laws, and why does a type need to satisfy them to be a lawful monad? How do you verify them for a concrete monad like State or Reader?
- Explain the relationship between Functor, Applicative, and Monad. Why is Applicative strictly more powerful than Functor but strictly less powerful than Monad?
- What is a natural transformation in category theory, and how does it relate to polymorphic functions in Haskell?
- How do Foldable and Traversable abstractions generalize recursion? What is the difference between folding and traversing, and when would you use each?
- Describe the design and performance characteristics of a persistent data structure (e.g., a finger tree or banker's queue). Why can't you achieve the same performance with mutable data structures?
- What is an adjoint pair of functors, and how do you recognize one in practice? Give an example from Haskell or another FP language.
- How would you implement a lawful Monad instance for a custom type? Walk through the process and explain how you'd test it.
- Work through Real World Haskell chapters 10–14 (Monads, Functors, Applicatives): implement custom Monad instances for at least 3 types (e.g., a custom Either variant, a simple Parser monad, a Continuation monad) and verify they satisfy the monad laws.
- Complete all exercises in Haskell Programming from First Principles chapters 18–22 (Monad, Applicative, Functor, Foldable, Traversable). Implement Foldable and Traversable instances for a custom recursive data type (e.g., a binary tree or rose tree).
- Study Category Theory for Programmers Part 1 (chapters 1–7): work through the categorical definitions of Functor, Natural Transformation, and Adjunction. Sketch the categorical diagrams for at least 5 examples from Haskell (e.g., forall a. a → f a as a natural transformation).
- Implement 4–5 persistent data structures from Purely Functional Data Structures: a persistent list with O(1) cons, a banker's queue with amortized O(1) operations, a finger tree, and a persistent balanced tree. Benchmark them against mutable equivalents.
- Build a small domain-specific language (DSL) or parser combinator library using Applicative and Monad abstractions. Demonstrate how the laws enable equational reasoning about your code (e.g., show that two different implementations are equivalent).
- Write a detailed blog post or document explaining one advanced abstraction (e.g., Traversable, adjoint functors, or banker's method) in your own words, with concrete code examples. This forces you to internalize the concept deeply.
Next up: This stage equips you with the mathematical and practical foundations to recognize and design abstractions across any functional language, preparing you to tackle language-specific advanced topics (like type-level programming, effect systems, or dependent types) with a principled, category-theoretic mindset.
Bridges the gap between Haskell theory and production use, covering monads, monad transformers, and IO in depth — essential before tackling the mathematical treatment that follows.
The most thorough treatment of Haskell's abstraction hierarchy (Functor → Applicative → Monad) with exhaustive exercises; it consolidates and deepens everything learned so far.
Provides the mathematical backbone — categories, functors, natural transformations, monads — explained specifically for programmers, giving a unified language for all FP abstractions.
The definitive study of how to design efficient, immutable data structures — a capstone that applies everything learned about purity and types to real algorithmic problems.
Discussion
Keep reading
Paths that share books, cover the same subject, or open a related topic.
