Key Concepts Summary

This page provides a concise summary of the most important concepts in functional programming with Haskell, organized by topic. For a more detailed breakdown, see Functions and Equations, Algebraic Data Types, Monads Basics, Common Monads, Functors and Applicatives, Pattern Matching and Recursion, and Evaluation Strategies.

Functional Programming Fundamentals

Pure Functions

Definition: Functions that always return the same result for the same arguments and have no side effects (Functions and Equations)
Properties: Referential transparency, no state mutation, no side effects (Expressions and Reduction)
Benefits: Easier to reason about, test, and compose; facilitates parallelism

Immutability

Definition: Values cannot be changed after creation (Expressions and Reduction)
Implementation: New values are created instead of modifying existing ones
Example: x = x + 1 in Haskell defines recursion, not reassignment (Functions and Equations)

First-Class Functions

Definition: Functions can be passed as arguments, returned from other functions, and assigned to variables (Higher-Order Functions)
Example: map, filter, and fold take functions as arguments (Lists and List Comprehensions)

Expressions vs. Statements

In FP, everything is an expression that evaluates to a value (Expressions and Reduction)
No statements that merely produce side effects

Type System

Static Typing

All expressions have a type determined at compile time (Polymorphism)
Type errors are caught before runtime

Type Inference

The compiler can deduce types without explicit annotations (Polymorphism)
Type signatures enhance readability and serve as documentation

Polymorphism

Parametric: Functions work on any type (id :: a -> a) (Polymorphism)
Ad-hoc: Functions behave differently for different types (typeclasses; see Polymorphism)

Algebraic Data Types

Sum types (alternatives): data Bool = True | False (Algebraic Data Types)
Product types (combinations): data Point = Point Float Float (Algebraic Data Types)
Recursive types: data List a = Nil | Cons a (List a) (Algebraic Data Types)

Function Concepts

Currying

All functions take exactly one argument (Functions and Equations)
Multi-argument functions are actually a series of one-argument functions
Enables partial application

Higher-Order Functions

Functions that take other functions as arguments or return functions (Higher-Order Functions)
Examples: map, filter, fold, compose (Lists and List Comprehensions)

Function Composition

Combining functions: (f . g) x = f (g x) (Functions and Equations)
Enables point-free style

Recursion

The primary control structure in functional programming (Pattern Matching and Recursion)
Base case and recursive case
Tail recursion for efficiency (Evaluation Strategies)

Evaluation

Lazy Evaluation

Expressions are only evaluated when their values are needed (Evaluation Strategies)
Enables infinite data structures and separation of concerns (Lists and List Comprehensions)
Thunks: unevaluated expressions stored for later computation

Strictness

Forcing evaluation with bang patterns (!) (Evaluation Strategies)
seq function: evaluate first argument before returning second
Trade-offs between lazy and strict evaluation

Monadic Concepts

Functors

Types that can be mapped over (Functors and Applicatives)
Law: fmap id = id
Law: fmap (f . g) = fmap f . fmap g

Applicatives

Apply wrapped functions to wrapped values (Functors and Applicatives)
pure injects values into the applicative context
<*> applies functions in context to values in context

Monads

Sequencing computations that may have contexts or effects (Monads Basics)
return wraps values in a monadic context
>>= (bind) chains monadic operations
Three laws: left identity, right identity, associativity (Monad Laws)

Common Monads

Maybe: Computations that might fail (Common Monads, Error Handling)
Either: Computations that might fail with an error message (Common Monads, Error Handling)
List: Non-deterministic computations (Common Monads)
IO: Side-effecting computations (Introduction to IO)
State: Computations with mutable state (Common Monads)
Reader: Computations with read-only environment (Common Monads)
Writer: Computations that produce a log (Common Monads)

Monad Transformers

Combine the effects of multiple monads (Monad Transformers)
Stack monads to create more complex behavior
lift operations from inner monads

Patterns and Techniques

Pattern Matching

Destructure data based on its shape (Pattern Matching and Recursion)
Match on constructors, constants, variables, wildcards
Guards for additional conditions

List Comprehensions

Concise syntax for creating lists (Lists and List Comprehensions)
Similar to set-builder notation in mathematics
Generators, filters, and transformations

Do Notation

Syntactic sugar for monadic operations (Monads Basics)
Makes monadic code look more imperative
Desugars to applications of >>= and >> (Monad Laws)

Property-Based Testing

Define properties that code should satisfy (Property-Based Testing)
Test system generates random inputs
QuickCheck: verify properties hold for many cases

Advanced Concepts

Typeclasses

Define interfaces that types can implement (Polymorphism)
Enable ad-hoc polymorphism
Examples: Eq, Ord, Show, Functor, Monad

Parser Combinators

Build complex parsers by combining simpler ones (Parser Combinators)
Monadic interface for sequencing parsers
Libraries: Parsec, Megaparsec, Attoparsec

Equational Reasoning

Substituting equals for equals (Equational Reasoning)
Proving properties about code
Basis for program transformation and optimization

Lambda Calculus

Formal system underlying functional programming (Lambda Calculus)
Variables, abstractions (functions), and applications
Rewrite rules: alpha conversion, beta reduction, eta conversion

Key Functions to Remember

List Functions

map :: (a -> b) -> [a] -> [b] - Apply function to each element
filter :: (a -> Bool) -> [a] -> [a] - Keep elements satisfying predicate
foldr :: (a -> b -> b) -> b -> [a] -> b - Right-associative fold
foldl :: (b -> a -> b) -> b -> [a] -> b - Left-associative fold
zip :: [a] -> [b] -> [(a, b)] - Combine corresponding elements
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] - Combine with function

Function Combinators

(.) :: (b -> c) -> (a -> b) -> a -> c - Function composition
($) :: (a -> b) -> a -> b - Function application
flip :: (a -> b -> c) -> b -> a -> c - Flip function arguments
const :: a -> b -> a - Constant function

Monad Operations

return :: a -> m a - Wrap value in monad
(>>=) :: m a -> (a -> m b) -> m b - Bind/sequence
(>>) :: m a -> m b -> m b - Sequence, discard first result
liftM :: Monad m => (a -> b) -> m a -> m b - Map function over monad

IO Functions

getLine :: IO String - Read line from stdin
putStrLn :: String -> IO () - Write line to stdout
readFile :: FilePath -> IO String - Read file contents
writeFile :: FilePath -> String -> IO () - Write string to file

Key Tips for Exams

Focus on types: Understanding the types often reveals the function’s purpose
Practice pattern matching: Many problems are solved with clever pattern matching
Learn the common higher-order functions: They form building blocks for many solutions
Understand monads conceptually: Know how they sequence operations with contexts
Master recursion: It’s the primary control structure in functional programming
Remember typeclass laws: They constrain behavior and ensure consistency
Apply equational reasoning: Step-by-step transformation helps solve complex problems

Quartz 4

Explorer