Lecture Notes

Functional Programming Abstractions

These notes form an introductory course on functional programming using the Haskell programming language, based on Stanford’s CS43. They are intended to briefly present the necessary syntax and basic concepts (which are covered elsewhere in much greater depth) and focus on further theoretical exposition and examples. They are written by Adithya Ganesh and Isaac Scheinfeld, under the advising of Jerry Cain. Special thanks to Allan Jiang, co-creator of CS43.

Note that since this is the first year this material is being taught in CS43, this page will be updated throughout the course with new material.

Background and Basics

  1. Why Haskell?: An overview of Haskell’s defining features, with brief examples.

  2. Getting Set Up: One way to set up a Haskell environment with stack, as well as some options for minimal tooling.

  3. Introduction to Haskell: Expressions, values, and types.

  4. Algebraic Datatypes: Defining and using types in Haskell, and the basics of type algebra.

Functional Abstractions

  1. Higher Order Functions: Functions that operate on other functions, generalizing basic functions, and defining map.

  2. Folds, Scans, and Laziness: Examining the many ways to process lists.

Type Design Patterns

  1. Typeclasses: Introducing typeclasses and polymorphism.

  2. Typeclasses II, Batteries Included: More on the built-in typeclasses in Haskell.

Algebraic Abstractions

  1. Semigroup and Monoid: Abstracting compositionalstructures.

  2. Functor: Lifting function application to a new level.

  3. Monad: It isn’t that complicated.

Beyond Haskell

  1. Idris and Dependent Types