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.

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. Algebraic Datatypes: Defining and using types in Haskell, and the basics of type algebra.

  2. Typeclasses: Using, writing, and deriving typeclasses, and the power of polymorphism.

Algebraic Abstractions

  1. Semigroup and Monoid: Abstracting compositional structures.

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

  3. Monad: It isn’t that complicated.

Beyond Haskell

  1. Idris and Dependent Types