These mathematical guarantees make reasoning about comparisons reliable.
TheOrdTypeclass: Ordering
Ord defines ordering functions. A type must be Eq before it can be Ord.
Important operations:
(<) :: Ord a => a -> a -> Bool
(>) :: Ord a => a -> a -> Bool
(<=) :: Ord a => a -> a -> Bool
(>=) :: Ord a => a -> a -> Bool
compare :: Ord a => a -> a -> Ordering
You can automatically derive comparison operations for your own data types:
data Color = Red | Green | Blue
deriving (Eq, Ord, Show)
Red < Blue -- True (ordering = definition order)
For more complex types:
data Point = Point Int Int
deriving (Eq, Ord, Show)
Point 1 3 < Point 1 4 -- True (lexicographic)
Custom Comparison Logic
You can manually implement Eq or Ord to override behavior:
data Person = Person { name :: String, age :: Int }
instance Eq Person where
p1 == p2 = age p1 == age p2
instance Ord Person where
compare p1 p2 = compare (age p1) (age p2)
Now persons compare by age only, ignoring the name.
Chaining Comparisons UsingOrdering
Sometimes you want to compare multiple fields manually:
But tupled arguments group multiple parameters into one:
addT :: (Int, Int) -> Int
addT (x, y) = x + y
Use curried forms when possible; tupled forms when logically grouping values.
Types and Typeclasses in Haskell
Why Types Matter in Haskell
Haskell is a statically typed language:
Every expression has a type, known at compile time.
The compiler checks type correctness before running your program.
Haskell also has type inference:
you usually do not need to write types explicitly,
the compiler can infer them from the code.
Typeclasses add another layer: they describe behavior that types can implement.
Basic Built-in Types
Some common primitive types:
42 :: Int -- fixed-size integer
3.14 :: Double -- double-precision floating point
True :: Bool -- boolean
'a' :: Char -- character
"hello" :: String -- String = [Char]
You can always ask GHCi for the type of an expression using :t:
Prelude> :t 42
42 :: Num a => a
Note: The compiler often shows polymorphic types (like Num a => a) instead of a concrete Int.
Type Signatures for Functions
Type signatures document what a function takes and returns.
General form:
name :: TypeOfArg1 -> TypeOfArg2 -> ... -> ResultType
Example:
add :: Int -> Int -> Int
add x y = x + y
Read as: add is a function that takes an Int, then another Int, and returns an Int.
Because functions are curried, Int -> Int -> Int is really Int -> (Int -> Int).
Type Variables and Polymorphism
Haskell supports parametric polymorphism via type variables.
A type variable is a lowercase letter like a, b, t:
identity :: a -> a
identity x = x
identity works for any type a:
identity 3 -> 3
identity "hi" -> "hi"
identity True -> True
This is true parametric polymorphism: behavior does not depend on the specific type.
Type Constructors and Parameterized Types
Types can be parameterized by other types, just like generic types in other languages.
Example: Maybe a, [a], Either e a.
Just 5 :: Maybe Int
Nothing :: Maybe a
[1,2,3] :: [Int]
Right "ok" :: Either e String
Left "err" :: Either String a
Here, Maybe, [] (list), and Either are type constructors:
They are not full types until you give them a parameter.
E.g. Maybe alone is like a function at the type level: it maps a to Maybe a.
Type Synonyms (Type Aliases)
You can give a new name to an existing type using type:
type UserName = String
type Age = Int
greet :: UserName -> String
greet name = "Hello, " ++ name
This does not create a new type, just a nickname for an existing one.
The compiler treats UserName as String.
Algebraic Data Types (ADTs)
Haskell allows you to define your own types using data.
General forms:
Sum types (one of several constructors),
Product types (constructors with multiple fields).
-- Sum type: a value is either a Circle or a Rectangle
data Shape
= Circle Double -- radius
| Rectangle Double Double -- width height
-- Product type with a single constructor and multiple fields
data Person = Person
{ name :: String
, age :: Int
}
ADTs combine:
Choice (which constructor?)
Structure (what fields in each constructor?)
You use pattern matching to work with custom types.
What Is a Typeclass?
A typeclass is a way to define a set of operations (methods) that a type can implement.
Think of it as an interface of behavior, but:
It works at the type level,
It supports ad-hoc polymorphism (overloading by type).
Example: the Eq typeclass defines equality operations:
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
Any type a that provides definitions for (==) and (/=) can be an instance of Eq.
Typeclass Constraints
A function can require that its type parameters belong to certain typeclasses.
General form:
function :: (Constraint1 a, Constraint2 a, Constraint3 b) => a -> b -> ...
Example: a function that compares and prints something:
showIfEqual :: (Eq a, Show a) => a -> a -> String
showIfEqual x y =
if x == y
then "Equal: " ++ show x
else "Not equal"
For any type a that implements Eq and Show,
showIfEqual takes two as and returns a String.
Common Standard Typeclasses
Eq — equality and inequality: (==), (/=)
Ord — ordering: (<), (>), (<=), (>=), compare
Show — convert to human-readable String: show :: Show a => a -> String
Read — parse from String:
Num — numeric types (supports + - * fromInteger):
Integral — integer types (Int, Integer):
Fractional — fractional types (Float, Double):
Functor — types you can map over: fmap :: Functor f => (a -> code) -> f a -> f code
Applicative, Monad — types supporting sequencing and effects.
Defining Instances: Making a Type Implement a Typeclass
To make a type implement a typeclass, you write an instance declaration.
Example: implement Eq and Show for a custom type.
data Color = Red | Green | Blue
instance Eq Color where
Red == Red = True
Green == Green = True
Blue == Blue = True
_ == _ = False
instance Show Color where
show Red = "Red"
show Green = "Green"
show Blue = "Blue"
Now you can write:
Red == Green -- False
show Blue -- "Blue"
Deriving Typeclass Instances Automatically
Writing instances by hand can be repetitive, so Haskell supports deriving.
Example:
data Color = Red | Green | Blue
deriving (Eq, Show, Ord)
The compiler automatically creates reasonable implementations of these typeclasses.
Now you get:
Red == Red works,
show Green yields "Green",
Red < Green based on constructor order.
Many standard typeclasses can be derived: Eq, Ord, Show, Read, Enum, Bounded, etc.
Parametric vs Ad-hoc Polymorphism
Parametric polymorphism (via type variables):
Same implementation for all types.
Example: identity :: a -> a.
Ad-hoc polymorphism (via typeclasses):
Different implementation depending on the type.
Example: show :: Show a => a -> String behaves differently for Int vs Bool.
Haskell lets you mix both:
type variables for generality,
typeclass constraints for required capabilities.
Putting It Together: A Small Example
Define a custom type, derive some typeclasses, and write a polymorphic function:
data Point a = Point a a
deriving (Eq, Show)
-- Distance squared between two points (works for any Num type)
distSquared :: Num a => Point a -> Point a -> a
distSquared (Point x1 y1) (Point x2 y2) =
(x2 - x1) ^ 2 + (y2 - y1) ^ 2
-- Check if two points are the same and show a message
describePoints :: (Eq a, Show a, Num a) => Point a -> Point a -> String
describePoints p1 p2 =
if p1 == p2
then "Same point: " ++ show p1
else "Different points: " ++ show p1 ++ " and " ++ show p2
Key ideas:
Point a is a parameterized type.
We derive Eq and Show automatically.
distSquared uses Num a because it needs (-) and (^).
describePoints uses both Eq and Show for comparison and printing.
Algebraic Data Types (ADTs) in Haskell
What Are ADTs?
An Algebraic Data Type (ADT) is a user-defined type created by combining other types using either Sum types (choices) or Product types (combinations)
They are called “algebraic” because they combine types using algebra-like operations:
+ = either/or (sum types)
× = “and” (product types)
Sum Types: Representing Alternatives
A sum type describes a value that may be one of several variants.
Each variant is called a constructor.
data Shape
= Circle Double -- radius
| Rectangle Double Double -- width height
A Shape value is either a Circle with a radius, or a Rectangle with width and height.
Pattern matching is used to work with sum types:
area :: Shape -> Double
area (Circle r) = pi * r^2
area (Rectangle w h) = w * h
Product Types: Grouping Multiple Values Together
A product type contains multiple fields at once.
data Person = Person String Int
-- name age
Meaning: a Person is constructed with a String and an Int.
greet :: Person -> String
greet (Person name age) =
"Hello, " ++ name ++ ", age " ++ show age
Record Syntax for Product Types
Record syntax provides named fields:
data User = User
{ username :: String
, password :: String
, userAge :: Int
}
Automatic getters are created:
username (User "a" "b" 21) -- "a"
userAge (User "a" "b" 21) -- 21
Record updates create modified copies:
let u = User "bob" "pass" 30
u { userAge = 31 }
Combining Sum + Product: The Real Power of ADTs
Real-world ADTs often combine both approaches:
data Expr
= Lit Int -- product type (literal)
| Add Expr Expr -- product type
| Mul Expr Expr
Pattern matching lets us write logic elegantly:
eval :: Expr -> Int
eval (Lit n) = n
eval (Add a b) = eval a + eval b
eval (Mul a b) = eval a * eval b
ADTs can model algebraic expressions, ASTs, API responses, states, and more.
Recursive ADTs
Constructors can refer to the type being defined.
data List a
= Empty
| Cons a (List a)
This is essentially how Haskell’s built-in list [a] works!
Recursive types allow:
trees
graphs
linked structures
ASTs (Abstract Syntax Trees)
data Tree a
= Leaf a
| Node (Tree a) (Tree a)
Parameterized ADTs (Generics)
ADTs often take type parameters:
data Maybe a
= Nothing
| Just a
This is a generic container type:
Maybe Int
Maybe String
Maybe (Int, Bool)
Just 5 :: Maybe Int
Nothing :: Maybe a
Derived Instances for ADTs
Most ADTs can automatically derive useful typeclass instances:
data Color
= Red | Green | Blue
deriving (Eq, Show, Ord)
Automatic benefits:
Red == Blue -- False
show Green -- "Green"
Red < Blue -- True (constructor order)
Pattern Matching with ADTs
Pattern matching is the primary way to consume ADTs.
describeColor :: Color -> String
describeColor Red = "Warm color"
describeColor Green = "Natural color"
describeColor Blue = "Cool color"
Pattern matching ensures:
exhaustiveness checking,
safe decomposition of product types,
errors caught at compile time.
Real-World Example: Handling API Results
ADTs allow representing cases cleanly:
data Result a
= Success a
| Error String
Usage:
handle :: Result Int -> String
handle (Success n) = "Value: " ++ show n
handle (Error msg) = "Error: " ++ msg
Typeclasses in Haskell
What Are Typeclasses?
A typeclass in Haskell defines a set of behaviors (operations) that a type can implement.
A typeclass does not define data, it defines functions that types must provide.
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
This means: any type a that implements Eq must define (==) and (/=).
The Role of Typeclass Constraints
Functions often restrict type variables to only those types that implement a required typeclass.
equalMessage :: Eq a => a -> a -> String
equalMessage x y =
if x == y then "Equal" else "Not equal"
Eq a => is a constraint meaning: "this function only works for types that implement Eq."
You can have multiple constraints:
describe :: (Eq a, Show a) => a -> a -> String
Defining a Typeclass
You define a typeclass using the class keyword.
Example of a custom typeclass:
class Printable a where
toText :: a -> String
Any type that implements Printable must define toText.
Creating a Typeclass Instance
To make a type implement a typeclass, write an instance.
data Color = Red | Green | Blue
instance Printable Color where
toText Red = "Red"
toText Green = "Green"
toText Blue = "Blue"
Now you can call:
toText Red -- "Red"
toText Blue -- "Blue"
Automatic Instance Derivation
Haskell can auto-generate implementations for many standard typeclasses:
data Point = Point Int Int
deriving (Eq, Show)
Eq: now (==) compares coordinates
Show: allows show (Point 1 2) => "Point 1 2"
Typeclasses as Constraints on Polymorphic Functions
Typeclasses let you write functions that work for many types, but only those that implement required behaviors.
max3 :: Ord a => a -> a -> a -> a
max3 a b c = max a (max b c)
Because max needs ordering, the function requires Ord a.
Multiple Typeclass Constraints
You can require several typeclasses at once:
format :: (Show a, Ord a) => a -> a -> String
format x y =
if x < y
then "Ascending: " ++ show x ++ ", " ++ show y
else "Descending: " ++ show y ++ ", " ++ show x
Typeclasses for Parameterized Types
Typeclasses can reference types of the form f a (e.g., Maybe a, [a]).
This allows modeling behaviors of containers.
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)
Any type constructor f of kind * -> * can implement Functor.
Subclassing in Typeclasses
Typeclasses can depend on other typeclasses.
Example: Ord requires Eq.
class Eq a => Ord a where
(<) :: a -> a -> Bool
(>) :: a -> a -> Bool
compare :: a -> a -> Ordering
Meaning: "Any Ord instance must also implement Eq."
Advanced Feature: Default Method Implementations
Typeclasses can provide default method bodies, which instances may override or keep.
If an instance does not define the method, the default version is used automatically.
class Size a where
size :: a -> Int
size _ = 1 -- default implementation
Here, any type that derives Size without defining size will return 1.
data Point = Point Int Int
-- Using the default implementation
instance Size Point
main = print (size (Point 3 4)) -- prints 1
You can also override the default:
data Pair a = Pair a a
instance Size (Pair a) where
size (Pair _ _) = 2 -- custom implementation
Some typeclasses work on type constructors (not simple types).
Examples:
Functor: fmap
Applicative: pure, (<*>)
Monad: (>>=)
Real-World Example: Defining Equality and Display
Create a custom type and implement two typeclasses:
data Pair a = Pair a a
instance Eq a => Eq (Pair a) where
Pair x1 y1 == Pair x2 y2 = x1 == x2 && y1 == y2
instance Show a => Show (Pair a) where
show (Pair x y) = "Pair(" ++ show x ++ ", " ++ show y ++ ")"
Pattern Matching in Haskell
What Is Pattern Matching?
It allows you to “deconstruct” values by matching them against patterns, and automatically bind variables.
Patterns may describe:
literal values,
data constructors,
tuples, lists, records,
wildcards _,
nested structures,
guards combined with patterns.
Pattern matching is everywhere: in function definitions, case expressions, let bindings, and list comprehensions.
Pattern Matching in Function Definitions
Functions can define multiple equations using different patterns.
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs
Pattern Matching with Data Constructors (ADTs)
When working with algebraic data types, pattern matching is essential.
data Shape
= Circle Double
| Rectangle Double Double
area :: Shape -> Double
area (Circle r) = pi * r^2
area (Rectangle w h) = w * h
You extract fields naturally as part of the pattern.
Pattern Matching with Records
Record fields can be extracted by naming them in patterns:
data User = User
{ name :: String
, age :: Int
}
describeUser :: User -> String
describeUser User { name = n, age = a } =
n ++ " is " ++ show a ++ " years old"
You may also mix record syntax with positional patterns.
As-patterns
An as-pattern lets you refer to the entire matched value and its components.
describeList :: [a] -> String
describeList xs@(x:_) = "first element: " ++ show x ++ ", full list: " ++ show xs
describeList [] = "empty list"
xs@(x:_) means:
x:_ matches first element + rest
xs is bound to the whole list
Pattern Matching in case Expressions
Useful when you want pattern matching inside an expression instead of top-level definitions.
describeBool :: Bool -> String
describeBool b =
case b of
True -> "yes"
False -> "no"
case expressions follow the same matching rules as functions.
Guards Together with Pattern Matching
When matching is not enough, guards add conditional logic.
classify :: Int -> String
classify n
| n < 0 = "negative"
| n == 0 = "zero"
| otherwise = "positive"
Patterns match structure, guards match conditions.
Matching Failure: Why Order Matters
Patterns are checked top to bottom.
If a pattern fails, Haskell tries the next one.
This can affect correctness:
bad :: [a] -> String
bad (x:xs) = "nonempty"
bad [] = "empty"
-- The order here is fine.
Multiple comma-separated conditions act as multiple guard checks.
UsingotherwiseSafely
otherwise is simply:
otherwise = True
It must appear at the last. If placed earlier, all following guards become unreachable.
A correct example:
describe n
| n > 10 = "big"
| otherwise = "small or equal to 10"
Guards vs If/Else
Guards:
cleaner syntax for many branches,
work well with pattern matching,
read top–down like logic rules,
avoid nesting.
If/else:
better for small, inline conditions,
less readable for multi-branch logic.
Guards with Multiple Arguments
Patterns can match arguments, and guards refine conditions:
max3 :: Ord a => a -> a -> a -> a
max3 x y z
| x >= y && x >= z = x
| y >= x && y >= z = y
| otherwise = z
Guards with Pattern Guards (Advanced)
Pattern guards allow matching and binding inside a guard expression.
Syntax:
f x
| Just y <- lookup x table = "found " ++ show y
| otherwise = "not found"
Pattern guards:
first try the pattern,
bind its contents,
continue if match succeeds.
Example: Combining Everything
A function that classifies triangles:
triangleType :: (Eq a, Ord a, Num a) => a -> a -> a -> String
triangleType a b c
| a + b <= c || b + c <= a || a + c <= b = "not a triangle"
| a == b && b == c = "equilateral"
| a == b || b == c || a == c = "isosceles"
| otherwise = "scalene"
Built-in Types in Haskell
Big Picture
Many types you use come from:
The Prelude (imported automatically),
The base library (standard library),
Other common libraries (containers, text, bytestring, scientific, etc.).
This chapter focuses on:
Primitive & core types: Bool, Char, numeric types
Composite types: lists, tuples
Algebraic types: Maybe, Either, Ordering
Special types: (), IO a, function types a -> b
Type constructors & kinds, and typeclass relationships
Some widely used numeric & scientific types (Rational, Complex, Natural, Scientific-like)
String is easy to reason about but inefficient for large text (linked list of Char).
For serious text processing, libraries use:
Data.Text.Text (Unicode, packed array),
Data.ByteString.ByteString (binary data, bytes).
Numeric Tower Overview
Haskell uses typeclasses to organize numeric types:
class Num a where ...
class Real a where ...
class Integral a where ...
class Fractional a where ...
class Floating a where ...
class RealFrac a where ...
class RealFloat a where ...
Rough hierarchy (simplified):
Integral ⊆ Real ⊆ Num
Fractional ⊆ Num
Floating ⊆ Fractional
RealFrac ⊆ Real & Fractional
RealFloat ⊆ RealFrac & Floating
Numeric literals are polymorphic:
5 :: Num a => a -- can be Int, Integer, Double, ...
3.5 :: Fractional a => a -- can be Float or Double
Integral Types
Int:
Fixed-size, machine integer (usually 64-bit).
Fast, but can overflow on very large values.
42 :: Int
(-10) :: Int
Integer:
Arbitrary-precision integer (no overflow, limited only by memory).
Great for exact math or big integers, slower than Int.
123456789012345678901234567890 :: Integer
Fixed-width integer types (from Data.Int):
import Data.Int
Int8, Int16, Int32, Int64 -- signed fixed-width
This brings all exported names from the module into scope (unqualified, unless you add qualified).
Haskell modules form a hierarchy that mirrors directories:
Data.List usually comes from Data/List.hs
MyApp.Utils.Strings from MyApp/Utils/Strings.hs
Importing Specific Names
You can restrict imports to a selected list of names using an import list in parentheses:
import Data.List (sort, nub)
This imports only sort and nub from Data.List.
You can also import type constructors and their constructors:
import Data.Maybe (Maybe(..))
-- imports the type Maybe and its constructors: Just, Nothing
import Data.Either (Either(Left, Right))
Type(..) means “import the type and all of its constructors”.
You may also list constructors explicitly instead of (..).
Hiding Names withhiding
You can import everything except some names using hiding:
import Data.List hiding (sort)
This imports all exported names from Data.List except sort.
You can hide multiple names:
import Prelude hiding (head, tail)
Useful when:
you want to define your own version of a common function (e.g. a safer head), or
you want to avoid name clashes with another module.
Qualified Imports
A qualified import requires you to prefix names with the module name when using them:
import qualified Data.Map
example :: Data.Map.Map String Int
example = Data.Map.fromList [("a", 1), ("b", 2)]
Advantages:
avoids name clashes (e.g. Data.Map.lookup vs Data.List.lookup),
makes code more explicit about where functions come from.
Disadvantage:
can be verbose, especially with long module names.
Qualified Imports withas (Aliases)
You can combine qualified with an alias using as to shorten names:
import qualified Data.Map as M
example :: M.Map String Int
example = M.fromList [("a", 1), ("b", 2)]
This is a very common style:
Data.Map as M
Data.Set as S
Data.Text as T or Text
You must always use the alias to refer to imported names.
Combining Qualified, Explicit, and Hiding
You can combine many import options:
-- 1. Qualified with explicit import list
import qualified Data.Map as M (Map, fromList, lookup)
-- 2. Unqualified with explicit list
import Data.List (sort, nub)
-- 3. Qualified hiding some names (less common)
import qualified Data.List as L hiding (nub)
Most typical patterns in real projects:
Unqualified + explicit list for small utility modules.
Qualified + alias for large libraries (Maps, Sets, Text, Conduit, etc.).
hiding to avoid conflicts with Prelude or to override a function.
Dealing with Name Clashes
Sometimes two modules export functions with the same name (e.g. Data.List.map and Prelude.map).
Strategies to handle clashes:
-- Strategy 1: qualified import
import qualified Data.Map as M
-- Strategy 2: hide conflicting names
import Prelude hiding (lookup)
import qualified Data.Map as M
Example: using both lookup from Data.Map and Data.List:
import qualified Data.Map as M
import qualified Data.List as L
foo :: Maybe Int
foo =
let m = M.fromList [("a", 1)]
in M.lookup "a" m -- clearly from Data.Map
bar :: Maybe Int
bar =
L.lookup "a" [("a", 1)] -- from Data.List
The Prelude and Turning It Off
Prelude is the default module imported into every Haskell module:
-- Implicitly:
import Prelude
It provides:
basic types (Int, Bool, Maybe, [], Either...)
basic functions (map, foldr, length, etc.)
You can disable the implicit Prelude import with a language pragma:
{-# LANGUAGE NoImplicitPrelude #-}
module Main where
import MyCustomPrelude
This is used in some projects to define their own “prelude” or to have stricter control over imports.
Importing Your Own Modules
Project modules are just modules you define yourself.
Directory structure mirrors module hierarchy:
-- File: src/MyApp/Utils/Math.hs
module MyApp.Utils.Math where
square :: Int -> Int
square x = x * x
From another module:
-- File: src/MyApp/Main.hs
module MyApp.Main where
import MyApp.Utils.Math (square)
foo :: Int
foo = square 10
Your build tool (Cabal, Stack, etc.) must be configured so that src is on the module search path.
importin GHCi
In GHCi (the interactive REPL), you can also use import statements, or the :m command:
($) is a function that simply applies another function:
($) :: (a -> b) -> a -> b
f $ x = f x
It is useful to reduce parentheses:
sum (map abs [1,-2,3])
sum $ map abs [1,-2,3]
Common in pipelines.
Partial Application
Because functions in Haskell are curried, you can call a function with fewer arguments than it expects.
This creates a new function (higher-order behavior).
add :: Int -> Int -> Int
add x y = x + y
addFive = add 5 -- addFive :: Int -> Int
addFive 10 -- 15
This technique is used constantly in functional programming.
Sections: Turning Operators into Functions
Operators can be partially applied using parentheses:
(+) 3 -- \x -> 3 + x
(3 +) -- same as above
(+ 3) -- \x -> x + 3
(*2) -- \x -> x * 2
These are higher-order functions created automatically by partial application.
Zip Functions
zipWith is a classic higher-order function:
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (+) [1,2,3] [4,5,6] -- [5,7,9]
zipWith max [1,5,2] [3,2,8] -- [3,5,8]
It applies a function elementwise to two lists.
Higher-Order Patterns in Real Projects
Real Haskell code frequently uses higher-order functions for:
callbacks,
data transformation pipelines,
domain-specific languages,
parsers (Parsec/Megaparsec use HOFs everywhere),
IO actions chaining,
validation pipelines,
business logic combinators.
Example: Using HOFs to build reusable validation logic:
validate :: (a -> Bool) -> String -> a -> Either String a
validate p msg x =
if p x then Right x else Left msg
isPositive = validate (> 0) "not positive"
isEven = validate even "not even"
isEven 4 -- Right 4
isPositive (-1) -- Left "not positive"
Using HOFs to Create Pipelines
Chaining functions is a core functional technique:
processNumbers =
map (*2)
. filter odd
. map (+1)
Now processNumbers is itself a function:
processNumbers [1,2,3,4] -- [4,8]
Lambda Expressions (Anonymous Functions) in Haskell
What Are Lambda Expressions?
A lambda expression (also called an anonymous function) is a function defined without a name.
In Haskell, lambdas use a special syntax based on mathematical lambda calculus:
\x -> expression
The backslash \ represents λ (lambda).
Lambdas are used when:
you need a function only once,
you want to pass inline behavior into another function,
you want to avoid naming trivial helper functions.
Basic Syntax
The simplest lambda:
\x -> x + 1
Equivalent named version:
addOne x = x + 1
A lambda is just another ordinary function.
(\x -> x + 1) 5 -- 6
Multiple Arguments
Lambdas can have multiple parameters:
\x y -> x + y
Equivalent to:
add x y = x + y
And because Haskell is curried:
(\x -> \y -> x + y)
Lambdas Inside Higher-Order Functions
Lambdas shine when passed to higher-order functions:
map (\x -> x * 2) [1,2,3]
-- [2,4,6]
filter (\x -> x > 5) [3,4,5,6,7]
-- [6,7]
Using a lambda avoids having to name trivial helpers:
map (\c -> toUpper c) "lambda"
-- "LAMBDA"
Lambdas with Pattern Matching
You can pattern match directly in a lambda:
\ (x, y) -> x + y
Example with tuple destructuring:
map (\(x,y) -> x * y) [(2,3), (4,5)]
-- [6,20]
Or matching list patterns:
\ (x:_) -> x
Pattern failures inside lambdas cause runtime errors, so they should be used carefully.
Lambdas in Let and Where Bindings
Lambdas can appear in let or where:
let f = \x -> x * 2
in f 10
Equivalent to:
let f x = x * 2 in f 10
Lambda Case (\case)
Using the LambdaCase extension, you can write pattern-matching lambdas without naming the argument.
Enable the extension:
{-# LANGUAGE LambdaCase #-}
Then write:
\case
Just x -> x * 2
Nothing -> 0
Equivalent to:
\m -> case m of
Just x -> x * 2
Nothing -> 0
Lambda Patterns with \\ Syntax (Multi-Clause Lambdas)
With the LambdaCase or MultiWayIf extension, lambdas can have multiple pattern branches.
Using \\ (double-backslash):
\case
(x,y) -> x
_ -> 0
This is cleaner than wrapping everything in case ... of.
Common Lambda Shorthands
Lambdas can be simplified using operators or partial application:
\x -> x + 1 == (+1)
\x -> 1 + x == (1+)
\x -> x * y == (*y)
\x -> f (g x) == (f . g)
Many lambdas can be rewritten more concisely using sectioning or composition.
Examples of Real-World Lambda Usage
Sorting with custom comparators:
import Data.List (sortBy)
sortBy (\a b -> compare (length a) (length b)) ["hi", "hello", "a"]
-- ["a","hi","hello"]
Parsing transforms:
map (\x -> read x :: Int) ["1","2","3"]
-- [1,2,3]
Functional pipelines:
let pipeline = filter (\x -> x > 3) . map (\x -> x * 2)
pipeline [1,2,3,4]
-- [8]
Do Lambdas Have Types?
Yes — every lambda has a type just like any function.
:t \x -> x + 1
-- :: Num a => a -> a
Types can also be added explicitly:
(\x -> x + 1) :: Int -> Int
Modules in Haskell
What Are Modules in Haskell?
A module is Haskell’s fundamental unit of code organization.
Every Haskell file defines exactly one module.
Modules:
group related functions, types, and typeclasses,
control what is visible to other modules,
enable namespace management,
improve maintainability and structure.
Modules correspond to files, and hierarchical module names correspond to folder structure.
Basic Module Declaration
Each file begins with a module declaration:
module MyModule where
x = 42
If no module is declared, the file is assumed to be Main.
File name must match the module name and folder hierarchy:
MyModule.hs defines module MyModule
Data/ListUtils.hs defines module Data.ListUtils
Export Lists
A module can selectively expose names using an export list:
module Math.Utils (square, cube) where
square x = x * x
cube x = x * x * x
secret = 123 -- not exported
Anything not listed in the export list is private.
To export everything, omit the export list.
module Math.Utils where
Exporting Types and Constructors
You may export:
just the type name,
the type with all constructors,
or specific constructors.
module Shapes
( Shape(Circle, Rectangle)
, area
) where
data Shape = Circle Double | Rectangle Double Double
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
Exporting all constructors:
module Shapes (Shape(..)) where
Importing Modules (Short Summary)
Imported using import Module.Name:
import Data.List (sort, nub)
import qualified Data.Map as M
For full rules of importing, see your previous “Haskell import” chapter.
Hierarchical Modules
Modules support hierarchical naming using dots.
For example:
module MyApp.Utils.Math where
File structure must mirror the hierarchy:
MyApp/
└─ Utils/
└─ Math.hs
This improves organization in large codebases.
The Prelude Module
Prelude is automatically imported into every module:
import Prelude
It provides:
basic types (Int, Bool, Maybe, [], Either, ...),
basic functions (map, foldr, not, (++)).
You can disable it:
{-# LANGUAGE NoImplicitPrelude #-}
module Main where
Useful for custom preludes (e.g. CodeWorld, Yesod, commercial codebases).
module Main where
import Utils.StringTools
main = putStrLn (capitalize "hello world")
Deriving Instances in Haskell
What Does "Deriving" Mean in Haskell?
In Haskell, many behaviors are expressed via typeclasses (e.g. Eq, Show, Ord).
An instance tells the compiler how a specific type supports a given typeclass.
Deriving allows the compiler to automatically generate standard instance implementations for many common typeclasses.
Instead of writing:
data Color = Red | Green | Blue
instance Eq Color where
Red == Red = True
Green == Green = True
Blue == Blue = True
_ == _ = False
instance Show Color where
show Red = "Red"
show Green = "Green"
show Blue = "Blue"
you can simply write:
data Color = Red | Green | Blue
deriving (Eq, Show)
The compiler generates the "obvious" instances for you, based on the data declaration.
Basic Deriving Syntax
The simplest form is attached directly to a data or newtype definition:
data Point = Point Int Int
deriving (Eq, Show)
This creates:
Eq Point instance: two Points are equal if both coordinates are equal.
Show Point instance: show (Point 1 2) produces something like "Point 1 2".
You can derive multiple classes at once by listing them in parentheses separated by commas.
Example: Deriving Eq and Show for an ADT
Consider an expression tree:
data Expr
= Lit Int
| Add Expr Expr
| Mul Expr Expr
deriving (Eq, Show)
For simple enumerations, deriving Enum and Bounded is very convenient:
data Color = Red | Green | Blue
deriving (Eq, Ord, Show, Enum, Bounded)
allColors :: [Color]
allColors = [minBound .. maxBound]
-- [Red,Green,Blue]
succ Red -- Green
pred Blue -- Green
fromEnum Red -- 0
fromEnum Blue -- 2
The order is the declaration order: Red < Green < Blue.
Deriving for Parameterized Types
You can derive instances for types with type parameters too:
data Pair a = Pair a a
deriving (Eq, Ord, Show, Functor)
Some classes (like Functor) require GHC extensions (DeriveFunctor):
{-# LANGUAGE DeriveFunctor #-}
data Tree a
= Leaf a
| Node (Tree a) (Tree a)
deriving (Eq, Show, Functor)
Now you can fmap over trees:
fmap (+1) (Leaf 3) -- Leaf 4
Deriving for Newtypes
newtype defines a type with exactly one constructor and one field, with no runtime overhead.
You can often derive instances for a newtype based on the underlying type.
newtype UserId = UserId Int
deriving (Eq, Ord, Show)
This works because UserId has the same runtime representation as Int.
You can also use more advanced newtype-deriving via extensions (see below).
Standalone Deriving
With the StandaloneDeriving extension, you can write deriving declarations separate from the type definition.
Enable the extension:
{-# LANGUAGE StandaloneDeriving #-}
Then:
data Foo a = Foo a
-- later in the file, or even another module (with some restrictions):
deriving instance Eq a => Eq (Foo a)
deriving instance Show a => Show (Foo a)
Useful when:
you cannot or do not want to modify the original type definition,
you want instances in a different module,
you have conditional instances depending on constraints.
Deriving Strategies: stock, newtype, anyclass, via
This uses newtype deriving to reuse Double's instances.
Deriving Generic / Generic1
With DeriveGeneric, you can derive Generic and Generic1 to support generic programming and libraries like Aeson (JSON).
{-# LANGUAGE DeriveGeneric #-}
import GHC.Generics (Generic)
data User = User
{ name :: String
, age :: Int
} deriving (Show, Generic)
Then libraries can auto-derive things like JSON encoders/decoders using the Generic representation.
Deriving Anyclass
With DeriveAnyClass, you can derive instances for custom typeclasses that provide default method implementations.
{-# LANGUAGE DeriveAnyClass #-}
{-# LANGUAGE DeriveGeneric #-}
import GHC.Generics (Generic)
class MyClass a where
describe :: a -> String
describe _ = "default"
data Foo = Foo Int
deriving (Generic, MyClass)
Here the MyClass instance for Foo uses the default describe implementation.
Often combined with Generic to write generic default definitions.
Deriving Via (Advanced)
DerivingVia lets you derive an instance "via" another type that already has the right behavior.
You need the DerivingVia extension and a helper newtype.
{-# LANGUAGE DerivingVia #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Data.Monoid (Sum(..))
newtype Score = Score Int
deriving (Eq, Show)
deriving (Semigroup, Monoid) via (Sum Int)
Now Score has Semigroup and Monoid instances that behave like Sum Int, without writing any instance code.
The => Operator (Constraint Arrow) in Haskell
What Is the=>Operator?
The => operator in Haskell is called the constraint arrow.
It appears in type signatures and separates:
a list of typeclass constraints, and
the actual type of the function.
General shape:
constraint1, constraint2, ... => type
Example:
show :: Show a => a -> String
Constraints Are Typeclass Requirements
A constraint has the form:
ClassName typeVariable
Examples:
Eq a -- a supports equality
Ord a -- a supports ordering
Num a -- a acts like a number
Monad m -- m is a monad
Functor f -- f is a functor
In the type signature:
Eq a => a -> a -> Bool
This means the function:
takes two values of type a,
requires that a belongs to Eq,
returns a Bool.
Multiple Constraints Using a Tuple
Multiple constraints appear inside parentheses and separated by commas:
(Eq a, Show a) => a -> String
This means:
a must support both Eq and Show.
How GHC Interprets the Constraint Arrow
Conceptually, the type:
Eq a => a -> a -> Bool
means “for all types a that satisfy Eq a”.
Behind the scenes, GHC passes dictionaries containing the functions of the typeclass instance.
For example:
Eq a provides (==) and (/=).
Example: Using a Constraint in a Function
Here is a function using the Eq constraint:
isIn :: Eq a => a -> [a] -> Bool
isIn x xs = any (== x) xs
Why do we need the constraint?
Because (==) is only defined for types in Eq.
Constraint Arrow with Polymorphic Functions
Functions may require multiple constraints to use multiple typeclass methods:
compareAndShow :: (Ord a, Show a) => a -> a -> String
compareAndShow x y =
if x > y
then show x ++ " > " ++ show y
else if x == y
then show x ++ " == " ++ show y
else show x ++ " < " ++ show y
=> vs ->
These look similar but have completely different meanings.
Symbol
Meaning
->
Function arrow: maps inputs to outputs.
=>
Constraint arrow: says that certain typeclasses must be satisfied.
Example of both in one signature:
foo :: (Eq a, Show a) => a -> a -> String
Constraint Arrow in Typeclass Definitions
Typeclasses themselves may impose constraints on their parameters:
class (Eq a, Show a) => MyClass a where
foo :: a -> String
This means any instance of MyClass must also be an instance of Eq and Show.
Constraint Arrow in Instance Declarations
Instance declarations can also have constraints:
instance (Eq a, Show a) => Show (Pair a) where
show (Pair x y) = "(" ++ show x ++ "," ++ show y ++ ")"
Here, Pair a has a Show instance as long as a has both Eq and Show instances.
Constraint Arrow Inside Type Synonyms (Using ConstraintKinds)
With the ConstraintKinds extension, constraints themselves become first-class:
{-# LANGUAGE ConstraintKinds #-}
type Number a = (Num a, Ord a)
Use it like this:
foo :: Number a => a -> a -> a
foo x y = if x > y then x else y
Constraint Arrow in Higher-Kinded Types
Some typeclasses operate on type constructors, requiring constraints on type parameters:
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
The constraint Functor f => ensures that every Applicative is also a Functor.
Constraint Arrow with Forall Quantifiers (Advanced)
Using extensions like RankNTypes, constraints can appear in polymorphic types:
{-# LANGUAGE RankNTypes #-}
bar :: (forall a. Show a => a -> String) -> (String, String)
bar f = (f 3, f "hi")
Here Show a => applies inside a universal quantifier.
Kinds * and * -> * in Haskell
What Are Kinds?
In Haskell, types classify values, and kinds classify types.
You can think of kinds as "types of types".
The most common kind is *, pronounced "star" or "Type".
Historically and in GHCi, you will often see *, more modern notation uses Type (from Data.Kind), but the idea is the same.
-- Value has a type:
42 :: Int
-- Type has a kind:
Int :: *
Maybe :: * -> *
Either :: * -> * -> *
You can inspect kinds in GHCi with :k or :kind.
Kind *: Concrete (Fully Applied) Types
A type of kind * is a concrete type that can have values.
Examples of types of kind *:
Int :: *
Bool :: *
Char :: *
[Int] :: *
Maybe Int :: *
Either String Int :: *
All of these can appear as the type of a value or function parameter/result:
x :: Int
x = 42
name :: String
name = "haskell"
maybeNum :: Maybe Int
maybeNum = Just 10
Key point: only types of kind * classify actual runtime values.
Kind * -> *: Type Constructors
A type of kind * -> * is a type constructor that takes a concrete type and returns a concrete type.
It is "waiting for one type argument".
Examples:
Maybe :: * -> *
[] :: * -> *
IO :: * -> *
When you apply them to a type of kind *, you get a new type of kind *:
Maybe Int :: *
Maybe Bool :: *
[Char] :: *
IO Int :: *
Think of Maybe as a function at the type level:
Maybe :: * -> *
Maybe a :: * -- when a :: *
Higher-Kinded Types: * -> * -> * and Beyond
Some type constructors take two or more type parameters:
Either :: * -> * -> *
(,) :: * -> * -> *
Either takes two * types:
Either String Int :: *
Either String :: * -> * -- partially applied
Either :: * -> * -> *
You can partially apply type constructors, just like functions.
Higher kinds (like (* -> *) -> *, etc.) appear with more advanced type-level programming, but the core idea stays the same.
Why * -> * Matters: Typeclasses Like Functor and Monad
Many important typeclasses (like Functor, Applicative, Monad) work on type constructors of kind * -> *, not on concrete types.
class Functor f where
fmap :: (a -> b) -> f a -> f b
Here f must have kind * -> *, because we use f a and f b where a and b are concrete types (*).
Examples of valid Functor instances:
instance Functor Maybe where ...
instance Functor [] where ...
instance Functor IO where ...
instance Functor (Either e) where ...
Notice Either has kind * -> * -> *, but we turn it into a * -> * by fixing the first argument: (Either e).
You cannot write instance Functor Int where ..., because Int :: *, not * -> *.
Using:kindin GHCi
GHCi lets you inspect kinds with :k (or :kind):
Prelude> :k Int
Int :: *
Prelude> :k Maybe
Maybe :: * -> *
Prelude> :k Maybe Int
Maybe Int :: *
Prelude> :k Either
Either :: * -> * -> *
Prelude> :k Either String
Either String :: * -> *
This is extremely helpful for understanding whether something is a concrete type or a type constructor.
* vs Type
Modern GHC internally uses Type (from Data.Kind) instead of *, but conceptually they are equivalent.
import Data.Kind (Type)
-- These are conceptually the same:
Int :: Type
Maybe :: Type -> Type
You will still often see * in documentation and GHCi output, especially in older code; just read * as "Type".
Advanced: Beyond * (Other Kinds)
With extensions like DataKinds, kinds become richer:
{-# LANGUAGE DataKinds #-}
-- Promoted values become types, and types get more specific kinds
data Color = Red | Green | Blue
-- Kinds: Color, not just *
But for a large amount of everyday Haskell, focusing on * and * -> * is enough.
Input and Output in Haskell
Why Is IO Special in Haskell?
Haskell is a pure functional language:
Functions cannot have side effects (e.g., printing, reading files, randomness) unless explicitly marked.
Every pure function must always produce the same output for the same input.
But real programs must interact with the world.
Haskell solves this using the IO type and the IO Monad.
Key idea:
IO values describe actions.
The runtime executes them only inside main.
main :: IO ()
main = putStrLn "Hello!"
putStrLn "Hello!" has type IO () meaning:
an IO action that outputs a string,
with no useful return value (()).
The IO Type
IO is a type constructor with kind * -> *:
IO :: * -> *
This means IO wraps a “normal type” to represent an action returning that type:
IO Int -- an action that returns an Int
IO String -- an action that returns a String
IO () -- an action with no meaningful result
You do NOT execute IO actions yourself, Haskell's runtime does.
Do-notation: Sequencing IO
IO actions are sequenced with do-notation:
main :: IO ()
main = do
putStrLn "Enter your name:"
name <- getLine
putStrLn ("Hello, " ++ name ++ "!")
Facts about do-notation:
LHS of <- extracts the pure value from an IO action.
You may only use <- with IO actions.
Last expression in a do-block must be an IO action.
x <- 3 -- ❌ illegal, 3 is not an IO action
y <- getLine -- ✔️ OK
Basic IO Operations
Printing
putStr :: String -> IO ()
putStrLn :: String -> IO ()
print :: Show a => a -> IO ()
main = do
content <- readFile "data.txt"
putStrLn "File contents:"
putStrLn content
Example of manual handle management:
main = do
h <- openFile "log.txt" AppendMode
hPutStrLn h "new log entry"
hClose h
Exception Handling in IO
Use Control.Exception:
import Control.Exception (catch, IOException)
main = do
content <- catch (readFile "xxx.txt")
(\e -> do let _ = e :: IOException
putStrLn "File not found!"
return "")
putStrLn content
IO with pure functions
You cannot call IO inside pure code.
But pure functions can be used *inside* IO for transformations:
process :: String -> Int
process = length
main = do
s <- getLine
print (process s)
Always separate pure computation from IO orchestration.
Returning values from IO
Use return (or pure) to inject a pure value into IO:
main = do
let x = 10
y <- return (x * 2)
print y
return does NOT exit a function; it wraps a value in IO.
return x :: IO x
Infinite IO Loops
Because IO is monadic, infinite loops are easy:
forever :: IO a -> IO b
main = forever $ do
putStrLn "Enter something:"
s <- getLine
print (length s)
Sequencing a List of IO Actions
Haskell provides:
sequence :: [IO a] -> IO [a]
mapM :: (a -> IO b) -> [a] -> IO [b]
mapM_ :: (a -> IO b) -> [a] -> IO ()
traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
main = do
names <- mapM (\_ -> getLine) [1..3]
print names
Functors, Applicative Functors, and Monoids in Haskell
Overview
This chapter introduces three of the most important abstractions in Haskell’s typeclass hierarchy:
Functor — things you can map over
Applicative — functors with function application inside a context
Monoid — things that can be combined with an identity
They are foundational for Haskell’s standard library, parsing libraries, IO sequencing, concurrent programming, and functional design.
These abstractions come from category theory, but we will focus on the practical usage first.
Functors: Mapping Over a Structure
A Functor allows you to apply a pure function to values inside a context (container-like structure).
Definition:
class Functor f where
fmap :: (a -> b) -> f a -> f b
Key idea:fmap applies a function to the values inside a structure without modifying its shape.
Monoid is orthogonal but often used with Applicative and Monad:
Error accumulation
Logging
Building data structures
Combining validation results
Many Applicatives use Monoids internally for combination.
Example: Validation with Applicative and Monoid Errors
Suppose we want to validate fields and accumulate multiple error messages:
import Data.Monoid (Sum(..))
validate :: Int -> Either [String] Int
validate n
| n < 0 = Left ["Negative"]
| n > 100 = Left ["Too large"]
| otherwise = Right n
combine :: Either [String] (Int, Int)
combine =
(,) <$> validate 5
<*> validate (-2)
Applicative + Monoid gives parallel validation with error accumulation.
What Exactly Does f a Mean? Understanding Type Constructors in Haskell
In Haskell, the notation f a looks like a function call, but it is not a value-level function.
This syntax belongs to the type level, where f is a type constructor and a is a type that f takes as an input.
A type constructor is like a "function on types":
It receives one or more types
It produces a new type
But it only exists at compile time
Type-Level Application
Maybe Int -- apply the constructor Maybe to Int
[Char] -- apply the list constructor [] to Char
IO String -- apply IO to String
Either Int Bool -- apply Either to two types
These are all examples of type application, not value application.
Even though f a looks like calling f on a, it's happening entirely in the type system.
Type Constructors vs Value Functions
f 3 -- value-level function call
f a -- type-level constructor application
The similarity is only syntactic.
Type constructors:
Never run at runtime
Cannot be evaluated
Only exist to build types
Kinds: Why f Must Have the Form * -> *
class Functor f where
fmap :: (a -> b) -> f a -> f b
f is required to have the kind * -> *, meaning it takes one type and returns a new type.
Examples of valid f:
Maybe
[] (the list type constructor)
IO
Either e (partially applied)
Concrete Examples
Example 1: Maybe
f = Maybe
f a = Maybe a -- a new type
Example 2: Lists
f = []
f a = [a]
Example 3: IO
f = IO
f a = IO a
All these match the shape f a, meaning they construct a new type from a type.
Partial Application of Type Constructors
Either String Int -- full application
Either String -- partial: kind becomes * -> *
You can apply only some arguments of a multi-parameter constructor.
This is needed so Either e can be made into a Functor:
instance Functor (Either e) where
fmap f (Right x) = Right (f x)
fmap _ (Left e) = Left e
Why f a is NOT a Function
f a cannot be evaluated.
It cannot be passed to functions.
It has no runtime value.
It only describes types of values, not values themselves.
Why Functor Requires a Type Constructor (* -> *)
A Functor instance must be defined for a type constructorf whose kind is * -> *.
This means f must accept a type argument and produce a new type. For example:
Maybe Int
[Bool]
IO String
Either String Char
Because of this requirement, Functor cannot be defined for simple, fully-applied types such as:
Int
Bool
Float
Char
These types have kind * and do not take any type parameters — therefore they have no internal structure to “map over”.
Functor works only for type constructors such as:
Maybe
[] (the list constructor)
IO
Either e (partially applied)
Tree
Vector
(,) a (pair constructor with the first argument fixed)
These all take a type argument (a) and form new types (f a), meaning they have a “container-like” structure into which fmap can apply a function.
Summary
f is a type constructor
a is a type argument
f a is a new type built from the constructor
f a resembles function application but occurs only in the type system
Many important abstractions (Functor, Monad, Applicative) rely on this pattern
Monads in Haskell
What Is a Monad?
A Monad is a design pattern that allows you to:
sequence computations,
chain operations that depend on previous results,
model effects (state, IO, exceptions, nondeterminism) in a pure functional way.
Monads are not about "side effects" — they are about describing computations in steps.
Definition (simplified):
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
return: wrap a pure value into the monadic context.
(>>=) (bind): chain computations where output of one step feeds the next.
Every Monad is automatically a Functor and Applicative.
The Bind Operator(>>=)
The heart of a Monad is (>>=):
(>>=) :: m a -> (a -> m b) -> m b
Interpretation:
Take a computation of type m a,
extract its original value a,
pass it to a function that returns the next computation m b.
(>>=) sequences operations where the next step depends on the result of the previous one.
This is the key difference between Monad and Applicative.
The(>>)Operator
A simplified sequencing operator:
(>>) :: m a -> m b -> m b
It ignores the result of the first action, keeping only the second.
Useful when sequencing but not depending on earlier values:
putStrLn "A" >> putStrLn "B"
do-notation: Syntactic Sugar for Monads
Haskell provides do-notation to write monadic code more naturally:
main = do
putStrLn "Enter a number:"
s <- getLine
let n = read s :: Int
print (n * 2)
This is just syntactic sugar for:
main =
putStrLn "Enter a number:" >>=
\_ -> getLine >>=
\s -> let n = read s in
print (n * 2)
Important:
x <- m extracts the pure value inside the monad.
Last line in a do-block must be monadic.
Monad Laws (A lawful monad must satisfy)
Left identity
return a >>= f ≡ f a
Right identity
m >>= return ≡ m
Associativity
(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
These guarantee predictable sequencing.
Common Monad Instances
Maybe: computations that may fail.
instance Monad Maybe where
Nothing >>= _ = Nothing
Just x >>= f = f x
Example:
safeDiv a b =
if b == 0 then Nothing else Just (a `div` b)
calc = Just 10 >>= \x ->
Just 2 >>= \y ->
safeDiv x y
Either e: computations that can fail with an error.
instance Monad (Either e) where
Left e >>= _ = Left e
Right x >>= f = f x
List: nondeterministic computations.
instance Monad [] where
xs >>= f = concat (map f xs)
IO: sequencing interaction with the real world.
main = do
name <- getLine
putStrLn ("Hello " ++ name)
Monads vs Applicatives vs Functors
Concept
Capabilities
Signature
Functor
map a pure function over a structure
fmap :: (a -> b) -> f a -> f b
Applicative
apply wrapped functions to wrapped values
(<*>) :: f (a -> b) -> f a -> f b
Monad
perform computations where next step depends on previous results
(>>=) :: m a -> (a -> m b) -> m b
Hierarchy: Functor < Applicative < Monad
Every Monad is automatically an Applicative and a Functor.
Examples of Monad Use Cases
Maybe Monad: chaining computations that may fail.
lookupUser id = ...
lookupAddress user = ...
lookupZip address = ...
getZip id =
lookupUser id >>= lookupAddress >>= lookupZip
List Monad: generate combinations.
pairs = do
x <- [1,2]
y <- ['a','b']
return (x, y)
-- [(1,'a'),(1,'b'),(2,'a'),(2,'b')]
Either Monad: chain computations that produce errors.
parseInt s =
if all isDigit s then Right (read s)
else Left "not a number"
sumInts a b = do
x <- parseInt a
y <- parseInt b
return (x + y)
IO Monad: real-world programs.
main = do
putStrLn "Enter a number:"
s <- getLine
print (read s + 1)
Kleisli Composition
The operator (>=>) composes monadic functions:
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
Example:
f >=> g >=> h
Zippers in Haskell
What Is a Zipper?
A zipper is a functional data structure that allows:
efficient navigation through a data structure,
local editing of a focus element,
while preserving the immutability of the original structure.
Originally introduced by Gérard Huet in 1997, zippers are widely used for:
navigating trees,
writing editors or cursors,
interpreters or evaluation machines,
Undo/redo structures,
data manipulation with context preservation.
A zipper stores the current focus, and the context needed to rebuild the entire structure.
An Intuitive Example: List Zipper
We introduce zippers using lists:
data ListZipper a = ListZipper [a] a [a]
This represents:
the list of elements to the left of the focus, in reverse order,
the current element in focus,
the list of elements to the right of the focus.
Example for the list [1,2,3,4,5] with focus on 3:
ListZipper [2,1] 3 [4,5]
Moving left and right becomes efficient:
goLeft (ListZipper (l:ls) x rs) = ListZipper ls l (x:rs)
goRight (ListZipper ls x (r:rs)) = ListZipper (x:ls) r rs
We never reconstruct the entire list; we just update small pieces.
Zippers for Trees (The classical application)
Consider a binary tree:
data Tree a
= Empty
| Node a (Tree a) (Tree a)
A zipper for trees allows navigation like:
go to left child
go to right child
go back to parent
edit or replace any node
Idea: store the current subtree and the path (context) back to the root.
The Tree Zipper Context
To move down a tree, you must remember:
which child you came from,
the value at the parent,
the sibling subtree.
Define a "breadcrumb" that stores this context:
data Crumb a
= LeftCrumb a (Tree a) -- went left, store value & right subtree
| RightCrumb a (Tree a) -- went right, store value & left subtree
Zipper is then:
type Breadcrumbs a = [Crumb a]
type Zipper a = (Tree a, Breadcrumbs a)
Now the zipper holds:
focused subtree
breadcrumbs describing the path back up
Navigating the Tree
Go left:
goLeft :: Zipper a -> Zipper a
goLeft (Node x l r, bs) = (l, LeftCrumb x r : bs)
Go right:
goRight :: Zipper a -> Zipper a
goRight (Node x l r, bs) = (r, RightCrumb x l : bs)
Go up (using stored information):
goUp :: Zipper a -> Zipper a
goUp (t, LeftCrumb x r : bs) = (Node x t r, bs)
goUp (t, RightCrumb x l : bs) = (Node x l t, bs)
Each move requires O(1) time.
Editing with a Zipper
Zippers make edits simple because you operate only on the focused node.
Replace the focused value:
modify :: (a -> a) -> Zipper a -> Zipper a
modify f (Node x l r, bs) = (Node (f x) l r, bs)
Replace the focused subtree entirely:
attach :: Tree a -> Zipper a -> Zipper a
attach t (_, bs) = (t, bs)
You can modify deeply nested values without reconstructing the whole tree.
Building and Rebuilding the Entire Structure
Once edits are done, return to the root:
top :: Zipper a -> Zipper a
top z@(_, []) = z
top z = top (goUp z)
If the pattern fails, it triggers the monad’s fail behavior.
Using do-notation with Other Monads (Not Just IO)
do-notation works for any monad, not only IO.
Example: Maybe monad for computations that can fail.
half :: Int -> Maybe Int
half x = if even x then Just (x `div` 2) else Nothing
example :: Maybe Int
example = do
a <- half 20
b <- half a
return b
-- example == Just 5
If any half call returns Nothing, the whole block is Nothing.
Works similarly for:
Either e
[] (list monad)
custom monads
transformer stacks like ReaderT, StateT, etc.
Empty do Blocks and return
Every do-block must evaluate to a monadic value.
return injects a pure value into the monad.
example = do
return 42 -- :: Maybe Int, IO Int, etc.
return does not end the block (unlike other languages).
It simply wraps a pure value inside the monad.
Sequencing Without Bind:action1 >> action2
If you don’t care about the result of an action, you drop the <-:
main = do
putStrLn "Hello"
putStrLn "World"
Desugars to:
main =
putStrLn "Hello" >>
putStrLn "World"
Common Pitfalls
Forgetting that let does not use in inside do blocks.
let x = 10 in print x -- ❌ not allowed inside do
Using <- on pure values.
x <- 5 -- ❌ Wrong: 5 is not monadic
let x = 5 -- ✔ Correct
Mixing up do with imperative semantics.
Under the hood, do is still purely functional.
Practical Real-World Code Examples of Functor, Applicative, and Monad
Introduction:
Functor: lets you apply a pure function inside a context (like Maybe, [], IO).
Applicative: lets you apply a function inside a context to arguments also inside contexts. Useful for combining independent effects.
Monad: lets you run computations where each step depends on the result of the previous step.
Functor: Apply a Pure Function Inside a Context
The key method is fmap :: (a -> b) -> f a -> f b.
1.Maybe aas Functor
-- Double a number inside Maybe
example1 :: Maybe Int
example1 = fmap (*2) (Just 10)
-- Nothing stays Nothing
example2 :: Maybe Int
example2 = fmap (*2) Nothing
Monad lets you run sequential computations where later steps depend on earlier results.
Uses:
>>= (bind)
return
1.Maybe aas Monad — sequential failure
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)
example8 :: Maybe Int
example8 = do
a <- safeDiv 100 2 -- Just 50
b <- safeDiv a 5 -- Just 10
return b
example8 == Just 10
If any step divides by zero → whole chain becomes Nothing.
2.[] a / [a]List Monad — branching / nondeterminism
example9 :: [(Int, Int)]
example9 = do
x <- [1,2]
y <- [10,20]
return (x,y)
example9 == [(1,10),(1,20),(2,10),(2,20)]
Each choice branches → list monad acts like nondeterministic computation.
3.IO aMonad — dependent input/output
main3 :: IO ()
main3 = do
putStrLn "What is your name?"
name <- getLine
putStrLn ("Hello, " ++ name ++ "!")
The output of getLine determines the next step.
4. State Monad — threading state
Very practical for simulations, counters, parsers, etc.
import Control.Monad.State
tick :: State Int Int
tick = do
n <- get
put (n + 1)
return n
example10 :: (Int, Int)
example10 = runState (tick >> tick >> tick) 0
tickTwice :: State Int (Int, Int)
tickTwice = do
a <- tick
b <- tick
return (a, b)
example10 == (2,3)
-- Explanation:
-- tick 1: returns 0, state becomes 1
-- tick 2: returns 1, state becomes 2
-- tick 3: returns 2, state becomes 3
Putting It All Together: A Practical Example
Task: read two numbers, validate them, and add them.
readInt :: String -> Maybe Int
readInt s =
case reads s of
[(n, "")] -> Just n
_ -> Nothing
example11 :: IO ()
example11 = do
putStrLn "Enter a number:"
x <- readInt <$> getLine -- Functor: apply inside IO
putStrLn "Enter another:"
y <- readInt <$> getLine -- Functor again
let result = pure (+) <*> x <*> y -- Applicative: combine Maybe
case result of
Nothing -> putStrLn "Invalid input"
Just sum -> putStrLn ("Sum: " ++ show sum)
Control Flow in Haskell
Overview: Expressions, Not Statements
In Haskell, control flow is expression-based:
There are no traditional "statements" like in C or Java.
Everything (even an if) is an expression that produces a value.
This chapter will cover:
if / then / else
guards
pattern matching and case
let / where
recursion as looping
higher-order functions
monadic control (do, when, etc.)
if / then / else
Haskell’s if is an expression and must have an else branch.
General shape:
absVal :: Int -> Int
absVal n =
if n < 0
then -n
else n
Important points:
The condition must be Bool.
then and else branches must have the same type.
Because it is an expression, you can nest it anywhere:
description :: Int -> String
description n = "The number is " ++
if n > 0 then "positive"
else if n == 0 then "zero"
else "negative"
In practice, nested ifs quickly become hard to read; Haskell offers nicer tools: guards and pattern matching.
Guards: Multi-Way Branching for Functions
Guards give a clean, readable way to encode multi-branch logic.
Syntax (on a function definition):
sign :: Int -> Int
sign n
| n < 0 = -1
| n == 0 = 0
| otherwise = 1
Read it as: "sign of n is -1 if n < 0, 0 if n == 0, otherwise 1".
otherwise is just a synonym for True, used as a final catch-all guard.
Guards are evaluated top to bottom; the first True guard wins.
You can also use guards in where blocks or case expressions (indirectly via helper functions).
Pattern Matching and case Expressions
You can pattern match in:
function arguments,
let / where bindings,
case ... of expressions.
Pattern matching in function arguments:
head' :: [a] -> a
head' (x:_) = x
head' [] = error "empty list"
The compiler chooses the first pattern that matches the argument value.
case expression (expression-form pattern matching):
describeMaybe :: Maybe Int -> String
describeMaybe m =
case m of
Nothing -> "No value"
Just n -> "Value: " ++ show n
General form:
case expression of
pattern1 -> result1
pattern2 -> result2
...
They behave as in other languages, but are still pure and lazy:
a && b evaluates b only if a is True.
a || b evaluates b only if a is False.
This gives familiar "short-circuit" control flow.
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y
| y /= 0 && x `mod` y == 0 = Just (x `div` y)
| otherwise = Nothing
let / where: Local Bindings for Structured Branches
Local bindings help keep control-flow expressions clean.
areaMessage :: Double -> Double -> String
areaMessage w h =
let area = w * h
in if area > 100
then "Large area: " ++ show area
else "Small area: " ++ show area
let ... in ... is an expression.
greeting :: String -> String
greeting name
| long = "Hello, distinguished " ++ name
| short = "Hi, " ++ name
| otherwise = "Hey " ++ name
where
len = length name
long = len > 10
short = len < 4
where attaches local definitions to a function equation or pattern, often making guards more readable.
Recursion as "Loops"
Haskell has no for, while, or do ... while loops.
Instead, you use:
recursion, or
higher-order functions that encapsulate common recursion patterns.
sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs
This recursive function plays the role of a loop summing all elements.
Tail-recursive style (often optimized by GHC):
sumList' :: [Int] -> Int
sumList' xs = go 0 xs
where
go acc [] = acc
go acc (y:ys) = go (acc + y) ys
Here, go mimics a loop with an accumulator.
Higher-Order Control: map, filter, fold, any, all
Common "loops" are abstracted into reusable higher-order functions:
map :: (a -> b) -> [a] -> [b]
filter :: (a -> Bool) -> [a] -> [a]
foldr :: (a -> b -> b) -> b -> [a] -> b
any :: (a -> Bool) -> [a] -> Bool
all :: (a -> Bool) -> [a] -> Bool
Instead of writing explicit loops, you describe "what" you want to do:
transform every element → map
keep only some → filter
combine all into one value → fold
This style is extremely idiomatic in Haskell and controls the flow of data through your program.
Monadic Control Flow and do-Notation
When dealing with effects (IO, Maybe, Either, State, etc.), we use monads.
Control flow in monadic code is written with do-notation:
askName :: IO ()
askName = do
putStrLn "What is your name?"
name <- getLine
if null name
then putStrLn "You didn't enter a name!"
else putStrLn ("Hello, " ++ name ++ "!")
Here, control flow is:
sequential (first print, then read, then branch),
with branching done via normal expressions (if, case, guards).
In other monads (like Maybe), do-notation gives a "short-circuiting" style control flow:
safeRoot :: Double -> Maybe Double
safeRoot x
| x < 0 = Nothing
| otherwise = Just (sqrt x)
safeExpr :: Double -> Double -> Maybe Double
safeExpr x y = do
r1 <- safeRoot x
r2 <- safeRoot y
return (r1 + r2)
If either safeRoot returns Nothing, the whole do-block evaluates to Nothing.
This gives you a "fail fast" control flow without explicit ifs.
Monadic Control Helpers:when, unless, forM, mapM
The Control.Monad module provides utilities for common control-flow patterns inside monads.
when :: Monad m => Bool -> m () -> m ()
unless :: Monad m => Bool -> m () -> m ()
forM :: Monad m => [a] -> (a -> m b) -> m [b]
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
when / unless as monadic if helpers:
import Control.Monad (when, unless)
askSecret :: IO ()
askSecret = do
putStrLn "Are you sure? (yes/no)"
ans <- getLine
when (ans == "yes") $
putStrLn "The secret is: Haskell is cool!"
unless (ans == "yes") $
putStrLn "No secret for you."
forM / mapM for "looping" with effects:
import Control.Monad (forM_)
printLines :: [String] -> IO ()
printLines xs = forM_ xs $ \line -> do
putStrLn line
forM_ is like a monadic for-each loop that discards the result list (_ means "ignore result").
Introduction to Cabal (Haskell’s Build & Package Tool)
What Is Cabal?
Cabal is the standard build and packaging system for Haskell projects.
It provides:
a declarative project configuration format (.cabal files),
automatic dependency resolution,
build, test, and install operations,
package publishing via Hackage.
Cabal is similar to tools like:
npm for JavaScript,
pip for Python,
cargo for Rust.
Haskell developers often use:
cabal directly, or
stack (built on top of the Cabal library).
Key Concepts
The Cabal Library
A Haskell library that defines the format and logic for package descriptions.
Used by both cabal and stack.
Hackage
The official community package repository for Haskell.
Cabal downloads dependencies from here by default.
Sandboxes / Nix-style local builds
Modern Cabal uses per-project isolation via cabal.project files.
This avoids global dependency pollution.
Creating a New Cabal Project
Create a new project skeleton:
cabal init
This asks you several questions:
library / executable / both
project name
language version
dependencies
license
Then it generates:
myproject.cabal
cabal.project
app/Main.hs or src/ directory
Understanding the.cabalFile
The .cabal file is the heart of your project, it describes:
data keyword introducing a new algebraic datatype.
TypeName must begin with a capital letter.
typeVars zero or more lowercase identifiers:
data Maybe a = ...
data Either a b = ...
data MyType = ...
= introduces constructor alternatives (sum type).
Constructor must start with uppercase letter.
fields zero or more types as parameters.
Constructors: positional vs record form
-- Positional
Constructor t1 t2 t3
-- Record syntax
Constructor
{ field1 :: Type1
, field2 :: Type2
}
Record fields must be lowercase identifiers.
Positional arguments are simply listed after the constructor.
Multiple constructors
data Shape
= Circle Float
| Rectangle Float Float
| Triangle
| separates constructors.
Each constructor may have different arity.
Type constraints in data grammar (rare)
data Eq a => Weird a = W a
Although syntactically allowed, this form is discouraged and almost never used.
The deriving clause
deriving (Eq, Ord, Show)
Always appears at the end of the data declaration.
Contains a comma-separated list of typeclasses the compiler should automatically implement.
The Grammar of class Declarations
Full grammar skeleton:
class (Constraints) => ClassName typeVar where
method1 :: type
method2 :: type
...
class keyword introducing a typeclass.
(Constraints) => are optional, parentheses required if there are multiple constraints.
ClassName must be capitalized.
typeVar is usually a single lowercase variable (often a), may have more.
where introduces method signatures.
method declarations must each have a type signature.
Simple example of minimal grammar:
-- In the future, you can use (==) on any two values of the same type a,
-- as long as that type a has an Eq instance.
class Eq a where
(==) :: a -> a -> Bool
Operator methods are allowed and treated the same as named functions.
Class with multiple methods
class Ord a where
(<) :: a -> a -> Bool
(<=) :: a -> a -> Bool
(>) :: a -> a -> Bool
Class with superclasses (constraints)
class (Eq a, Show a) => MyClass a where
method :: a -> String
Constraints appear before the =>.
If there is only one constraint, parentheses may still be required depending on style:
class Eq a => MyClass a where ...
Multi-parameter typeclasses (valid grammar)
class Convert a b where
convert :: a -> b
Associated defaults in grammar (still just syntax):
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
x /= y = not (x == y) -- default implementation
Grammar allows method implementations inside a class.
These are optional, missing ones must be implemented by instances.
instance keyword introducing an instance declaration.
Constraints are same structure as class constraints.
ClassName is capitalized.
typeArgs must fully apply the class’ type variables.
Example:
instance Eq Person where
(Person n1 a1) == (Person n2 a2) =
n1 == n2 && a1 == a2
Grammar rule: type variables must be "fully saturated"
-- Valid
instance Ord (Maybe a) where ...
-- INVALID (partial application)
instance Ord Maybe where ...
Instances require all type parameters to be applied.
Irrefutable Patterns in Haskell
What Is an Irrefutable Pattern?
A pattern is irrefutable if it never fails to match when evaluated in its usual binding context.
By contrast, a refutable pattern can fail and cause:
a pattern match failure at runtime, or
another pattern (like in case) to be tried instead.
Common examples:
Irrefutable:
x (simple variable)
~pat (lazy pattern)
top-level and let pattern bindings behave as if they had ~
Refutable:
(x:xs)
Just x
(a,b) in case / function arguments
Simple Irrefutable Patterns
These patterns never fail:
x :: Int
x = 10 -- "x" is an irrefutable pattern
y :: (Int, Int)
y = (1, 2) -- at top level, "y" is a variable pattern, always matches
Even if the right-hand side diverges (undefined, infinite recursion), the pattern itself does not fail, it fails only when you force the value.
Pattern Bindings Are Lazy (Irrefutable) by Default
A subtle (but very important) point: In a let or top-level binding, patterns are lazy → effectively irrefutable.
example1 :: Int
example1 =
let (x, y) = undefined
in 1
This does not crash, because:
The pattern (x, y) is not forced when the let is entered.
It is only forced when x or y is used.
Here we return 1 without ever needing x or y.
example2 :: Int
example2 =
let (x, y) = undefined
in x -- "x" is demanded, pattern is forced, crash at runtime
So for let (x, y) = ..., the pattern behaves like a lazy pattern (~(x,y)).
Explicit Lazy Patterns with~
The tilde introduces an explicit lazy (irrefutable) pattern:
f :: (Int, Int) -> Int
f ~(x, y) = 1
Here:
f undefined returns 1 without crashing.
Because ~(x, y) does not force evaluation of the argument unless x or y is used.
g :: (Int, Int) -> Int
g (x, y) = 1
In contrast: g undefined crashes immediately, because the strict pattern (x,y) is forced.
Lazy Patterns indo-Notation
In monadic do-blocks, a pattern to the left of <- is normally refutable:
exampleMaybe :: Maybe Int
exampleMaybe = do
Just x <- Just 3 -- OK
return x
exampleFail :: Maybe Int
exampleFail = do
Just x <- Nothing -- pattern match failure => Nothing
return x
Here the match with Nothing does not cause an immediate failure.
But if x is later forced, evaluation will fail.
In practice, lazy patterns in do are used carefully to avoid unwanted failures or to break certain dependency cycles.
Irrefutable Patterns in where / let Blocks
Patterns in where and let behave like lazy bindings by default.
h :: Int
h =
let pair@(x, y) = undefined
in 1 -- OK, pattern not forced
h :: Int
h =
let ~(pair@(x, y)) = undefined
in 1 -- OK, pattern not forced
h :: Int
h =
let ~pair@(x, y) = undefined
in 1 -- OK, pattern not forced
k :: Int
k =
let pair@(x, y) = undefined
in x -- crash: forcing "x" forces the pattern
pair@(x, y) is a pattern binding and is lazily matched.
This is effectively an irrefutable pattern at binding time.
Irrefutable vs Refutable in case and Function Arguments
In case and function argument patterns, the default is strict (refutable).
strictPair :: (Int, Int) -> Int
strictPair (x, y) = x + y
lazyPair :: (Int, Int) -> Int
lazyPair ~(x, y) = 1
strictPair undefined → crash.
lazyPair undefined → 1.
caseExample :: Maybe Int -> Int
caseExample m =
case m of
Just x -> x -- refutable
Nothing -> 0
Just x here is refutable: if m is Nothing, the pattern fails and the next branch is tried.
When Irrefutable Patterns Are Useful
Irrefutable (lazy) patterns can be useful when:
you want to define something in terms of itself (cyclic structures),
you want to bind names to parts of a structure but may not need them,
you want to avoid premature pattern match failures in lazy code.
Example: tying a knot with an infinite structure:
ones :: [Int]
ones = xs
where
~(x:xs) = 1 : xs -- lazy pattern allows "xs" to refer to itself
Without ~, this kind of "knot tying" would crash immediately.
Infix Operators, Fixity, and Associativity in Haskell
What Is an Infix Operator?
In Haskell, most functions are written in prefix form: add 2 3
But operators like +, *, == are written in infix form: 2 + 3
Haskell lets you turn any binary functions into an infix operator using backticks: 5 `mod` 2
And you can define your own operators using symbolic names: (<>), (&&), (!), (!?), etc.
Why Fixity Matters
If you write a ! b ! c, Haskell must know how to group the expression:
(a ! b) ! c (left-associative)
or a ! (b ! c) (right-associative)
Fixity declarations tell the compiler:
associativity: left, right, or none
precedence: how tightly it binds compared to other operators
Fixity Declaration Syntax
The general form is:
infixl <precedence> op1, op2, op3
infixr <precedence> op
infix <precedence> op
Associativity keywords:
infixl → left associative
infixr → right associative
infix → no associativity (chaining is disallowed)
Precedence: a number from 0 (lowest) to 9 (highest).
The lookup operation elegantly expresses tree traversal:
lookup :: Ord k => k -> Map k v -> Maybe v
lookup _ Tip = Nothing
lookup k (Bin _ kx x l r) =
case compare k kx of
LT -> lookup k l -- Search left subtree
GT -> lookup k r -- Search right subtree
EQ -> Just x -- Found it!
This pure recursive definition is remarkably clear:
Base case: Empty tree returns Nothing
Recursive case: Compare and traverse left or right
No mutation, no side effects, just pure computation
The insert function showcases functional programming's elegance:
insert :: Ord k => k -> v -> Map k v -> Map k v
insert kx x Tip = Bin 1 kx x Tip Tip
insert kx x (Bin sz ky y l r) =
case compare kx ky of
LT -> balance ky y (insert kx x l) r
GT -> balance ky y l (insert kx x r)
EQ -> Bin sz kx x l r -- Update value
Key observations:
No mutation: Creates a new tree path from root to insertion point
Structural sharing: Unmodified subtrees are reused
Automatic balancing: The balance function maintains tree balance
Structural sharing visualization:
-- Original tree:
-- 5
-- / \
-- 3 7
-- / \
-- 1 4
-- After inserting 6:
-- 5
-- / \
-- 3 7 <- 7's subtree is shared
-- / \ /
-- 1 4 6 <- Only new path from root is created
-- The nodes for 1, 4, and the right subtree of 7
-- are shared between old and new versions!
Usage examples:
-- Single insertion
inventory :: M.Map String Int
inventory = M.insert "apples" 10 M.empty
-- Multiple insertions
inventory2 = M.insert "oranges" 15
$ M.insert "bananas" 8
$ M.insert "apples" 10
$ M.empty
-- Update existing key
inventory3 = M.insert "apples" 20 inventory2 -- Replaces 10 with 20
-- Insert with combining function
incrementCount = M.insertWith (+) "apples" 5 inventory2
-- If "apples" exists, adds 5 to existing value
The Balance Function: Maintaining Tree Health
Size-balanced trees use a clever balancing strategy based on subtree sizes:
-- Balancing constant
delta, ratio :: Int
delta = 3 -- Size ratio limit
ratio = 2 -- Size ratio for single vs double rotation
balance :: k -> v -> Map k v -> Map k v -> Map k v
balance k x l r
| sizeL + sizeR <= 1 = Bin (sizeL + sizeR + 1) k x l r
| sizeR > delta * sizeL = rotateL k x l r
| sizeL > delta * sizeR = rotateR k x l r
| otherwise = Bin (sizeL + sizeR + 1) k x l r
where
sizeL = size l
sizeR = size r
The beauty of this approach:
Simple invariant: No subtree is more than 3× larger than its sibling
Efficient: Most operations don't require rebalancing
Predictable: Guarantees O(log n) height
Rotation functions:
-- Left rotation
rotateL :: k -> v -> Map k v -> Map k v -> Map k v
rotateL k x l r@(Bin _ ky y ly ry)
| size ly < ratio * size ry = singleL k x l r
| otherwise = doubleL k x l r
-- Single left rotation:
-- k ky
-- / \ / \
-- l ky => k ry
-- / \ / \
-- ly ry l ly
singleL :: k -> v -> Map k v -> Map k v -> Map k v
singleL k x l (Bin _ ky y ly ry) =
Bin (size l + size ly + size ry + 1) ky y
(Bin (size l + size ly + 1) k x l ly) ry
Rotations preserve the binary search tree property while rebalancing the tree.
Deletion: Elegant Recursion
Deletion demonstrates how FP handles complex operations elegantly:
delete :: Ord k => k -> Map k v -> Map k v
delete _ Tip = Tip
delete k (Bin _ kx x l r) =
case compare k kx of
LT -> balance kx x (delete k l) r
GT -> balance kx x l (delete k r)
EQ -> glue l r -- Remove this node
-- Glue combines two subtrees after deletion
glue :: Map k v -> Map k v -> Map k v
glue Tip r = r
glue l Tip = l
glue l r
| size l > size r =
let (km, vm, l') = deleteFindMax l
in balance km vm l' r
| otherwise =
let (km, vm, r') = deleteFindMin r
in balance km vm l r'
The glue function beautifully handles the tricky case:
When deleting a node with two children
Takes the maximum from left or minimum from right
Promotes it to replace the deleted node
Recursively balances the result
Usage examples:
scores :: M.Map String Int
scores = M.fromList [("Alice", 95), ("Bob", 87), ("Carol", 92)]
-- Delete a key
scores' = M.delete "Bob" scores
-- Result: fromList [("Alice", 95), ("Carol", 92)]
-- Delete non-existent key (safe, returns unchanged map)
scores'' = M.delete "David" scores
-- Adjust or delete conditionally
scores''' = M.update (\v -> if v < 90 then Nothing else Just v) "Bob" scores
-- Removes Bob because his score is < 90
Map Operations: Functional Beauty
Mapping over values:
map :: (a -> b) -> Map k a -> Map k b
map _ Tip = Tip
map f (Bin sx kx x l r) = Bin sx kx (f x) (map f l) (map f r)
-- Example: double all values
scores = M.fromList [("Alice", 95), ("Bob", 87)]
doubled = M.map (*2) scores
-- Result: fromList [("Alice", 190), ("Bob", 174)]
Mapping with keys:
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
-- Example: format grade strings
grades = M.fromList [("Alice", 95), ("Bob", 87)]
formatted = M.mapWithKey (\name score -> name ++ ": " ++ show score) grades
-- Result: fromList [("Alice", "Alice: 95"), ("Bob", "Bob: 87")]
Folding (reducing):
foldr :: (a -> b -> b) -> b -> Map k a -> b
foldr _ z Tip = z
foldr f z (Bin _ _ x l r) = foldr f (f x (foldr f z r)) l
-- Example: sum all values
scores = M.fromList [("Alice", 95), ("Bob", 87), ("Carol", 92)]
total = M.foldr (+) 0 scores -- 274
-- Example: collect all passing scores
passing = M.foldr (\score acc -> if score >= 90 then score:acc else acc) [] scores
-- Result: [95, 92]
Filtering:
filter :: (a -> Bool) -> Map k a -> Map k a
-- Example: keep only high scores
highScores = M.filter (>= 90) scores
-- Result: fromList [("Alice", 95), ("Carol", 92)]
-- With keys
topStudents = M.filterWithKey (\name score -> name /= "Bob" && score >= 90) scores
Set Operations on Maps
Union (merge maps):
union :: Ord k => Map k a -> Map k a -> Map k a
union Tip r = r
union l Tip = l
union l r = hedgeUnion NothingS NothingS l r
-- Uses efficient hedge algorithm to merge trees
-- Example
map1 = M.fromList [("a", 1), ("b", 2)]
map2 = M.fromList [("b", 3), ("c", 4)]
result = M.union map1 map2
-- fromList [("a", 1), ("b", 2), ("c", 4)]
-- Left-biased: keeps values from first map for duplicate keys
-- Union with combining function
combined = M.unionWith (+) map1 map2
-- fromList [("a", 1), ("b", 5), ("c", 4)]
Intersection:
intersection :: Ord k => Map k a -> Map k b -> Map k a
intersection Tip _ = Tip
intersection _ Tip = Tip
intersection l r = hedgeInt NothingS NothingS l r
-- Example
map1 = M.fromList [("a", 1), ("b", 2), ("c", 3)]
map2 = M.fromList [("b", 20), ("c", 30), ("d", 40)]
common = M.intersection map1 map2
-- fromList [("b", 2), ("c", 3)]
-- Intersection with combining function
combined = M.intersectionWith (*) map1 map2
-- fromList [("b", 40), ("c", 90)]
Difference:
difference :: Ord k => Map k a -> Map k b -> Map k a
-- Example
map1 = M.fromList [("a", 1), ("b", 2), ("c", 3)]
map2 = M.fromList [("b", 20), ("d", 40)]
diff = M.difference map1 map2
-- fromList [("a", 1), ("c", 3)]
-- Keeps keys only in first map
Conversion Functions
To/from lists:
-- Convert to list
scores = M.fromList [("Alice", 95), ("Bob", 87)]
pairs = M.toList scores -- [("Alice", 95), ("Bob", 87)]
keys = M.keys scores -- ["Alice", "Bob"]
values = M.elems scores -- [95, 87]
-- Convert from list
scores' = M.fromList [("Carol", 92), ("David", 88)]
-- From list with combining function for duplicates
pairs = [("a", 1), ("b", 2), ("a", 3)]
result = M.fromListWith (+) pairs -- fromList [("a", 4), ("b", 2)]
To/from ascending lists (O(n)):
-- More efficient if list is already sorted
sortedPairs = [("Alice", 95), ("Bob", 87), ("Carol", 92)]
scores = M.fromAscList sortedPairs -- O(n) instead of O(n log n)
-- Check if valid for fromAscList
isValidAsc = all (\(a,b) -> fst a < fst b) $ zip sortedPairs (tail sortedPairs)
Performance Characteristics
Understanding the costs of operations:
Operation
Time Complexity
Notes
lookup
O(log n)
Binary search through tree
insert
O(log n)
Search + possible rebalancing
delete
O(log n)
Search + glue + rebalancing
member
O(log n)
Similar to lookup
size
O(1)
Cached in each node
union
O(m log(n/m + 1))
Where m ≤ n; efficient merge
intersection
O(m log(n/m + 1))
Where m ≤ n
map
O(n)
Must visit every node
foldr/foldl
O(n)
Must visit every node
fromList
O(n log n)
Build balanced tree
fromAscList
O(n)
Linear if already sorted
Space efficiency:
Each node requires: key + value + 2 pointers + size = ~5 words
Structural sharing means modifications only copy O(log n) nodes
Old versions remain accessible without duplicating entire tree
Why This Implementation is Beautiful
Immutability as a feature:
No defensive copying needed
Thread-safe by default
Enables time-travel debugging and undo/redo
Makes reasoning about code dramatically simpler
Structural sharing is elegant:
-- Creating multiple versions is cheap
let v1 = M.insert "x" 1 original
v2 = M.insert "y" 2 original
v3 = M.insert "z" 3 original
-- All three versions share most of the original tree!
Composability:
-- Operations compose naturally
result = M.map (*2) -- double values
$ M.filter (>10) -- keep only large values
$ M.insert "new" 15 -- add new entry
$ M.delete "old" -- remove old entry
$ originalMap
-- Each step returns a new map, no mutation
Type safety:
-- Keys must be comparable
scores :: M.Map String Int -- String keys, Int values
ages :: M.Map Int String -- Int keys, String values
-- Compiler prevents mixing incompatible types
-- M.union scores ages -- Type error!
-- Polymorphism enables generic operations
process :: Ord k => M.Map k Int -> M.Map k Int
process = M.map (*2) . M.filter (>0)
Lazy evaluation synergy:
-- Build map lazily
infiniteMap = M.fromList [(n, n*n) | n <- [1..]]
-- Only evaluates elements as needed
-- Take first few squares
firstSquares = M.toList $ M.filterWithKey (\k _ -> k <= 10) infiniteMap
-- Fusion optimizations eliminate intermediate maps
optimized = M.map (+1) . M.map (*2) $ original
-- GHC can fuse these into a single traversal
Practical Examples
Word frequency counter:
import qualified Data.Map as M
import Data.Char (toLower)
import Data.List (words)
wordFrequency :: String -> M.Map String Int
wordFrequency text =
M.fromListWith (+)
$ map (\w -> (w, 1))
$ words
$ map toLower text
-- Usage
countWords = wordFrequency "hello world hello Haskell world"
-- Result: fromList [("haskell",1),("hello",2),("world",2)]
Graph represented as adjacency map:
type Graph = M.Map String [String]
graph :: Graph
graph = M.fromList
[ ("A", ["B", "C"])
, ("B", ["C", "D"])
, ("C", ["D"])
, ("D", [])
]
-- Get neighbors
neighbors :: String -> Graph -> [String]
neighbors node g = M.findWithDefault [] node g
-- Add edge
addEdge :: String -> String -> Graph -> Graph
addEdge from to = M.insertWith (++) from [to]
Caching/memoization:
import qualified Data.Map as M
-- Fibonacci with memoization
fib :: Int -> Integer
fib n = fibMemo M.! n
where
fibMemo = M.fromList [(i, fibCalc i) | i <- [0..n]]
fibCalc 0 = 0
fibCalc 1 = 1
fibCalc i = fibMemo M.! (i-1) + fibMemo M.! (i-2)
-- The map caches all intermediate results
Configuration management:
type Config = M.Map String String
defaultConfig :: Config
defaultConfig = M.fromList
[ ("host", "localhost")
, ("port", "8080")
, ("timeout", "30")
]
-- Merge user config with defaults
loadConfig :: [(String, String)] -> Config
loadConfig userSettings = M.union userConfig defaultConfig
where userConfig = M.fromList userSettings
-- Get config value with default
getConfig :: String -> Config -> String
getConfig key cfg = M.findWithDefault "" key cfg
Advanced Patterns
Merging with custom strategies:
-- Keep maximum value for duplicate keys
mergeMax :: M.Map String Int -> M.Map String Int -> M.Map String Int
mergeMax = M.unionWith max
-- Concatenate lists for duplicate keys
mergeLists :: M.Map String [Int] -> M.Map String [Int] -> M.Map String [Int]
mergeLists = M.unionWith (++)
-- Merge with awareness of both values
mergeCustom :: M.Map k a -> M.Map k a -> M.Map k a
mergeCustom = M.mergeWithKey
(\_ x y -> Just (combine x y)) -- Both present
id -- Only in left
id -- Only in right
where combine x y = x -- Custom logic here
Grouping operations:
-- Group items by a key function
groupBy :: Ord k => (a -> k) -> [a] -> M.Map k [a]
groupBy f = M.fromListWith (++) . map (\x -> (f x, [x]))
-- Example: group words by length
words = ["cat", "dog", "bird", "ant", "elephant"]
byLength = groupBy length words
-- fromList [(3,["cat","dog","ant"]),(4,["bird"]),(8,["elephant"])]
-- Example: group students by grade
students = [("Alice", 95), ("Bob", 87), ("Carol", 95), ("David", 87)]
byGrade = groupBy snd students
-- fromList [(87,[("Bob",87),("David",87)]),(95,[("Alice",95),("Carol",95)])]
Nested maps:
-- Two-level lookup: country -> city -> population
type CityData = M.Map String (M.Map String Int)
worldCities :: CityData
worldCities = M.fromList
[ ("USA", M.fromList [("NYC", 8000000), ("LA", 4000000)])
, ("Japan", M.fromList [("Tokyo", 14000000), ("Osaka", 2700000)])
]
-- Nested lookup
lookupCity :: String -> String -> CityData -> Maybe Int
lookupCity country city db = do
cities <- M.lookup country db
M.lookup city cities
-- Example
tokyo = lookupCity "Japan" "Tokyo" worldCities -- Just 14000000
Difference tracking:
-- Track changes between two maps
data Change a = Added a | Removed a | Modified a a
deriving (Show, Eq)
changes :: (Ord k, Eq v) => M.Map k v -> M.Map k v -> M.Map k (Change v)
changes old new =
let added = M.map Added $ M.difference new old
removed = M.map Removed $ M.difference old new
modified = M.intersectionWith compareValues old new
in M.unions [added, removed, modified]
where
compareValues oldV newV
| oldV == newV = Modified oldV newV -- No change actually
| otherwise = Modified oldV newV
Comparison with Other Approaches
vs Hash Tables:
Aspect
Balanced Tree (Map)
Hash Table
Lookup
O(log n) - predictable
O(1) average, O(n) worst
Insert
O(log n) - predictable
O(1) average, O(n) worst
Immutability
Natural with structural sharing
Requires copying entire table
Ordered iteration
O(n) in sorted order
O(n) in arbitrary order
Memory
~5 words per entry
~3 words per entry + array
Thread safety
Implicit (immutable)
Requires explicit locking
Predictability
Always O(log n)
Can degrade to O(n)
vs Association Lists:
-- Association list: [(k, v)]
type AssocList k v = [(k, v)]
-- Simple but slow
lookupAssoc :: Eq k => k -> [(k, v)] -> Maybe v
lookupAssoc k = lookup k -- O(n) linear search
-- Map is dramatically faster for large datasets
-- But assoc lists are simpler for small collections (< 10 items)
Common Pitfalls and Best Practices
Don't nest lookups deeply:
-- Bad: deeply nested Maybe
badLookup m k1 k2 k3 = do
m1 <- M.lookup k1 m
m2 <- M.lookup k2 m1
M.lookup k3 m2
-- Better: flatten structure or use lenses
Use strict operations when appropriate:
import qualified Data.Map.Strict as MS
-- Strict insert avoids space leaks
strictMap = MS.fromList [(1, expensiveComputation 1)]
-- Strict version forces evaluation of values immediately
Prefer fromAscList when possible:
-- If data is already sorted, use O(n) construction
sortedData = [(1, "a"), (2, "b"), (3, "c")]
fastMap = M.fromAscList sortedData -- O(n)
-- Instead of
slowMap = M.fromList sortedData -- O(n log n)
Use specialized combining functions:
-- Incrementing counters
-- Good
counts = M.insertWith (+) key 1 oldCounts
-- Better
counts = M.alter incrementOrInsert key oldCounts
where incrementOrInsert Nothing = Just 1
incrementOrInsert (Just n) = Just (n + 1)
Remember maps are ordered:
-- Take advantage of ordering
smallest = M.lookupMin myMap -- O(log n)
largest = M.lookupMax myMap -- O(log n)
-- Range queries are efficient
range = M.filterWithKey (\k _ -> k >= minKey && k <= maxKey) myMap