Functional Programming Past Paper Portal Functional Programming Lab Portal

Haskell Fundamentals

Expressions and Reduction
Expressions vs. Statements

In functional programming, computation is expressed through expressions rather than statements, which is a fundamental difference from imperative languages.

See also: Functions and Equations, Evaluation Strategies, Equational Reasoning, Polymorphism

Imperative Languages Functional Languages
Use statements: instructions that are executed sequentially Everything is an expression that reduces to a value
Modify program state and control flow Don’t modify state; expressions are evaluated
Example: x = x + 1; (modifies x) Example: let x' = x + 1 in ... (creates new value)

Key Points

In Haskell, everything is an expression

All expressions eventually reduce to values

Even control structures (like if-then-else) are expressions that return values

See: Pattern Matching and Recursion, Lists and List Comprehensions

Examples

Conditional as expression:
if 2 < 3 then
  "two is less than three"
else
  "three is less than two"
Let expressions:
let msg =
  if 2 < 3 then
    "two is less than three"
  else
    "three is less than two"
in
  "Result: " ++ msg
Reduction

Reduction is the process of evaluating an expression to produce a value.

Church-Rosser Property

Functional reduction satisfies the Church-Rosser property:

Regardless of the order in which subexpressions are evaluated

The final result will always be the same (if evaluation terminates)

This property is central to functional programming and enables:

Equational Reasoning

Referential transparency

Functional parallelism

Example of Reduction
1 + (2 + (3 + 4))
→ 1 + (2 + 7)
→ 1 + 9
→ 10
Different reduction paths lead to the same result:
(10 * 4) + (5 * 3)
↙         ↘
40 + (5 * 3)    (10 * 4) + 15
↘         ↙
      55
Types

In Haskell, every expression has a type that classifies values:

See: Polymorphism, Algebraic Data Types
5 :: Int
True :: Bool
(1, "Hello") :: (Int, String)
Types help prevent nonsensical expressions (e.g., 5 + True would be a type error).

Type Inference

Haskell infers types automatically, but it’s good practice to add type signatures for top-level functions:
addOne :: Int -> Int
addOne x = x + 1
Summary

Statements are instructions in imperative languages; expressions reduce to values in functional languages

Reduction is the process of evaluating expressions to values

The Church-Rosser property ensures consistent results regardless of evaluation order

Every expression in Haskell has a type

Link to original

Functions and Equations
Functions are central to functional programming. In Haskell, functions are first-class citizens, meaning they can be:
- Passed as arguments
- Returned as results
- Assigned to variables
- Stored in data structures
See also: Higher-Order Functions, Pattern Matching and Recursion, Polymorphism, Equational Reasoning

Function Definitions

Functions in Haskell can be defined in several ways:

Lambda (Anonymous) Functions

See: Lambda Calculus, Higher-Order Functions
```
\name -> "Hello, " ++ name
\n -> n + 5
```
Named Functions with Equations
```
add x y = x + y
min x y = if x < y then x else y
```
Type Signatures
```
add :: Int -> Int -> Int
add x y = x + y
```
Currying

Haskell functions are “curried” by default, meaning they take one argument at a time and return a function that accepts the next argument.

See: Higher-Order Functions, Polymorphism
```
add :: Int -> (Int -> Int)
add x = \y -> x + y
```
This is equivalent to:
```
add :: Int -> Int -> Int
add x y = x + y
```
Benefits of Currying

Currying enables partial application - supplying only some of the arguments to create a new function:
```
addFive :: Int -> Int
addFive = add 5
 
-- Usage:
addFive 10  -- Returns 15
```
Function Application

Function application in Haskell doesn’t require parentheses around arguments:
```
f x y z  -- Applies function f to arguments x, y, and z
```
Function application has the highest precedence:
```
f x * 2  -- Means (f x) * 2, not f (x * 2)
```
Function Composition

The composition operator (.) combines functions:

See: Higher-Order Functions, Functors and Applicatives
```
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)
```
This enables point-free style programming:
```
-- With explicit parameter
\x -> show (add10 x)
 
-- Point-free style
show . add10
```
Equations are not Assignments

In imperative languages, we might write:
```
x = x + 1  // Modify x by adding 1
```
In Haskell, an equation like x = x + 1 is not an assignment; it’s a recursive definition that tries to define x as its successor, which would lead to an infinite loop.

Key Principles
- Variables in Haskell are immutable
- Equations establish mathematical relationships
- Once defined, a value cannot change
See: Expressions and Reduction, Equational Reasoning

Key Points to Remember
1. All functions in Haskell take exactly one argument (currying makes multi-argument functions possible)
2. Partial application is a powerful technique for creating specialized functions
3. Function composition provides a way to combine functions elegantly
4. Equations in Haskell define values; they don’t modify state
See: Pattern Matching and Recursion, Higher-Order Functions

Common Mistakes
- Confusing equations with assignments
- Misunderstanding function application precedence
- Forgetting to account for currying in type signatures
Link to original

Imperative Languages	Functional Languages
Use statements: instructions that are executed sequentially	Everything is an expression that reduces to a value
Modify program state and control flow	Don’t modify state; expressions are evaluated
Example: `x = x + 1;` (modifies x)	Example: `let x' = x + 1 in ...` (creates new value)

Lists and List Comprehensions
Lists are one of the most fundamental data structures in Haskell. They store sequences of elements of the same type.

See also: Pattern Matching and Recursion, Algebraic Data Types, Polymorphism, Higher-Order Functions

List Basics

Syntax

Lists in Haskell are written with square brackets and commas:
[1, 2, 3, 4, 5] :: [Int]
["Hello", "FP", "Students"] :: [String]
List Construction

Lists can be constructed in several ways:
Cons operator (:)
1 : (2 : (3 : []))  -- Equivalent to [1, 2, 3]
Range notation
[1..10]  -- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
['a'..'z']  -- ['a', 'b', 'c', ..., 'z']
Infinite lists
[1..]  -- [1, 2, 3, 4, ...] (thanks to lazy evaluation)
List Manipulation

Basic operations for accessing lists:
head [1, 2, 3]  -- 1
tail [1, 2, 3]  -- [2, 3]
[1, 2, 3] !! 1  -- 2 (0-indexed)
Warning: These functions are partial (can fail with an error on empty lists).

List Comprehensions

List comprehensions provide a concise syntax for creating lists based on existing lists.

See: Pattern Matching and Recursion, Property-Based Testing

Basic Syntax
[expression | generator, condition]
Where:

expression is the output expression

generator pulls values from a list

condition filters values (optional)

Examples
Basic generator
[x * 2 | x <- [1..5]]  -- [2, 4, 6, 8, 10]
With filtering condition
[x * 2 | x <- [1..10], x `mod` 2 == 0]  -- [4, 8, 12, 16, 20]
Multiple generators (Cartesian product)
[(x, y) | x <- [1, 2], y <- ['a', 'b']]  -- [(1,'a'), (1,'b'), (2,'a'), (2,'b')]
Dependent generators
[(x, y) | x <- [1..3], y <- [x..3]]  -- [(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)]
Pythagorean triples
[(x, y, z) | x <- [1..10], y <- [x..10], z <- [y..10], x^2 + y^2 == z^2]
List Operations

See: Higher-Order Functions, Functors and Applicatives

List Concatenation
[1, 2, 3] ++ [4, 5]  -- [1, 2, 3, 4, 5]
List Zipping
zip [1, 2, 3] ["one", "two", "three"]  -- [(1,"one"), (2,"two"), (3,"three")]
zipWith (+) [1, 2, 3] [4, 5, 6]  -- [5, 7, 9]
Lists vs. Tuples

See: Algebraic Data Types

Lists Tuples
Same type for all elements Can have different types
Variable length Fixed length
[Int], [String], etc. (Int, String), (Bool, Int, Char), etc.
Operations like map, filter Accessed by pattern matching

Key Points to Remember

Lists are homogeneous (all elements have the same type)

Lists can be infinite thanks to lazy evaluation

List comprehensions provide a powerful, declarative way to create and transform lists

The cons operator (:) and empty list ([]) are the fundamental building blocks of lists

Pattern matching on lists typically uses the (x:xs) pattern

See: Pattern Matching and Recursion
Link to original

Algebraic Data Types
Algebraic Data Types (ADTs) are composite types in Haskell that allow you to create custom data structures.

See also: Pattern Matching and Recursion, Lists and List Comprehensions, Polymorphism, Type Synonyms, Newtype, Maybe, Either, Functors and Applicatives

Basic Syntax

ADTs are defined using the data keyword:
```
data TypeName = Constructor1 [Types] | Constructor2 [Types] | ...
```
Types of ADTs

Sum Types (Enumerations)

Sum types provide alternatives, similar to enums in other languages:
```
data Season = Spring | Summer | Autumn | Winter
```
Here, Season can be any one of the four constructors.

Product Types

Product types combine multiple values:
```
data Point = Point Float Float
--             ^      ^     ^
--             |      |     Second coordinate (Float)
--             |      First coordinate (Float)  
--             Constructor name
```
Mixed Sum and Product Types

Many ADTs combine both concepts:
```
data Shape = Circle Float  -- Radius
           | Rectangle Float Float  -- Width and Height
           | Triangle Float Float Float  -- Three sides
```
Record Syntax

For product types with many fields, record syntax provides named fields:
```
data Person = Person { name :: String
                     , age :: Int
                     , email :: String
                     }
```
Benefits of record syntax:
- Automatic accessor functions (name, age, email)
- Easier to create/update values with many fields
- Better readability for complex types
Recursive Data Types

See: Lists and List Comprehensions, Pattern Matching and Recursion

ADTs can be recursive, referring to themselves in their definition:
```
data List a = Empty | Cons a (List a)
```
```
data Tree a = Leaf | Node a (Tree a) (Tree a)
```
These recursive structures enable complex data structures like lists, trees, and graphs.

Parameterized Types

See: Polymorphism, Maybe, Either

Types can be parameterized with type variables:
```
data Maybe a = Nothing | Just a
```
```
data Either a b = Left a | Right b
```
This enables generic programming, similar to generics in other languages.

Type Synonyms

Type synonyms create aliases for existing types:
```
type String = [Char]
type Name = String
type Age = Int
type Person = (Name, Age)
```
Unlike data, type doesn’t create a new type; it just provides an alternative name.

Newtype

For single-constructor, single-field types, newtype provides a more efficient alternative to data:
```
newtype Age = Age Int
```
Benefits of newtype:
- No runtime overhead
- Creates a distinct type (unlike type)
- Compiler guarantees it has exactly one constructor with one field
Pattern Matching with ADTs

See: Pattern Matching and Recursion

ADTs are typically used with pattern matching:
```
showSeason :: Season -> String
showSeason Spring = "It's spring!"
showSeason Summer = "It's summer!"
showSeason Autumn = "It's autumn!"
showSeason Winter = "It's winter!"
```
```
area :: Shape -> Float
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
area (Triangle a b c) = sqrt (s * (s - a) * (s - b) * (s - c))
  where s = (a + b + c) / 2  -- Semi-perimeter
```
The Maybe Type

See: Error Handling, Common Monads

Maybe is a built-in ADT that represents optional values:
```
data Maybe a = Nothing | Just a
```
It’s used to handle potential failures without exceptions:
```
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)
```
Deriving Typeclasses

See: Polymorphism, Functors and Applicatives

Common behaviors can be automatically derived:
```
data Season = Spring | Summer | Autumn | Winter
  deriving (Show, Eq, Ord, Enum)
```
This gives the type:
- String representation (Show)
- Equality testing (Eq)
- Comparison operations (Ord)
- Enumeration capabilities (Enum)
Key Points to Remember
1. ADTs are the primary way to create custom data types in Haskell
2. They can represent both alternatives (sum types) and combinations (product types)
3. Pattern matching is the primary mechanism for working with ADTs
4. Type parameters and recursion make ADTs extremely flexible
5. Maybe and Either are important built-in ADTs for handling potential failures
Link to original

Lists	Tuples
Same type for all elements	Can have different types
Variable length	Fixed length
`[Int]`, `[String]`, etc.	`(Int, String)`, `(Bool, Int, Char)`, etc.
Operations like map, filter	Accessed by pattern matching

Pattern Matching and Recursion
Pattern matching and recursion are core techniques in functional programming that work hand-in-hand to process data structures and implement algorithms.

See also: Algebraic Data Types, Lists and List Comprehensions, Functions and Equations, Higher-Order Functions, Error Handling

Pattern Matching

See: Algebraic Data Types, Lists and List Comprehensions, Functions and Equations

Basic Syntax

Pattern matching is often used in function definitions:
functionName pattern1 = result1
functionName pattern2 = result2
functionName pattern3 = result3
The patterns are tried in order until one matches.

Patterns for Different Types

Numbers and Characters: See Equational Reasoning

Lists: See Lists and List Comprehensions

Tuples: See Algebraic Data Types

ADTs: See Algebraic Data Types

Matching on Numbers and Characters
isZero :: Int -> Bool
isZero 0 = True
isZero _ = False
 
isVowel :: Char -> Bool
isVowel 'a' = True
isVowel 'e' = True
isVowel 'i' = True
isVowel 'o' = True
isVowel 'u' = True
isVowel _ = False
Matching on Lists
isEmpty :: [a] -> Bool
isEmpty [] = True
isEmpty _ = False
 
head' :: [a] -> a
head' [] = error "Empty list"
head' (x:_) = x
 
tail' :: [a] -> [a]
tail' [] = error "Empty list"
tail' (_:xs) = xs
 
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs
Matching on Tuples
fst' :: (a, b) -> a
fst' (x, _) = x
 
snd' :: (a, b) -> b
snd' (_, y) = y
 
addPairs :: [(Int, Int)] -> [Int]
addPairs [] = []
addPairs ((x, y):ps) = (x + y) : addPairs ps
Matching on Algebraic Data Types
data Shape = Circle Float | Rectangle Float Float
 
area :: Shape -> Float
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
 
data Tree a = Leaf | Node a (Tree a) (Tree a)
 
treeDepth :: Tree a -> Int
treeDepth Leaf = 0
treeDepth (Node _ left right) = 1 + max (treeDepth left) (treeDepth right)
Pattern Guards

Pattern guards add conditions to patterns:
absoluteValue :: Int -> Int
absoluteValue n
  | n < 0     = -n
  | otherwise = n
 
grade :: Int -> String
grade score
  | score >= 90 = "A"
  | score >= 80 = "B"
  | score >= 70 = "C"
  | score >= 60 = "D"
  | otherwise   = "F"
case Expressions

Pattern matching can also be done within expressions using case:
describePair :: (Int, Int) -> String
describePair pair = case pair of
  (0, 0) -> "Origin"
  (0, _) -> "Y-axis"
  (_, 0) -> "X-axis"
  (x, y) -> "Point at (" ++ show x ++ "," ++ show y ++ ")"
Recursion

See: Functions and Equations, Higher-Order Functions, Lists and List Comprehensions

Anatomy of Recursive Functions

Base case(s): Simple scenarios where the result is directly computed

Recursive case(s): Complex scenarios where the result depends on smaller instances of the same problem

List Processing with Recursion

See: Lists and List Comprehensions, Higher-Order Functions
length' :: [a] -> Int
length' [] = 0                -- Base case
length' (_:xs) = 1 + length' xs  -- Recursive case
 
map' :: (a -> b) -> [a] -> [b]
map' _ [] = []               -- Base case
map' f (x:xs) = f x : map' f xs  -- Recursive case
 
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []            -- Base case
filter' p (x:xs)             -- Recursive case
  | p x       = x : filter' p xs
  | otherwise = filter' p xs
Recursive Numerical Functions
-- Factorial
factorial :: Integer -> Integer
factorial 0 = 1                    -- Base case
factorial n = n * factorial (n-1)  -- Recursive case
 
-- Fibonacci
fibonacci :: Int -> Integer
fibonacci 0 = 0                              -- Base case 1
fibonacci 1 = 1                              -- Base case 2
fibonacci n = fibonacci (n-1) + fibonacci (n-2)  -- Recursive case
Tree Traversal with Recursion

See: Algebraic Data Types
-- Sum all values in a tree
treeSum :: Tree Int -> Int
treeSum Leaf = 0
treeSum (Node value left right) = value + treeSum left + treeSum right
 
-- Map a function over all values in a tree
treeMap :: (a -> b) -> Tree a -> Tree b
treeMap _ Leaf = Leaf
treeMap f (Node value left right) = Node (f value) (treeMap f left) (treeMap f right)
Mutual Recursion

See: Equational Reasoning

Functions can also be mutually recursive, calling each other:
isEven :: Int -> Bool
isEven 0 = True
isEven n = isOdd (n-1)
 
isOdd :: Int -> Bool
isOdd 0 = False
isOdd n = isEven (n-1)
Tail Recursion

See: Evaluation Strategies

Tail recursion is a special case where the recursive call is the last operation:
-- Not tail recursive
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs  -- Must do addition after recursive call
 
-- Tail recursive version with accumulator
sumTail :: [Int] -> Int
sumTail xs = sumHelper xs 0
  where
    sumHelper [] acc = acc
    sumHelper (x:xs) acc = sumHelper xs (acc + x)  -- Recursive call is last operation
Benefits of tail recursion:

Can be optimized by the compiler into iteration

Doesn’t grow the call stack

Prevents stack overflow for large inputs

Key Points to Remember

Pattern matching is a fundamental technique for working with data in Haskell

Patterns are tried in order; use _ as a catch-all pattern

Recursion replaces loops in functional programming

Every recursive function needs at least one base case to terminate

Tail recursion can be more efficient for large inputs

Link to original

Higher-Order Functions
Higher-order functions (HOFs) are functions that take other functions as arguments or return functions as results. They are a powerful abstraction tool in functional programming.

See also: Functions and Equations, Lists and List Comprehensions, Pattern Matching and Recursion, Functors and Applicatives, Polymorphism, Evaluation Strategies

Core Concepts

Definition

A higher-order function is a function that satisfies at least one of these criteria:

Takes one or more functions as arguments

Returns a function as its result

Benefits

Abstracts common patterns

Reduces code duplication

Enables functional composition

Makes code more concise and readable

Common Higher-Order Functions on Lists

map

Applies a function to every element in a list:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Examples:
map (+1) [1, 2, 3]      -- [2, 3, 4]
map reverse ["abc", "def"]  -- ["cba", "fed"]
map (^ 2) [1..5]        -- [1, 4, 9, 16, 25]
filter

Retains elements that satisfy a predicate:
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
  | p x       = x : filter p xs
  | otherwise = filter p xs
Examples:
filter even [1..10]          -- [2, 4, 6, 8, 10]
filter (> 5) [1, 9, 2, 8, 3] -- [9, 8]
filter isPrime [1..20]       -- [2, 3, 5, 7, 11, 13, 17, 19]
Folds (foldr and foldl)

Folds reduce a list to a single value by applying a binary function:

Right Fold (foldr)
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)
Right fold associates to the right: f x1 (f x2 (f x3 ... (f xn acc)))

Examples:
foldr (+) 0 [1, 2, 3, 4]  -- 10 (1 + (2 + (3 + (4 + 0))))
foldr (:) [] [1, 2, 3]     -- [1, 2, 3] (1 : (2 : (3 : [])))
foldr max 0 [1, 5, 3, 2]   -- 5
Left Fold (foldl)
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs
Left fold associates to the left: f (... f (f (f acc x1) x2) x3 ...) xn

Examples:
foldl (+) 0 [1, 2, 3, 4]  -- 10 (((0 + 1) + 2) + 3) + 4)
foldl (flip (:)) [] [1, 2, 3]  -- [3, 2, 1] (reverses the list)
foldl max 0 [1, 5, 3, 2]   -- 5
Differences Between foldl and foldr

Associativity:

foldl is left-associative

foldr is right-associative

Laziness:

foldr can work on infinite lists when the combining function is lazy in its second argument

foldl always needs to traverse the entire list

Stack Safety:

foldl can cause stack overflow on large lists (use foldl' from Data.List instead)

foldr can be more stack-efficient for operations that short-circuit

zipWith

Combines two lists element-wise using a binary function:
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
Examples:
zipWith (+) [1, 2, 3] [4, 5, 6]       -- [5, 7, 9]
zipWith (*) [1, 2, 3, 4] [10, 20, 30] -- [10, 40, 90]
zipWith (,) [1, 2, 3] ['a', 'b', 'c'] -- [(1,'a'), (2,'b'), (3,'c')]
Function Composition

Function composition combines two functions to form a new function:
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)
Examples:
(length . filter even) [1..10]     -- 5
(reverse . map toUpper) "h
tally x :: Int -> Maybe String
| x < 0 = Nothing
| x == 0 = ""
| Just $ unwords (replicate (div x 5)  ("||||\\") ) ++ [ replicate snd ( (divMod x 5) ) "|" | (divMod x 5) /= 0 ]
tally :: Int -> Maybe String
tally n
  | n <  0    = Nothing
  | n == 0    = Just ""
  | otherwise = Just $ unwords parts
  where
    (fives, rest) = n `divMod` 5
    clusters      = replicate fives "||||\\"
    remainder     = replicate rest "|"
    parts         = clusters ++ [remainder | rest /= 0]
 
 
data Rectangle = Rectangle Int Int
 
x = Rectangle 5 9
 
data Rectangle = Rectangle { 
	width :: Int
	height :: Int
}
 
fun x = 
	width
 
Link to original

Property-Based Testing
Property-based testing is an approach that verifies that properties of a program hold true for a wide range of inputs. In Haskell, the primary tool for property-based testing is the QuickCheck library. This approach is especially useful for testing functions that operate on lists (Lists and List Comprehensions) or that involve algebraic laws (Equational Reasoning).

Core Concepts

What is Property-Based Testing?

Property-based testing:
- Tests that certain properties of your code hold across a range of inputs
- Generates random test data automatically
- Tries to find the simplest counterexample if a property fails
- Provides a systematic way to test code without writing individual test cases
Advantages over Unit Testing

Compared to traditional unit testing:
- Tests behavior rather than specific cases
- Explores edge cases you might not have considered
- Often requires less code to test more thoroughly
- Finds bugs that manual test cases might miss
QuickCheck Basics

Installation

QuickCheck can be installed using Cabal:
```
cabal update
cabal install --lib QuickCheck
```
Importing QuickCheck
```
import Test.QuickCheck
```
Defining Properties

A property in QuickCheck is a function that returns a Bool or a Property value:
```
prop_reverseReverse :: [Int] -> Bool
prop_reverseReverse xs = reverse (reverse xs) == xs
```
Running Tests
```
quickCheck prop_reverseReverse
-- +++ OK, passed 100 tests.
```
For more verbose output:
```
verboseCheck prop_reverseReverse
-- Passed:
-- [0]
-- Passed:
-- [-3,4]
-- ...
```
Common Properties to Test

Identity Properties
```
prop_reverseReverse :: [Int] -> Bool
prop_reverseReverse xs = reverse (reverse xs) == xs
 
prop_sortIdempotent :: [Int] -> Bool
prop_sortIdempotent xs = sort (sort xs) == sort xs
```
Invariant Properties
```
prop_lengthPreserved :: [Int] -> Bool
prop_lengthPreserved xs = length (sort xs) == length xs
```
Transformation Properties
```
prop_mapPreservesLength :: [Int] -> Bool
prop_mapPreservesLength xs = length (map (+1) xs) == length xs
```
Algebraic Properties
```
prop_appendAssociative :: [Int] -> [Int] -> [Int] -> Bool
prop_appendAssociative xs ys zs = (xs ++ ys) ++ zs == xs ++ (ys ++ zs)
```
Constraining Inputs

Sometimes we need to limit the property to certain kinds of inputs:

Using Conditional Properties
```
prop_divisionInverse :: Int -> Int -> Property
prop_divisionInverse x y = y /= 0 ==> (x `div` y) * y + (x `mod` y) == x
```
Using Generators
```
prop_divisionInverse2 :: Int -> NonZero Int -> Bool
prop_divisionInverse2 x (NonZero y) = (x `div` y) * y + (x `mod` y) == x
```
Custom Generators

For more control, we can define our own generators:
```
genEven :: Gen Int
genEven = do
  n <- arbitrary
  return (n * 2)
 
prop_evenNumberIsEven :: Property
prop_evenNumberIsEven = forAll genEven (\n -> even n)
```
Testing Example: A Sorting Function

Let’s verify that a sorting function behaves correctly:
```
-- Properties for a sorting function
prop_sortOrders :: [Int] -> Bool
prop_sortOrders xs = ordered (sort xs)
  where ordered [] = True
        ordered [_] = True
        ordered (x:y:zs) = x <= y && ordered (y:zs)
 
prop_sortPreservesLength :: [Int] -> Bool
prop_sortPreservesLength xs = length (sort xs) == length xs
 
prop_sortPreservesElements :: [Int] -> Bool
prop_sortPreservesElements xs = 
  all (`elem` xs) (sort xs) && all (`elem` sort xs) xs
```
Finding Bugs with QuickCheck

When a property fails, QuickCheck attempts to shrink the counterexample to a minimal case, which is useful for debugging recursive functions (Pattern Matching and Recursion):
```
-- Bug: doesn't handle negative numbers correctly
isAscending :: [Int] -> Bool
isAscending [] = True
isAscending [x] = True
isAscending (x:y:zs) = (x < y) && isAscending (y:zs)
 
-- Testing this buggy function
prop_sortIsAscending :: [Int] -> Bool
prop_sortIsAscending xs = isAscending (sort xs)
 
-- QuickCheck will find a counterexample like:
-- *** Failed! Falsified (after 15 tests and 10 shrinks):
-- [0,0]
```
Correcting the Bug
```
-- Fixed version
isAscending :: [Int] -> Bool
isAscending [] = True
isAscending [x] = True
isAscending (x:y:zs) = (x <= y) && isAscending (y:zs)
                      -- ^ Changed < to <=
```
Performance Considerations
- QuickCheck generates and tests many cases, which can be slow for complex properties
- Use quickCheckWith to configure test parameters:
```
quickCheckWith stdArgs {maxSuccess = 1000} prop_myProperty
```
Best Practices
1. Define simple, specific properties that can be checked independently
2. Think about edge cases and invariants in your functions
3. Test algebraic laws when appropriate (associativity, commutativity, etc.)
4. Use appropriate generators for your data types
5. Combine property-based testing with unit testing for critical code paths
Key Points to Remember
1. QuickCheck generates random test cases to verify properties of your code
2. Properties are expressed as functions that return Bool or Property values
3. When a property fails, QuickCheck tries to find the simplest counterexample
4. Custom generators can be defined for specific test data requirements
5. Property-based testing is especially powerful for functional code, where properties and invariants are well-defined
Common properties to test include identity properties (e.g., reverse (reverse xs) == xs), which relate to the concept of pure functions (Functions and Equations), and algebraic properties such as associativity of list append (++), which is a key law for monads (Monads Basics) and functors/applicatives (Functors and Applicatives).

When testing functions that manipulate lists, such as map, filter, or sort, you are often indirectly testing higher-order functions (Higher-Order Functions).

Best practices for property-based testing include thinking about invariants and algebraic laws, which are also central to Equational Reasoning and Monad Laws.
Link to original
Evaluation Strategies
Evaluation strategies determine when expressions are evaluated during program execution. Haskell uses lazy evaluation by default, which has significant implications for how programs behave.

Lazy vs. Eager Evaluation

Eager (Strict) Evaluation

In eager (strict) evaluation:
- Arguments to functions are evaluated before the function is called
- Expressions are evaluated as soon as they are bound to variables
- Most common programming languages (C, Java, Python, etc.) use eager evaluation
Example in Python (eager):
```
def f(x, y):
    return x + 2
 
# Both arguments are evaluated, even though y is never used
result = f(3, expensive_computation())  
```
Lazy (Non-strict) Evaluation

In lazy (non-strict) evaluation:
- Expressions are only evaluated when their values are needed
- Arguments to functions are not evaluated until they are used inside the function
- Evaluation is delayed until the last possible moment (“call by need”)
Example in Haskell (lazy):
```
f :: Int -> Int -> Int
f x y = x + 2
 
-- y is never evaluated because it's not used in the function body
result = f 3 (expensive_computation)
```
Benefits of Lazy Evaluation

Infinite Data Structures

Lazy evaluation allows for infinite data structures:
```
-- Infinite list of natural numbers
naturals = [0..]
 
-- We can operate on infinite lists
take 5 naturals                  -- [0,1,2,3,4]
take 10 (filter even naturals)   -- [0,2,4,6,8,10,12,14,16,18]
```
Short-Circuit Evaluation

Functions can terminate early without evaluating all arguments:
```
-- Returns first element of the list that satisfies the predicate
find :: (a -> Bool) -> [a] -> Maybe a
find p [] = Nothing
find p (x:xs)
  | p x       = Just x       -- Terminates here if predicate is satisfied
  | otherwise = find p xs
  
-- Only computes until it finds the first prime number greater than 100
find (> 100) primes
```
Performance Optimization

Lazy evaluation can lead to performance optimizations:
1. Avoiding unnecessary computations:
```
if condition then expensiveComputation1 else expensiveComputation2
```
  Only one of the expensive computations will be evaluated, depending on the condition.
2. Fusion transformations:
```
sum (map (*2) [1..1000000])
```
  Can be optimized to avoid creating the intermediate list.
Better Modularity

Lazy evaluation allows for better separation of concerns:
```
-- Producer generates all possible solutions
solutions = generateAllPossibleSolutions problem
 
-- Consumer takes only what it needs
firstSolution = head solutions
bestSolution = minimumBy compareCost solutions
```
Drawbacks of Lazy Evaluation

Unpredictable Space Usage

Lazy evaluation can lead to space leaks if thunks (unevaluated expressions) build up:
```
sum [1..1000000]  -- Can use a lot of memory due to thunk accumulation
```
Harder to Reason About Performance

It can be difficult to predict exactly when expressions will be evaluated.

Not Always More Efficient

For code that needs to evaluate everything anyway, the overhead of tracking thunks can make lazy evaluation less efficient.

Thunks

A thunk is a suspended computation - a promise to compute a value when needed.
- Thunks are created when expressions are not immediately evaluated
- They store all data needed to evaluate the expression later
- When evaluation is needed, the thunk is forced and replaced with the result
Forcing Evaluation

Bang Patterns

Bang patterns (!) can be used to force evaluation:
```
-- This version of sum is strict in its accumulator
sum' :: [Int] -> Int
sum' = go 0
  where
    go !acc [] = acc
    go !acc (x:xs) = go (acc + x) xs
```
Seq Function

The seq function forces evaluation of its first argument before returning the second:
```
seq :: a -> b -> b
 
-- Forces evaluation of x before returning y
x `seq` y
```
Example usage:
```
sum' :: [Int] -> Int
sum' xs = go 0 xs
  where
    go acc [] = acc
    go acc (x:xs) = let acc' = acc + x in acc' `seq` go acc' xs
```
Strictness Annotations

Data types can be made strict with strictness annotations:
```
data Pair a b = Pair !a !b
```
This forces both fields to be evaluated when the constructor is evaluated.

Common Patterns

Lazy Functions vs. Strict Data

A common pattern in Haskell is to write functions that are lazy in their arguments but strict in their data fields:
```
data Vector = Vector !Double !Double !Double
 
dot :: Vector -> Vector -> Double
dot (Vector x1 y1 z1) (Vector x2 y2 z2) = x1*x2 + y1*y2 + z1*z2
```
Worker/Wrapper Transformation

For recursive functions, a common pattern is to have a lazy wrapper function and a strict worker function:
```
sum :: [Int] -> Int
sum = sum' 0  -- Lazy wrapper
  where
    sum' !acc [] = acc  -- Strict worker
    sum' !acc (x:xs) = sum' (acc + x) xs
```
Examples of Infinite Structures

Infinite Lists
```
-- Infinite list of ones
ones = 1 : ones
 
-- Infinite list of Fibonacci numbers
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
-- Primes using the Sieve of Eratosthenes
primes = sieve [2..]
  where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
```
Infinite Trees
```
data Tree a = Node a (Tree a) (Tree a)
 
-- Infinite binary tree where each node contains its path
paths = build []
  where build path = Node path (build (False:path)) (build (True:path))
```
Key Points to Remember
1. Haskell uses lazy evaluation by default: expressions are only evaluated when needed
2. Lazy evaluation enables infinite data structures and certain programming patterns
3. Thunks are delayed computations that are evaluated on demand
4. Strict evaluation can be enforced using bang patterns, seq, or strictness annotations
5. Space leaks are a common issue with lazy evaluation, requiring careful attention to performance
Link to original

Polymorphism
Polymorphism (meaning “many forms”) allows code to work with values of different types. Haskell supports two main kinds of polymorphism: parametric polymorphism and ad-hoc polymorphism (via typeclasses).

Parametric Polymorphism

Parametric polymorphism allows functions to operate on values of any type, without knowing or caring what that type is.

Type Variables

Type variables (usually lowercase letters like a, b, c) represent arbitrary types:
id :: a -> a                 -- Identity function works on any type
length :: [a] -> Int         -- Length works on lists of any type
reverse :: [a] -> [a]        -- Reverse works on lists of any type
fst :: (a, b) -> a           -- First works on any pair of types
Examples of Parametrically Polymorphic Functions
-- Identity function
id :: a -> a
id x = x
 
-- Apply a function twice
twice :: (a -> a) -> a -> a
twice f x = f (f x)
 
-- Swap elements in a pair
swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)
Parametrically Polymorphic Data Types

Data types can also be parametrically polymorphic:
-- List of elements of type a
data List a = Empty | Cons a (List a)
 
-- Binary tree with values of type a
data Tree a = Leaf | Node a (Tree a) (Tree a)
 
-- Maybe type (optional value)
data Maybe a = Nothing | Just a
 
-- Either type (value of one type or another)
data Either a b = Left a | Right b
Parametricity

Parametricity is a property of parametrically polymorphic functions: the behavior of a function is determined solely by its type signature, not by the types it operates on.

For example, a function with type [a] -> Int can only compute properties like length - it cannot inspect the elements themselves because it knows nothing about type a.

Consequences of Parametricity

Free theorems: We get certain properties “for free” based on the type signature

Limited operations: Functions can only perform operations consistent with all possible types

Predictable behavior: Functions behave uniformly across all types

Example: Functions of Type a -> a

How many functions can have the type a -> a?

With parametricity, there’s only one possible function: the identity function id x = x.

This is because any function of type a -> a must work the same way for all types, and the only thing it can do is return its input unchanged.

Ad-hoc Polymorphism via Typeclasses

Ad-hoc polymorphism allows functions to behave differently depending on the type of their arguments. In Haskell, this is accomplished with typeclasses.

What are Typeclasses?

A typeclass defines a set of functions that must be implemented by any type that wants to be a member of that class.
class Show a where
  show :: a -> String
This says: “For a type a to be a member of the Show class, it must implement the show function.”

Typeclass Instances

Types become members of a typeclass by providing implementations of the required functions:
data Color = Red | Green | Blue
 
instance Show Color where
  show Red = "Red"
  show Green = "Green"
  show Blue = "Blue"
Typeclass Constraints

Functions can require that their type parameters belong to specific typeclasses:
-- A function that works on any type that can be shown
printTwice :: Show a => a -> IO ()
printTwice x = do
  putStrLn (show x)
  putStrLn (show x)
The Show a => part is a typeclass constraint, saying “this works for any type a that is a member of the Show class.”

Common Typeclasses

Eq - Equality Testing
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
 
  -- Default implementations
  x /= y = not (x == y)
  x == y = not (x /= y)
Example instance:
instance Eq Color where
  Red == Red = True
  Green == Green = True
  Blue == Blue = True
  _ == _ = False
Ord - Ordering
class Eq a => Ord a where
  compare :: a -> a -> Ordering
  (<), (<=), (>), (>=) :: a -> a -> Bool
  max, min :: a -> a -> a
 
  -- Default implementations provided
Ord has Eq as a superclass, meaning any type that is Ord must also be Eq.

Num - Numeric Types
class Num a where
  (+), (-), (*) :: a -> a -> a
  negate, abs, signum :: a -> a
  fromInteger :: Integer -> a
This allows numeric operations on various types (Int, Float, Double, etc.).

Show - String Conversion
class Show a where
  show :: a -> String
Read - Parsing from Strings
class Read a where
  read :: String -> a
deriving Mechanism

For common typeclasses, Haskell can automatically generate instances:
data Color = Red | Green | Blue
  deriving (Show, Eq, Ord, Enum)
This automatically implements:

show for Show

== and /= for Eq

compare, <, etc. for Ord

succ, pred, etc. for Enum

Custom Typeclasses

You can define your own typeclasses:
class Drawable a where
  draw :: a -> IO ()
  clear :: a -> IO ()
 
data Shape = Circle Float | Rectangle Float Float
 
instance Drawable Shape where
  draw (Circle r) = putStrLn $ "Drawing circle with radius " ++ show r
  draw (Rectangle w h) = putStrLn $ "Drawing rectangle " ++ show w ++ "x" ++ show h
  
  clear _ = putStrLn "Clearing shape"
Comparing Parametric and Ad-hoc Polymorphism

Parametric Polymorphism Ad-hoc Polymorphism (Typeclasses)
One implementation works for all types Different implementations for different types
Functions operate on the structure, not the content Functions can inspect and operate on values
”Uniform” behavior across types Type-specific behavior
Examples: id, map, reverse Examples: show, (+), (==)

Key Points to Remember

Parametric polymorphism uses type variables to create functions that work on any type

Parametricity restricts what polymorphic functions can do, leading to predictable behavior

Typeclasses enable ad-hoc polymorphism, allowing different implementations for different types

Common typeclasses include Eq, Ord, Show, Read, and Num

The deriving mechanism automates the creation of typeclass instances

Link to original

Parametric Polymorphism	Ad-hoc Polymorphism (Typeclasses)
One implementation works for all types	Different implementations for different types
Functions operate on the structure, not the content	Functions can inspect and operate on values
”Uniform” behavior across types	Type-specific behavior
Examples: `id`, `map`, `reverse`	Examples: `show`, `(+)`, `(==)`

Monads and Side-effects

Introduction to IO
Input/Output (IO) operations present a unique challenge in a pure functional language like Haskell. This page explains how Haskell manages side effects while maintaining purity.

The Problem of Side Effects

Pure Functions

A pure function:
- Always returns the same result when given the same arguments
- Has no observable side effects
- Does not depend on external state
In mathematical terms, pure functions are referentially transparent: any expression can be replaced with its value without changing the program’s behavior.

Side Effects

Side effects include:
- Reading/writing files
- Network operations
- Getting user input
- Printing to the console
- Getting the current time
- Generating random numbers
- Modifying mutable data structures
These operations depend on or modify external state, breaking referential transparency.

The Challenge

How can a pure functional language perform impure operations like IO while maintaining its mathematical foundation?

The IO Type

Haskell solves this problem using the IO type, which represents computations that might perform side effects.
```
putStrLn :: String -> IO ()
getLine :: IO String
readFile :: FilePath -> IO String
```
The IO type constructor wraps the type of the value that the IO action will produce:
- IO () - An IO action that produces no useful result (just the unit value ())
- IO String - An IO action that produces a String
- IO Int - An IO action that produces an Int
Key Insight

An IO a value doesn’t represent a value of type a; it represents a recipe or description for obtaining a value of type a (potentially with side effects).

The Haskell runtime system executes these recipes when the program runs.

Basic IO Operations

Printing to the Console
```
putStr :: String -> IO ()      -- Print without a newline
putStrLn :: String -> IO ()    -- Print with a newline
print :: Show a => a -> IO ()  -- Print any showable value
```
Reading from the Console
```
getChar :: IO Char   -- Read a single character
getLine :: IO String -- Read a line of text
```
File Operations
```
readFile :: FilePath -> IO String        -- Read entire file as String
writeFile :: FilePath -> String -> IO () -- Write String to file
appendFile :: FilePath -> String -> IO () -- Append String to file
```
Sequencing IO Actions with do Notation

do notation allows us to sequence IO actions and use their results:
```
greeting :: IO ()
greeting = do
  putStrLn "What's your name?"
  name <- getLine
  putStrLn $ "Hello, " ++ name ++ "!"
```
This code:
1. Prints a question
2. Waits for user input and binds the result to name
3. Prints a greeting using the name
Key Components of do Notation
1. Action Sequencing: Actions are executed in order from top to bottom
2. Result Binding: name <- getLine binds the result of getLine to the variable name
3. Let Bindings: let x = expression defines a pure value within the do block
4. Return: return value creates an IO action that produces value without any side effects
```
example :: IO Int
example = do
  x <- readFile "number.txt"
  let n = read x :: Int
  let doubled = n * 2
  putStrLn $ "Doubled number: " ++ show doubled
  return doubled  -- The final result of the IO action
```
The main Function

Every Haskell program has a main function:
```
main :: IO ()
main = do
  putStrLn "Hello, world!"
```
The Haskell runtime system executes the IO actions described by main.

Combining Pure and Impure Code

Pure functions cannot directly use IO results, and IO actions cannot directly use pure functions. Instead, we:
1. Extract values from IO actions using <- in a do block
2. Process them with pure functions
3. Wrap results back in IO actions if needed
```
processFile :: FilePath -> IO String
processFile path = do
  content <- readFile path           -- Impure: read file
  let processed = map toUpper content -- Pure: process with function
  return processed                   -- Wrap result in IO
```
The return Function

return lifts a pure value into an IO action:
```
return :: a -> IO a
```
return x creates an IO action that produces x without performing any actual IO.

Common Patterns

Reading and Processing Input
```
readAndProcess :: IO ()
readAndProcess = do
  input <- getLine
  let processed = process input  -- Pure function
  putStrLn processed
```
Interactive Loops
```
loop :: IO ()
loop = do
  input <- getLine
  if input == "quit"
    then return ()  -- End the loop
    else do
      putStrLn $ "You entered: " ++ input
      loop  -- Recursive call for the next iteration
```
Error Handling
```
import System.IO.Error
 
safeReadFile :: FilePath -> IO (Either IOError String)
safeReadFile path = do
  result <- try (readFile path)
  return result
```
Random Number Generation
```
import System.Random
 
randomExample :: IO Int
randomExample = do
  randomNumber <- randomRIO (1, 100)
  return randomNumber
```
Mutable References

Mutable references can be created within the IO monad:
```
import Data.IORef
 
counterExample :: IO ()
counterExample = do
  counter <- newIORef 0        -- Create reference with initial value 0
  value <- readIORef counter   -- Read current value
  writeIORef counter (value+1) -- Update value
  newValue <- readIORef counter
  print newValue               -- Will print 1
```
Why This Approach Matters

By encapsulating side effects within the IO type:
1. Type Safety: The type system clearly distinguishes between pure and impure code
2. Referential Transparency: Pure parts of the program remain referentially transparent
3. Reasoning: We can reason about pure functions using equational reasoning
4. Composition: IO actions can be composed like other values
5. Lazy Evaluation: Haskell maintains its lazy evaluation strategy outside of IO
Common Pitfalls

No “Escape” from IO

There is no safe way to extract a value from an IO action without being in IO yourself:
```
-- This doesn't exist in safe Haskell
unsafeGetValue :: IO a -> a
```
If a function uses IO, its return type must reflect this with the IO type constructor.

Debugging with Trace

For debugging pure functions, the Debug.Trace module provides functions that “cheat” by using unsafePerformIO:
```
import Debug.Trace
 
factorial :: Int -> Int
factorial n = trace ("Computing factorial of " ++ show n) $
              if n <= 1 then 1 else n * factorial (n-1)
```
These functions should only be used for debugging, not in production code.

Key Points to Remember
1. Haskell uses the IO type to represent computations that might have side effects
2. IO actions are recipes for performing IO, executed by the Haskell runtime system
3. do notation provides a convenient syntax for sequencing IO actions
4. Values can be extracted from IO actions using <- within a do block
5. Pure functions can be used inside IO blocks, but their results must be lifted back into IO if needed
6. Every Haskell program has a main :: IO () function as its entry point
Link to original
Monads Basics
Monads are a powerful abstraction in Haskell that provide a structured way to compose computations that may not be pure functions. See also: Common Monads, Monad Laws, Monad Transformers, Functors and Applicatives, Introduction to IO, Error Handling.

The Essence of Monads

A monad represents a computation with a specific context or effect:
- Maybe - Computations that might fail (Common Monads, Error Handling)
- List - Non-deterministic computations with multiple results (Common Monads)
- IO - Computations with side effects (Introduction to IO)
- State - Computations that maintain state (Common Monads)
- And many more…
The key insight is that monads provide a consistent interface for working with these contexts. See Monad Laws for the rules that all monads must follow.

The Monad Typeclass

The Monad typeclass is defined as:
```
class Applicative m => Monad m where
  return :: a -> m a
  (>>=)  :: m a -> (a -> m b) -> m b  -- pronounced "bind"
  (>>)   :: m a -> m b -> m b         -- pronounced "then"
  
  -- Default implementations
  m >> n = m >>= \_ -> n
```
Note: The Applicative constraint is part of the modern definition of the Monad typeclass. For this course, you can focus on return and (>>=). See Functors and Applicatives for more on the relationship between these abstractions.

Core Functions
1. return - Takes a value and wraps it in the monad
2. (>>=) (bind) - Sequences two monadic operations, passing the result of the first to the second
3. (>>) (then) - Sequences two monadic operations, discarding the result of the first
Understanding Bind (>>=)

The bind operator is the heart of monads:
```
(>>=) :: m a -> (a -> m b) -> m b
```
It allows us to:
1. Take a monadic value (m a)
2. Apply a function that takes a normal value and returns a monadic value (a -> m b)
3. Get a new monadic value (m b)
Think of it as “extracting” a value from a context, applying a function, and putting the result back into the context.

Example: The Maybe Monad

The Maybe type represents computations that might fail (Common Monads, Error Handling):
```
data Maybe a = Nothing | Just a
```
Its monad instance:
```
instance Monad Maybe where
  return x = Just x
  
  Nothing >>= _ = Nothing
  (Just x) >>= f = f x
```
This captures the idea that if any computation fails (returns Nothing), the entire sequence fails.

Example with Maybe
```
-- Safe division
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv x y = Just (x `div` y)
 
-- Using bind to chain operations
computation :: Int -> Int -> Int -> Maybe Int
computation x y z = 
  safeDiv x y >>= \result1 ->
  safeDiv result1 z >>= \result2 ->
  return (result2 * 2)
```
If either division fails, the entire computation returns Nothing.

Example: The List Monad

The list monad represents non-deterministic computations (Common Monads):
```
instance Monad [] where
  return x = [x]
  
  xs >>= f = concat (map f xs)
```
This captures the idea of exploring all possible outcomes.

Example with List
```
-- Generate all pairs from two lists
pairs :: [a] -> [b] -> [(a, b)]
pairs xs ys = 
  xs >>= \x ->
  ys >>= \y ->
  return (x, y)
 
-- Usage:
-- pairs [1,2] ['a','b'] == [(1,'a'),(1,'b'),(2,'a'),(2,'b')]
```
do Notation

Haskell provides syntactic sugar called do notation to make working with monads more readable. See Monad Laws for how do notation is translated to uses of >>= and return.
```
computation :: Int -> Int -> Int -> Maybe Int
computation x y z = do
  result1 <- safeDiv x y
  result2 <- safeDiv result1 z
  return (result2 * 2)
```
Translation Rules

do notation is translated to uses of >>= and return:

do notation Translation
do { x <- mx; rest } mx >>= \x -> do { rest }
do { let x = v; rest } let x = v in do { rest }
do { mx; rest } mx >> do { rest }
do { mx } mx

The Identity Monad

The simplest monad is the Identity monad, which adds no computational effects. See Monad Transformers for how this is used as a base for more complex monads.
```
newtype Identity a = Identity { runIdentity :: a }
 
instance Monad Identity where
  return x = Identity x
  
  (Identity x) >>= f = f x
```
It’s useful primarily for understanding monadic concepts and as a base for monad transformers.

Pattern: Building Computations with Monads

Monads allow us to build complex computations by sequencing smaller ones. This works for any monad, whether Maybe, List, IO, etc. (Common Monads, Introduction to IO)
```
complexComputation :: Monad m => m a -> m b -> (a -> b -> m c) -> m c
complexComputation ma mb combine = do
  a <- ma
  b <- mb
  combine a b
```
Using Monads for Different Contexts

Different monads handle different contexts (Common Monads, Error Handling, Introduction to IO).
```
-- Maybe: Handle potential failure
findUser :: UserId -> Maybe User
validateInput :: Input -> Maybe ValidInput
 
process :: UserId -> Input -> Maybe Result
process uid input = do
  user <- findUser uid
  validInput <- validateInput input
  return (computeResult user validInput)
 
-- List: Non-deterministic computation
possibleMoves :: GameState -> [Move]
possibleOutcomes :: GameState -> [GameState]
possibleOutcomes state = do
  move <- possibleMoves state
  return (applyMove state move)
 
-- IO: Sequential side effects
getUserData :: IO UserData
processUserData :: UserData -> IO Result
program :: IO Result
program = do
  userData <- getUserData
  processUserData userData
```
Key Points to Remember
1. A monad represents a computation with a specific context or effect
2. The Monad typeclass defines a consistent interface for these contexts
3. The two key functions are return (wrap a value) and >>= (sequence operations)
4. do notation provides syntactic sugar for monadic operations
5. Different monads handle different kinds of computational contexts
6. The Monad pattern allows for composing complex computations from simpler ones
Link to original

do notation	Translation
`do { x <- mx; rest }`	`mx >>= \x -> do { rest }`
`do { let x = v; rest }`	`let x = v in do { rest }`
`do { mx; rest }`	`mx >> do { rest }`
`do { mx }`	`mx`

Common Monads

This page explores several common monads in Haskell and their practical applications. For a general introduction, see Monads Basics. For laws and properties, see Monad Laws. For combining monads, see Monad Transformers.

Maybe Monad

The Maybe monad represents computations that might fail. See also: Error Handling, Algebraic Data Types.

Definition

data Maybe a = Nothing | Just a
 
instance Monad Maybe where
  return = Just
  
  Nothing >>= _ = Nothing
  (Just x) >>= f = f x

Use Cases

Representing partial functions (those not defined for all inputs)
Error handling without exceptions (Error Handling)
Optional values

Example

-- Safe lookup in a list
safeLookup :: Int -> [a] -> Maybe a
safeLookup _ [] = Nothing
safeLookup 0 (x:_) = Just x
safeLookup n (_:xs) = safeLookup (n-1) xs
 
-- Chain computations with potential failures
lookupAndProcess :: [Int] -> Int -> Maybe Int
lookupAndProcess list idx = do
  value <- safeLookup idx list
  if value > 0
    then Just (value * 2)
    else Nothing

List Monad

The List monad represents non-deterministic computations with multiple possible results. See also: Lists and List Comprehensions, Pattern Matching and Recursion.

Definition

instance Monad [] where
  return x = [x]
  
  xs >>= f = concat (map f xs)

Use Cases

Generating all possible outcomes (Lists and List Comprehensions)
Backtracking algorithms
Combinatorial problems

Example

-- Generate all possible dice rolls
diceRolls :: Int -> [Int]
diceRolls n = do
  -- Roll n dice
  rolls <- replicateM n [1..6]
  -- Return the sum
  return (sum rolls)
 
-- All pythagorean triples with components less than n
pythagoreanTriples :: Int -> [(Int, Int, Int)]
pythagoreanTriples n = do
  a <- [1..n]
  b <- [a..n]  -- Ensure b >= a
  c <- [b..n]  -- Ensure c >= b
  guard (a*a + b*b == c*c)  -- Only keep results that satisfy the equation
  return (a, b, c)

Reader Monad

The Reader monad represents computations that can read values from a shared environment. See also: Higher-Order Functions for the use of functions as first-class values.

Definition

newtype Reader r a = Reader { runReader :: r -> a }
 
instance Monad (Reader r) where
  return x = Reader (\_ -> x)
  
  (Reader f) >>= g = Reader $ \r -> 
                       let a = f r
                           Reader h = g a
                       in h r

Use Cases

Dependency injection
Configuration management
Functions sharing an immutable context

Example

import Control.Monad.Reader
 
-- Configuration data
data Config = Config {
  baseUrl :: String,
  timeout :: Int,
  maxRetries :: Int
}
 
-- Functions using configuration
getResource :: String -> Reader Config String
getResource path = do
  config <- ask  -- Get the environment
  return $ baseUrl config ++ "/" ++ path
 
fetchWithRetry :: String -> Reader Config String
fetchWithRetry resource = do
  path <- getResource resource
  config <- ask
  return $ "Fetching " ++ path ++ 
           " with timeout " ++ show (timeout config) ++ 
           " and " ++ show (maxRetries config) ++ " retries"
 
-- Main program using these functions
program :: Reader Config String
program = do
  result1 <- getResource "users"
  result2 <- fetchWithRetry "data"
  return (result1 ++ "\n" ++ result2)
 
-- Run the program with a specific config
runProgram :: String
runProgram = runReader program (Config "https://api.example.com" 1000 3)

Writer Monad

The Writer monad represents computations that can produce a secondary stream of data (e.g., a log). See also: Pattern Matching and Recursion for recursive logging examples.

Definition

newtype Writer w a = Writer { runWriter :: (a, w) }
 
instance (Monoid w) => Monad (Writer w) where
  return a = Writer (a, mempty)
  
  (Writer (a, w)) >>= f = 
    let (b, w') = runWriter (f a) 
    in Writer (b, w `mappend` w')

Use Cases

Logging
Collecting statistics
Building up strings or other monoid values

Example

import Control.Monad.Writer
 
-- Log messages during computation
factorial :: Int -> Writer [String] Int
factorial n = do
  tell ["Computing factorial of " ++ show n]
  if n <= 1
    then do
      tell ["Factorial of " ++ show n ++ " is 1"]
      return 1
    else do
      res <- factorial (n-1)
      let result = n * res
      tell ["Factorial of " ++ show n ++ " is " ++ show result]
      return result
 
-- Run the computation and get result with logs
computeFactorial :: Int -> (Int, [String])
computeFactorial n = runWriter (factorial n)

State Monad

The State monad represents computations that can maintain and modify state. See also: Pattern Matching and Recursion for recursive stateful algorithms.

Definition

newtype State s a = State { runState :: s -> (a, s) }
 
instance Monad (State s) where
  return a = State $ \s -> (a, s)
  
  (State h) >>= f = State $ \s ->
                      let (a, s') = h s
                          State g = f a
                      in g s'

Use Cases

Stateful algorithms
Passing mutable state through a computation
Random number generation

Example

import Control.Monad.State
 
-- Simple random number generator using state
type RandomState = State Int
 
-- Linear congruential generator parameters
a, c, m :: Int
a = 1103515245
c = 12345
m = 2^31
 
-- Generate a random number and update the seed
nextRandom :: RandomState Int
nextRandom = do
  seed <- get
  let newSeed = (a * seed + c) `mod` m
  put newSeed
  return newSeed
 
-- Generate n random numbers
randomList :: Int -> RandomState [Int]
randomList n = replicateM n nextRandom
 
-- Run with an initial seed
generateRandoms :: Int -> Int -> [Int]
generateRandoms seed count = evalState (randomList count) seed

Either Monad

The Either monad represents computations that might fail with an error value.

Definition

data Either e a = Left e | Right a
 
instance Monad (Either e) where
  return = Right
  
  Left e >>= _ = Left e
  Right a >>= f = f a

Use Cases

Error handling with specific error information
Validation with detailed error messages
Railway-oriented programming

Example

import Control.Monad.Trans.Either
 
-- Error types
data ValidationError = 
    EmptyField String
  | InvalidFormat String
  | OutOfRange String Int Int Int
  deriving Show
 
-- Validation functions
validateName :: String -> Either ValidationError String
validateName "" = Left (EmptyField "Name")
validateName name = Right name
 
validateAge :: Int -> Either ValidationError Int
validateAge age
  | age < 0 = Left (OutOfRange "Age" age 0 120)
  | age > 120 = Left (OutOfRange "Age" age 0 120)
  | otherwise = Right age
 
-- Combined validation
validatePerson :: String -> Int -> Either ValidationError (String, Int)
validatePerson name age = do
  validName <- validateName name
  validAge <- validateAge age
  return (validName, validAge)

IO Monad

The IO monad represents computations that perform input/output operations.

Definition

The implementation is built into the Haskell runtime system.

Use Cases

Reading/writing files
Network operations
Console input/output
Any interaction with the external world

Example

-- Interactive program
interactiveCalculator :: IO ()
interactiveCalculator = do
  putStrLn "Enter the first number:"
  input1 <- getLine
  putStrLn "Enter the second number:"
  input2 <- getLine
  putStrLn "Enter operation (+, -, *, /):"
  op <- getLine
  
  let num1 = read input1 :: Double
      num2 = read input2 :: Double
      result = case op of
        "+" -> num1 + num2
        "-" -> num1 - num2
        "*" -> num1 * num2
        "/" -> num1 / num2
        _   -> error "Invalid operation"
  
  putStrLn $ "Result: " ++ show result
  
  putStrLn "Continue? (y/n)"
  cont <- getLine
  if cont == "y" 
    then interactiveCalculator
    else putStrLn "Goodbye!"

Identity Monad

The Identity monad is the simplest monad, with no additional effects.

Definition

newtype Identity a = Identity { runIdentity :: a }
 
instance Monad Identity where
  return = Identity
  
  Identity x >>= f = f x

Use Cases

Understanding monadic concepts
Base case for monad transformers
Pure computations requiring a monadic interface

Example

import Control.Monad.Identity
 
-- Pure computation in a monadic style
factorial :: Int -> Identity Int
factorial n = do
  if n <= 1
    then return 1
    else do
      res <- factorial (n-1)
      return (n * res)
 
-- Run the computation
computeFactorial :: Int -> Int
computeFactorial n = runIdentity (factorial n)

Combining Monads

Different monads solve different problems, but we often need to combine their capabilities. This is where monad transformers come in (covered in a separate page).

Key Points to Remember

Maybe represents computations that might fail
List represents non-deterministic computations with multiple results
Reader provides read-only access to shared environment
Writer allows accumulating a secondary value (like a log)
State enables maintaining and modifying state throughout a computation
Either is like Maybe but with detailed error information
IO handles side effects and interaction with the external world
Identity is the simplest monad with no additional effects

Link to original

Monad Laws
For a type to be a proper monad, it must satisfy three laws that ensure it behaves consistently and predictably. These laws are mathematical properties that should hold for any monad implementation. See also: Monads Basics, Common Monads, Monad Transformers, Equational Reasoning.

The Three Monad Laws

1. Left Identity
```
return a >>= f = f a
```
This law states that if we take a value, wrap it in a monad using return, and then feed it to a function using >>=, the result should be the same as just applying the function directly to the value. For more on return and >>=, see Monads Basics.

Intuition

return is a “neutral” way to inject a value into a monad. It shouldn’t add any computational effect or change the value. So using return and then immediately extracting the value with >>= should be equivalent to not using the monad at all.

Example with Maybe
```
return 5 >>= (\x -> Just (x + 3))
-- is the same as
(\x -> Just (x + 3)) 5
-- Both evaluate to Just 8
```
2. Right Identity
```
m >>= return = m
```
This law states that if we have a monadic value and we feed its result to return using >>=, we should get back the original monadic value.

Intuition

Since return simply injects a value into the monad without adding any effects, taking a monadic value, extracting its core value, and then reinjecting it with return should give us back what we started with.

Example with List
```
[1, 2, 3] >>= return
-- is the same as
[1, 2, 3]
```
3. Associativity
```
(m >>= f) >>= g = m >>= (\x -> f x >>= g)
```
This law states that the order of application doesn’t matter when chaining monadic operations. Whether we first apply f to m and then apply g to the result, or we define a new function that applies f and then g, and apply that to m, the result should be the same. See Monads Basics for how this relates to do notation.

Intuition

This ensures that when we chain monadic operations, we can group them however we want without affecting the result. This is essential for building complex computations out of simpler ones in a modular way.

Example with IO
```
-- These two expressions are equivalent:
(getLine >>= readFile) >>= putStrLn
getLine >>= (\filename -> readFile filename >>= putStrLn)
```
Verifying the Laws for Specific Monads

Let’s verify the monad laws for a few common monads to better understand them. See Common Monads for more on these types.

Maybe Monad

The Maybe monad is defined as:
```
instance Monad Maybe where
  return = Just
 
  Nothing >>= _ = Nothing
  (Just x) >>= f = f x
```
Left Identity
```
return a >>= f
= Just a >>= f
= f a
```
Right Identity
```
m >>= return
```
For m = Nothing:
```
Nothing >>= return
= Nothing
```
For m = Just a:
```
Just a >>= return
= return a
= Just a
```
Associativity
```
(m >>= f) >>= g
```
For m = Nothing:
```
(Nothing >>= f) >>= g
= Nothing >>= g
= Nothing
 
Nothing >>= (\x -> f x >>= g)
= Nothing
```
For m = Just a:
```
(Just a >>= f) >>= g
= f a >>= g
 
Just a >>= (\x -> f x >>= g)
= (\x -> f x >>= g) a
= f a >>= g
```
List Monad

The List monad is defined as:
```
instance Monad [] where
  return x = [x]
  
  xs >>= f = concat (map f xs)
```
Left Identity
```
return a >>= f
= [a] >>= f
= concat (map f [a])
= concat [f a]
= f a
```
Right Identity
```
xs >>= return
= concat (map return xs)
= concat (map (\x -> [x]) xs)
= concat [[x] | x <- xs]
= xs
```
Associativity

The proof is more involved, but it relies on the associativity of concat and the distributivity of map over concat.

Why the Monad Laws Matter

The monad laws ensure that:
1. Consistency: Monads behave in a consistent, predictable way
2. Equational Reasoning: We can reason about monadic code using substitution (Equational Reasoning)
3. Refactoring: Code can be refactored without changing behavior
4. Composability: Monadic operations can be composed in any order (Monads Basics)
5. Do-Notation: The translation of do notation relies on these laws (Monads Basics)
Consequences of Breaking the Laws

If a monad implementation breaks these laws:
1. Code using that monad might behave unexpectedly
2. Refactoring could change the behavior of the code
3. The do notation might not work as expected
4. Composition with other monadic operations might be inconsistent
Practical Implications

For do Notation

The translation of do notation to >>= relies on the monad laws. For example:
```
do
  a <- ma
  b <- mb
  return (a, b)
```
This translates to:
```
ma >>= (\a -> 
  mb >>= (\b -> 
    return (a, b)))
```
The associativity law ensures that this is equivalent to:
```
(ma >>= (\a -> mb)) >>= (\b -> return (a, b))
```
For Monad Transformers

Monad transformers combine the effects of multiple monads. The monad laws ensure that these combinations behave reasonably.

For Library Design

When designing a library that uses monads, adhering to the monad laws ensures that users can reason about your library’s behavior and combine it with other monadic code.

Testing the Monad Laws

You can use property-based testing with QuickCheck to verify that your monad implementation satisfies the laws:
```
import Test.QuickCheck
 
-- For a custom monad MyMonad
prop_leftIdentity :: (Eq (m b), Monad m) => a -> (a -> m b) -> Bool
prop_leftIdentity a f = (return a >>= f) == f a
 
prop_rightIdentity :: (Eq (m a), Monad m) => m a -> Bool
prop_rightIdentity m = (m >>= return) == m
 
prop_associativity :: (Eq (m c), Monad m) => m a -> (a -> m b) -> (b -> m c) -> Bool
prop_associativity m f g = ((m >>= f) >>= g) == (m >>= (\x -> f x >>= g))
```
Key Points to Remember
1. The three monad laws are left identity, right identity, and associativity
2. These laws ensure consistent and predictable behavior when using monads
3. All proper monad implementations must satisfy these laws
4. The laws are not enforced by the type system - it’s the developer’s responsibility
5. The laws are essential for reasoning about monadic code and for the correct functioning of do notation
Link to original

Parser Combinators

Parser combinators are a functional approach to parsing where complex parsers are built by combining simpler ones. They’re a powerful application of monads in Haskell (Monads Basics, Common Monads, Monad Laws).

What are Parser Combinators?

A parser is a function that takes some input (typically a string) and produces a structured result. Parser combinators are higher-order functions (Higher-Order Functions) that take parsers as input and return new parsers.

The key insight is that we can:

Create primitive parsers for basic elements
Combine them to create more complex parsers
Use the monadic structure to sequence parsing operations (Monads Basics)

The Parsec Library

Parsec is the most common parser combinator library in Haskell. Let’s look at its core concepts.

Installation

cabal install --lib parsec

Basic Types

In Parsec, the primary type is:

type Parser a = Parsec String () a

which means a parser that consumes a String input, uses () as a custom state, and produces a value of type a.

Simple Parsers

Parsec provides many primitive parsers:

import Text.Parsec
import Text.Parsec.String (Parser)
 
-- Parse a single character
charParser :: Parser Char
charParser = char 'c'
 
-- Parse any digit
digitParser :: Parser Char
digitParser = digit
 
-- Parse a specific string
helloParser :: Parser String
helloParser = string "hello"

Running Parsers

To run a parser on an input string:

parse :: Parsec s u a -> SourceName -> s -> Either ParseError a

Examples:

parse charParser "input" "cat"  -- Right 'c'
parse charParser "input" "dog"  -- Left "unexpected 'd'"
 
parseTest :: Show a => Parsec s u a -> s -> IO ()
parseTest charParser "cat"  -- 'c'

Combining Parsers

The power of parser combinators comes from combining simpler parsers into more complex ones. This is a direct application of higher-order functions (Higher-Order Functions) and monadic sequencing (Monads Basics).

Sequencing Parsers

To parse one thing followed by another, we use monadic do notation (Monads Basics):

-- Parse "hello" followed by "world"
helloWorldParser :: Parser (String, String)
helloWorldParser = do
  hello <- string "hello"
  space
  world <- string "world"
  return (hello, world)

Alternatives

To try one parser, and if it fails, try another, we use the <|> operator from the Alternative typeclass (Functors and Applicatives):

-- Parse either "cat" or "dog"
animalParser :: Parser String
animalParser = try (string "cat") <|> string "dog"

The <|> operator comes from the Alternative typeclass and represents choice.

Repetition

To parse something multiple times:

-- Parse zero or more digits
digitsParser :: Parser String
digitsParser = many digit
 
-- Parse one or more digits
digitsParser1 :: Parser String
digitsParser1 = many1 digit

Building Complex Parsers

Let’s build a more complex parser for a simple arithmetic expression. This example uses recursive data types (Algebraic Data Types) and pattern matching (Pattern Matching and Recursion).

import Text.Parsec
import Text.Parsec.String (Parser)
import qualified Text.Parsec.Expr as E
import Text.Parsec.Token (GenLanguageDef(..), makeTokenParser)
import qualified Text.Parsec.Token as Token
 
-- Define the language
def :: GenLanguageDef String () Identity
def = LanguageDef
  { commentStart = "/*"
  , commentEnd = "*/"
  , commentLine = "//"
  , nestedComments = True
  , identStart = letter
  , identLetter = alphaNum <|> char '_'
  , opStart = oneOf "+-*/="
  , opLetter = oneOf "+-*/="
  , reservedNames = ["if", "then", "else", "while", "do", "end"]
  , reservedOpNames = ["+", "-", "*", "/", "="]
  , caseSensitive = True
  }
 
-- Create a token parser
tokenParser = makeTokenParser def
 
-- Extract useful parsers
identifier = Token.identifier tokenParser
reserved = Token.reserved tokenParser
reservedOp = Token.reservedOp tokenParser
parens = Token.parens tokenParser
integer = Token.integer tokenParser
whiteSpace = Token.whiteSpace tokenParser
 
-- Expression parser
expr :: Parser Integer
expr = E.buildExpressionParser table term
  where
    term = parens expr <|> integer
    table = [ [binary "*" (*) E.AssocLeft, binary "/" div E.AssocLeft]
            , [binary "+" (+) E.AssocLeft, binary "-" (-) E.AssocLeft]
            ]
    binary name fun assoc = E.Infix (reservedOp name >> return fun) assoc
 
-- Parse and evaluate an expression
parseExpr :: String -> Either ParseError Integer
parseExpr input = parse (whiteSpace >> expr) "" input

Building a Parse Tree

Often, we want to build a structured representation of the input rather than evaluating it directly. This is a classic use of algebraic data types (Algebraic Data Types) and recursion (Pattern Matching and Recursion).

-- Data type for arithmetic expressions
data Expr = Lit Integer
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          deriving (Show)
 
-- Parser for a parse tree
exprTree :: Parser Expr
exprTree = E.buildExpressionParser table term
  where
    term = parens exprTree <|> (Lit <$> integer)
    table = [ [binary "*" Mul E.AssocLeft, binary "/" Div E.AssocLeft]
            , [binary "+" Add E.AssocLeft, binary "-" Sub E.AssocLeft]
            ]
    binary name constructor assoc = 
      E.Infix (reservedOp name >> return constructor) assoc
 
-- After parsing, we can evaluate or transform the parse tree
eval :: Expr -> Integer
eval (Lit n) = n
eval (Add e1 e2) = eval e1 + eval e2
eval (Sub e1 e2) = eval e1 - eval e2
eval (Mul e1 e2) = eval e1 * eval e2
eval (Div e1 e2) = eval e1 `div` eval e2

Common Parser Combinators

Basic Parsers

char :: Char -> Parser Char           -- Parse a specific character
string :: String -> Parser String     -- Parse a specific string
anyChar :: Parser Char                -- Parse any character
letter :: Parser Char                 -- Parse a letter
digit :: Parser Char                  -- Parse a digit
alphaNum :: Parser Char              -- Parse a letter or digit
space :: Parser Char                 -- Parse a space character
spaces :: Parser ()                  -- Parse zero or more spaces

Combinators

(<|>) :: Parser a -> Parser a -> Parser a  -- Choice between parsers
try :: Parser a -> Parser a                -- Backtracking
many :: Parser a -> Parser [a]             -- Zero or more occurrences
many1 :: Parser a -> Parser [a]            -- One or more occurrences
option :: a -> Parser a -> Parser a        -- Optional parser with default
optional :: Parser a -> Parser ()          -- Optional parser, discarding result
between :: Parser open -> Parser close -> Parser a -> Parser a  -- Brackets
sepBy :: Parser a -> Parser sep -> Parser [a]      -- Separated list
sepBy1 :: Parser a -> Parser sep -> Parser [a]     -- Non-empty separated list
endBy :: Parser a -> Parser sep -> Parser [a]      -- List ending with separator
chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a  -- Left-associative chain

Handling Parse Errors

Parsec provides detailed error messages when parsing fails:

parse expr "" "1 + (2 * 3"
-- Left (line 1, column 10):
-- unexpected end of input
-- expecting ")" or digit

You can customize error messages using the <??> operator:

expr' = expr <?> "expression"

Common Patterns

Lexing and Parsing

For complex languages, it’s common to separate lexical analysis (tokenization) from parsing:

-- Lexer (converts string to tokens)
lexer :: Parser [Token]
lexer = many (space *> token <* spaces)
 
-- Parser (converts tokens to AST)
parser :: [Token] -> Either ParseError AST

Recursive Parsers

For recursive structures like expressions, we need to handle precedence and associativity:

-- Manual approach (without buildExpressionParser)
expr = term `chainl1` addOp
term = factor `chainl1` mulOp
factor = parens expr <|> integer
addOp = (reservedOp "+" >> return Add) <|> (reservedOp "-" >> return Sub)
mulOp = (reservedOp "*" >> return Mul) <|> (reservedOp "/" >> return Div)

Consumed Input

When dealing with ambiguous grammars, it’s important to use try to backtrack when a parser fails after consuming input:

-- Without try, this would fail if "let" is found but not followed by a valid definition
letExpr = try (do
  reserved "let"
  name <- identifier
  reservedOp "="
  value <- expr
  reserved "in"
  body <- expr
  return (Let name value body)
) <|> otherExpr

Practical Example: A JSON Parser

Here’s a simple JSON parser using Parsec:

import Text.Parsec
import Text.Parsec.String (Parser)
import Control.Applicative ((<$>), (<*>), (*>), (<*))
import Data.Char (digitToInt)
 
data JSON = JNull
          | JBool Bool
          | JNum Double
          | JStr String
          | JArr [JSON]
          | JObj [(String, JSON)]
          deriving (Show, Eq)
 
-- Whitespace
spaces :: Parser ()
spaces = skipMany (oneOf " \t\n\r")
 
-- JSON null
jNull :: Parser JSON
jNull = string "null" *> return JNull
 
-- JSON boolean
jBool :: Parser JSON
jBool = JBool <$> (true <|> false)
  where true = string "true" *> return True
        false = string "false" *> return False
 
-- JSON number
jNum :: Parser JSON
jNum = JNum <$> (do
  s <- option 1 (char '-' *> return (-1))
  n <- number
  return (s * n))
  where
    number = do
      i <- integer
      f <- option 0 fraction
      e <- option 0 exponent
      return ((fromIntegral i + f) * (10 ** e))
    integer = do
      first <- digit
      rest <- many digit
      return (read (first:rest))
    fraction = do
      char '.'
      digits <- many1 digit
      let f = read digits :: Integer
          l = fromIntegral (length digits)
      return (fromIntegral f / (10 ^ l))
    exponent = do
      e <- oneOf "eE"
      sign <- option 1 (char '+' *> return 1 <|> char '-' *> return (-1))
      digits <- many1 digit
      return (sign * (read digits))
 
-- JSON string
jStr :: Parser JSON
jStr = JStr <$> (char '"' *> many charParser <* char '"')
  where
    charParser = escapedChar <|> normalChar
    normalChar = noneOf "\\\"\n\r\t"
    escapedChar = char '\\' *> (
      char '"' <|> 
      char '\\' <|> 
      char '/' <|> 
      (char 'b' *> return '\b') <|>
      (char 'f' *> return '\f') <|>
      (char 'n' *> return '\n') <|>
      (char 'r' *> return '\r') <|>
      (char 't' *> return '\t'))
 
-- JSON array
jArr :: Parser JSON
jArr = JArr <$> (char '[' *> spaces *> elements <* spaces <* char ']')
  where
    elements = sepBy (spaces *> jsonParser <* spaces) (char ',')
 
-- JSON object
jObj :: Parser JSON
jObj = JObj <$> (char '{' *> spaces *> pairs <* spaces <* char '}')
  where
    pairs = sepBy pair (spaces *> char ',' <* spaces)
    pair = do
      key <- jStr
      spaces *> char ':' *> spaces
      value <- jsonParser
      case key of
        JStr k -> return (k, value)
        _ -> fail "Expected string key in object"
 
-- Main JSON parser
jsonParser :: Parser JSON
jsonParser = jNull <|> jBool <|> jNum <|> jStr <|> jArr <|> jObj
 
-- Parse JSON from a string
parseJSON :: String -> Either ParseError JSON
parseJSON = parse (spaces *> jsonParser <* spaces <* eof) ""

Key Points to Remember

Parser combinators allow you to build complex parsers by combining simpler ones
Parsec is a popular parser combinator library in Haskell
Parsers are monadic, allowing for clean sequencing of parsing operations
The <|> operator provides alternatives when parsing
Common combinators include many, many1, sepBy, and between
Recursive parsers can handle nested structures like expressions
Parser combinators provide a declarative, composable approach to parsing

Link to original

Advanced Concepts

Error Handling

Error handling in Haskell differs significantly from exception-based approaches in imperative languages. Haskell provides several approaches that align with its functional nature and type system.

Types of Errors in Haskell

Compile-time errors: Type errors, syntax errors, etc.
Runtime errors: Exceptions that occur during program execution
Expected failures: Situations where operations might legitimately fail

This page focuses on handling the last two categories.

Approaches to Error Handling

1. Maybe Type

The Maybe type represents computations that might fail:

data Maybe a = Nothing | Just a

Use Cases

Partial functions (not defined for all inputs)
Functions that could fail without needing detailed error information

Example

safeDivide :: Int -> Int -> Maybe Int
safeDivide _ 0 = Nothing
safeDivide x y = Just (x `div` y)
 
-- Usage
case safeDivide 10 0 of
  Nothing -> putStrLn "Division by zero!"
  Just result -> putStrLn $ "Result: " ++ show result

Working with Multiple Maybe Values

-- Using do notation
computeAverage :: [Int] -> Maybe Double
computeAverage xs = do
  if null xs
    then Nothing
    else Just (fromIntegral (sum xs) / fromIntegral (length xs))
 
-- Using monadic functions
findUserAvgScore :: UserId -> [ScoreId] -> Maybe Double
findUserAvgScore uid scoreIds = do
  user <- findUser uid
  scores <- mapM (getScore user) scoreIds
  return (average scores)

2. Either Type

The Either type provides more detailed error information:

data Either a b = Left a | Right b

By convention, Left contains error information and Right contains successful results.

Use Cases

When you need specific error information
Validation that needs to report why it failed
Functions with multiple failure modes

Example

data DivideError = DivideByZero | OverflowError
 
safeDivide :: Int -> Int -> Either DivideError Int
safeDivide _ 0 = Left DivideByZero
safeDivide x y
  | x > maxBound `div` y = Left OverflowError
  | otherwise = Right (x `div` y)
 
-- Usage
case safeDivide 10 0 of
  Left DivideByZero -> putStrLn "Cannot divide by zero!"
  Left OverflowError -> putStrLn "Overflow would occur!"
  Right result -> putStrLn $ "Result: " ++ show result

Working with Multiple Either Values

-- Using do notation
validatePerson :: String -> Int -> Either String Person
validatePerson name age = do
  validName <- validateName name
  validAge <- validateAge age
  Right (Person validName validAge)
  where
    validateName "" = Left "Name cannot be empty"
    validateName n = Right n
    validateAge a
      | a < 0 = Left "Age cannot be negative"
      | a > 120 = Left "Age is unrealistic"
      | otherwise = Right a

3. ExceptT Monad Transformer

ExceptT combines the Either type with another monad (often IO):

newtype ExceptT e m a = ExceptT { runExceptT :: m (Either e a) }

Use Cases

Handling errors in code that also performs IO or other monadic operations
Creating a clean separation of error handling from other effects
Building complex functions that can fail at multiple points

Example

import Control.Monad.Except
 
type AppError = String
type App a = ExceptT AppError IO a
 
readConfig :: FilePath -> App Config
readConfig path = do
  exists <- liftIO $ doesFileExist path
  unless exists $ 
    throwError $ "Config file not found: " ++ path
  content <- liftIO $ readFile path
  case parseConfig content of
    Nothing -> throwError "Invalid config format"
    Just config -> return config
 
runApp :: App a -> IO (Either AppError a)
runApp = runExceptT

4. Runtime Exceptions

Haskell has a system for runtime exceptions, but it’s generally avoided in favor of explicit error types:

-- Generating exceptions
error :: String -> a
undefined :: a
 
-- Catching exceptions
catch :: Exception e => IO a -> (e -> IO a) -> IO a
try :: Exception e => IO a -> IO (Either e a)

Example

import Control.Exception
 
-- Catching exceptions
readFileContent :: FilePath -> IO String
readFileContent path = readFile path `catch` handleError
  where
    handleError :: IOException -> IO String
    handleError e = return $ "Error reading file: " ++ show e
 
-- Using try
readFileContent' :: FilePath -> IO (Either IOException String)
readFileContent' path = try (readFile path)

5. Custom Exceptions

You can define custom exception types:

import Control.Exception
 
data AppException = ConfigError String
                  | DatabaseError String
                  | NetworkError String
                  deriving (Show, Typeable)
 
instance Exception AppException
 
-- Throwing custom exceptions
throwConfigError :: String -> IO a
throwConfigError msg = throwIO (ConfigError msg)
 
-- Catching specific exception types
catchAppExceptions :: IO a -> IO a
catchAppExceptions action = action `catches` 
  [ Handler (\(e :: ConfigError) -> handleConfigError e)
  , Handler (\(e :: DatabaseError) -> handleDatabaseError e)
  , Handler (\(e :: SomeException) -> handleOtherExceptions e)
  ]

Validation: Collecting Multiple Errors

Sometimes you want to report all errors rather than just the first one:

import Data.Validation
 
data ValidationError = NameTooShort
                     | AgeTooLow
                     | InvalidEmail
                     deriving (Show)
 
validatePerson :: String -> Int -> String -> Validation [ValidationError] Person
validatePerson name age email =
  Person <$> validateName name <*> validateAge age <*> validateEmail email
  where
    validateName n
      | length n < 2 = Failure [NameTooShort]
      | otherwise = Success n
      
    validateAge a
      | a < 18 = Failure [AgeTooLow]
      | otherwise = Success a
      
    validateEmail e
      | not (isValidEmail e) = Failure [InvalidEmail]
      | otherwise = Success e

Error Handling Patterns

Defensive Programming

processData :: Maybe Data -> Either Error Result
processData Nothing = Left (MissingData "No data provided")
processData (Just d)
  | isValid d = Right (computeResult d)
  | otherwise = Left (InvalidData "Data is invalid")

Railway-Oriented Programming

Thinking of functions as “tracks” where success follows one track and failure another:

validateInput :: Input -> Either Error ValidInput
transformData :: ValidInput -> Either Error TransformedData
computeOutput :: TransformedData -> Either Error Output
 
processInput :: Input -> Either Error Output
processInput input = do
  validInput <- validateInput input
  transformedData <- transformData validInput
  computeOutput transformedData

Error Handling with Monads

Using monadic functions for cleaner error handling:

-- mapM for processing lists with potential failures
processItems :: [Item] -> Either Error [Result]
processItems = mapM processItem
 
-- filterM for filtering with side effects
getValidItems :: [Item] -> IO [Item]
getValidItems = filterM isValid
 
-- Using forM_ for actions that might fail
processAllItems :: [Item] -> Either Error ()
processAllItems items = forM_ items $ \item -> do
  result <- processItem item
  storeResult result

Best Practices

Use the simplest mechanism that meets your needs:
- For simple absence/presence of a value, use Maybe
- For error details, use Either
- For more complex requirements, consider monad transformers

Make error types informative:

data UserError = UserNotFound UserId
               | InvalidPassword
               | AccountLocked DateTime

Return errors, don’t throw exceptions in pure code:

-- Good
lookup :: Key -> Map Key Value -> Maybe Value
 
-- Avoid
lookup :: Key -> Map Key Value -> Value
lookup k m = case Map.lookup k m of
  Just v  -> v
  Nothing -> error "Key not found"

Handle all cases explicitly:

processResult :: Either Error Value -> String
processResult (Right value) = "Success: " ++ show value
processResult (Left (InputError msg)) = "Input error: " ++ msg
processResult (Left (SystemError code)) = "System error: " ++ show code
processResult (Left (OtherError e)) = "Other error: " ++ show e

Compose error-handling functions using monads:

validateAndProcess :: Input -> Either Error Output
validateAndProcess = validate >=> process >=> format

Key Points to Remember

Haskell favors explicit error handling using types like Maybe and Either
Exceptions in Haskell are primarily for exceptional conditions, not regular error handling
Monadic composition makes it easy to chain operations that might fail
Custom error types help make error handling more informative and type-safe
For IO operations, consider using ExceptT to combine IO with structured error handling

Link to original

Monad Transformers
Monad transformers are a way to combine multiple monads to create a composite monad that has the features of all the component monads.

The Problem: Combining Monads

Different monads provide different computational effects:

Maybe - Computations that might fail

Either e - Computations that might fail with an error of type e

Reader r - Computations with read-only access to an environment of type r

State s - Computations with mutable state of type s

IO - Computations with side effects

But what if we need multiple effects? For example:

A computation that needs access to configuration AND might fail

A computation that maintains state AND performs IO operations

We can’t easily compose monads directly. If we have functions:
f :: a -> Maybe b
g :: b -> State s c
There’s no general way to compose them to get a function a -> SomeCombinedMonad c.

Monad Transformers: The Solution

Monad transformers are special types that add capabilities of one monad to another monad.

Key transformer types include:

MaybeT m a - Adds Maybe’s failure handling to monad m

ExceptT e m a - Adds Either e’s error handling to monad m

ReaderT r m a - Adds Reader r’s environment access to monad m

StateT s m a - Adds State s’s state manipulation to monad m

WriterT w m a - Adds Writer w’s logging to monad m

The MonadTrans Typeclass

The MonadTrans typeclass defines how to lift operations from the base monad into the transformer:
class MonadTrans t where
  lift :: (Monad m) => m a -> t m a
This allows operations from the inner monad to be used in the context of the transformer.

Common Monad Transformers

MaybeT

Adds optional values to any monad:
newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }
 
instance (Monad m) => Monad (MaybeT m) where
  return = MaybeT . return . Just
  
  x >>= f = MaybeT $ do
    v <- runMaybeT x
    case v of
      Nothing -> return Nothing
      Just y -> runMaybeT (f y)
 
instance MonadTrans MaybeT where
  lift = MaybeT . fmap Just
Example
import Control.Monad.Trans.Maybe
import Control.Monad.Trans.Class
 
findUser :: UserId -> MaybeT IO User
findUser uid = do
  mUser <- lift $ queryDatabase uid
  case mUser of
    Nothing -> MaybeT $ return Nothing
    Just user -> return user
 
getUserSettings :: User -> MaybeT IO Settings
getUserSettings user = do
  mSettings <- lift $ fetchSettings (userId user)
  MaybeT $ return mSettings
 
userProgram :: UserId -> IO (Maybe Settings)
userProgram uid = runMaybeT $ do
  user <- findUser uid
  getUserSettings user
ExceptT

Adds error handling to any monad:
newtype ExceptT e m a = ExceptT { runExceptT :: m (Either e a) }
Example
import Control.Monad.Trans.Except
import Control.Monad.Trans.Class
 
data AppError = NotFound | PermissionDenied | ServerError String
  deriving Show
 
type AppM a = ExceptT AppError IO a
 
findDocument :: DocId -> AppM Document
findDocument docId = do
  mDoc <- lift $ queryDatabase docId
  case mDoc of
    Nothing -> throwE NotFound
    Just doc -> return doc
 
checkPermission :: UserId -> Document -> AppM ()
checkPermission userId doc = do
  hasPermission <- lift $ checkUserPermission userId doc
  unless hasPermission $ throwE PermissionDenied
 
processDocument :: UserId -> DocId -> IO (Either AppError ProcessedDoc)
processDocument userId docId = runExceptT $ do
  doc <- findDocument docId
  checkPermission userId doc
  lift $ processDoc doc
ReaderT

Adds read-only environment to any monad:
newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a }
Example
import Control.Monad.Reader
import Control.Monad.Trans.Class
 
data Config = Config {
  apiUrl :: String,
  timeout :: Int,
  maxRetries :: Int
}
 
type AppM a = ReaderT Config IO a
 
fetchData :: Endpoint -> AppM Data
fetchData endpoint = do
  config <- ask
  let url = apiUrl config ++ endpoint
      to = timeout config
  lift $ httpGet url to
 
retryOperation :: AppM a -> AppM a
retryOperation operation = do
  config <- ask
  lift $ withRetry (maxRetries config) (runReaderT operation config)
 
appMain :: Config -> IO Result
appMain config = runReaderT program config
  where 
    program = do
      userData <- fetchData "/users"
      productData <- fetchData "/products"
      return (processResults userData productData)
StateT

Adds mutable state to any monad:
newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }
Example
import Control.Monad.State
import Control.Monad.Trans.Class
 
type GameState = (Player, World)
type GameM a = StateT GameState IO a
 
movePlayer :: Direction -> GameM ()
movePlayer dir = do
  (player, world) <- get
  let newPlayer = updatePosition player dir
  if isValidPosition world newPlayer
    then put (newPlayer, world)
    else return ()
 
interactWithObject :: GameM ()
interactWithObject = do
  (player, world) <- get
  case objectAt world (playerPosition player) of
    Nothing -> lift $ putStrLn "Nothing here."
    Just obj -> do
      lift $ putStrLn $ "Interacting with " ++ show obj
      let (newWorld, message) = interact world obj
      put (player, newWorld)
      lift $ putStrLn message
 
gameLoop :: GameM ()
gameLoop = do
  (player, _) <- get
  if playerHealth player <= 0
    then lift $ putStrLn "Game over!"
    else do
      cmd <- lift getCommand
      executeCommand cmd
      gameLoop
 
runGame :: GameState -> IO ()
runGame initialState = evalStateT gameLoop initialState
Transformer Stacks

Monad transformers can be stacked to combine multiple effects:
type AppM a = ExceptT AppError (ReaderT Config (StateT AppState IO)) a
This gives us a monad with:

Error handling (ExceptT)

Configuration access (ReaderT)

Mutable application state (StateT)

IO capabilities (IO)

Running a Transformer Stack

To run a monad transformer stack, you apply the “run” functions from outside in:
runApp :: Config -> AppState -> AppM a -> IO (Either AppError a, AppState)
runApp config state action = 
  runStateT (runReaderT (runExceptT action) config) state
Example: Complex Stack
{-# LANGUAGE FlexibleContexts #-}
import Control.Monad.Reader
import Control.Monad.State
import Control.Monad.Except
import Control.Monad.Writer
 
data AppConfig = AppConfig { ... }
data AppState = AppState { ... }
data AppError = AppError { ... }
type Log = [String]
 
type AppM a = ExceptT AppError (ReaderT AppConfig (StateT AppState (WriterT Log IO))) a
 
-- Access config
getConfig :: MonadReader AppConfig m => m AppConfig
getConfig = ask
 
-- Access/modify state
getState :: MonadState AppState m => m AppState
getState = get
 
updateState :: MonadState AppState m => (AppState -> AppState) -> m ()
updateState = modify
 
-- Error handling
throwAppError :: MonadError AppError m => AppError -> m a
throwAppError = throwError
 
-- Logging
logInfo :: MonadWriter Log m => String -> m ()
logInfo msg = tell [msg]
 
-- IO operations
liftIOOperation :: MonadIO m => IO a -> m a
liftIOOperation = liftIO
 
-- Running the application
runApp :: AppConfig -> AppState -> AppM a -> IO (((Either AppError a, AppState), Log))
runApp config state app = 
  runWriterT (runStateT (runReaderT (runExceptT app) config) state)
Lifting Through Transformer Stacks

When working with transformer stacks, you often need to lift operations:
-- Lift from innermost monad to transformer stack
liftIO :: MonadIO m => IO a -> m a
 
-- Lifting through a stack requires multiple lifts
liftMaybeIO :: MaybeT (StateT s IO) a -> ExceptT e (ReaderT r (StateT s IO)) a
liftMaybeIO = lift . lift . lift . except . maybe (Left defaultError) Right . runMaybeT
Type Classes for Lifting

The mtl library provides typeclasses for different monad capabilities:
class Monad m => MonadReader r m | m -> r where
  ask :: m r
  local :: (r -> r) -> m a -> m a
 
class Monad m => MonadState s m | m -> s where
  get :: m s
  put :: s -> m ()
 
class Monad m => MonadError e m | m -> e where
  throwError :: e -> m a
  catchError :: m a -> (e -> m a) -> m a
 
class Monad m => MonadWriter w m | m -> w where
  tell :: w -> m ()
  listen :: m a -> m (a, w)
  pass :: m (a, w -> w) -> m a
These typeclasses make it easier to write code that works with any transformer stack that has the required capabilities.

Common Patterns with Monad Transformers

The ReaderT IO Pattern

The ReaderT env IO monad is a common pattern for applications:
newtype App a = App { unApp :: ReaderT Env IO a }
  deriving (Functor, Applicative, Monad, MonadReader Env, MonadIO)
 
-- All functions can access the environment
getConfig :: App Config
getConfig = asks envConfig
 
-- Lift IO operations
logMessage :: String -> App ()
logMessage msg = do
  logger <- asks envLogger
  liftIO $ logger msg
 
-- Run the application
runApp :: Env -> App a -> IO a
runApp env app = runReaderT (unApp app) env
Error Handling with ExceptT

Adding error handling with ExceptT:
type App a = ExceptT AppError (ReaderT Env IO) a
 
-- Now we can throw and catch errors
saveDocument :: Document -> App ()
saveDocument doc = do
  db <- asks envDatabase
  result <- liftIO $ tryIOError $ writeToDatabase db doc
  case result of
    Left e -> throwError (DatabaseError e)
    Right _ -> return ()
 
-- Run with error handling
runApp :: Env -> App a -> IO (Either AppError a)
runApp env app = runReaderT (runExceptT app) env
State with StateT

Adding state management:
type App a = StateT AppState (ReaderT Env (ExceptT AppError IO)) a
 
-- Update state based on external operations
processTransaction :: Transaction -> App Balance
processTransaction tx = do
  AppState {balance} <- get
  let newBalance = updateBalance balance tx
  if newBalance < 0
    then throwError InsufficientFunds
    else do
      modify $ \s -> s {balance = newBalance}
      return newBalance
 
-- Run with state
runApp :: Env -> AppState -> App a -> IO (Either AppError (a, AppState))
runApp env state app = runExceptT $ runReaderT (runStateT app state) env
Monad Transformer Best Practices

1. Keep the Stack Simple

Don’t add transformers you don’t need. A common stack is:
type App a = ExceptT AppError (ReaderT Env IO) a
This gives you:

Error handling (ExceptT)

Environment access (ReaderT)

IO capabilities (IO)

2. Use Type Classes

Instead of directly referencing your transformer stack, use typeclasses:
-- Instead of this:
fetchUser :: UserId -> ExceptT Error (ReaderT Env IO) User
 
-- Prefer this:
fetchUser :: (MonadReader Env m, MonadError Error m, MonadIO m) => UserId -> m User
This makes your code more reusable and easier to test.

3. Define Helper Functions

Create helpers for common operations:
throwDbError :: MonadError AppError m => DbError -> m a
throwDbError = throwError . DatabaseError
 
withTransaction :: (MonadReader Env m, MonadError AppError m, MonadIO m) => (Connection -> IO a) -> m a
withTransaction action = do
  conn <- asks envDbConnection
  result <- liftIO $ try $ withDbTransaction conn action
  either throwDbError return result
4. Use Newtypes for Your App Monad
newtype App a = App { runApp :: ExceptT AppError (ReaderT Env IO) a }
  deriving (Functor, Applicative, Monad, MonadReader Env, MonadError AppError, MonadIO)
This gives you better type safety and lets you define custom instances.

5. Consider Performance

Monad transformers can introduce overhead. For performance-critical applications, consider alternatives like the RIO or ReaderT IO patterns.

Key Points to Remember

Monad transformers let you combine multiple monadic effects

Each transformer adds a specific capability (error handling, state, etc.)

Use lift to promote operations from inner monads to the transformer stack

The mtl library provides typeclasses for common monadic capabilities

The order of transformers matters - effects are applied from inner to outer

Common patterns include ReaderT Env IO and ExceptT Error (ReaderT Env IO)

Use typeclasses and helper functions to make your code more modular

Error handling in Haskell differs significantly from exception-based approaches in imperative languages. Haskell provides several approaches that align with its functional nature and type system. For background on types and monads, see Algebraic Data Types, Common Monads, and Monads Basics.

Types of Errors in Haskell

Compile-time errors: Type errors, syntax errors, etc.

Runtime errors: Exceptions that occur during program execution

Expected failures: Situations where operations might legitimately fail

This page focuses on handling the last two categories.

Approaches to Error Handling

1. Maybe Type

The Maybe type represents computations that might fail. This is a common pattern in Haskell and is discussed in more detail in Common Monads and Algebraic Data Types.

Working with Multiple Maybe Values

Using do notation with Maybe leverages the monadic structure described in Monads Basics.

2. Either Type

The Either type provides more detailed error information. Like Maybe, it is an algebraic data type (see Algebraic Data Types) and a common monad (Common Monads).

Working with Multiple Either Values

Chaining Either computations with do notation is another example of monadic error handling (see Monads Basics).

3. ExceptT Monad Transformer

ExceptT combines the Either type with another monad (often IO). For more on combining effects, see Monad Transformers. For IO, see Introduction to IO.

4. Runtime Exceptions

Haskell has a system for runtime exceptions, but idiomatic Haskell code prefers explicit error types like Maybe and Either (see above and Common Monads).

5. Custom Exceptions

You can define custom exception types using algebraic data types (see Algebraic Data Types).
Link to original

Functors and Applicatives
Functors and Applicative Functors are key typeclasses in Haskell that provide foundational abstractions for working with values in contexts. For related abstractions, see Monads Basics, Common Monads, and Polymorphism.

Functors

A functor represents a type that can be mapped over. Intuitively, it’s a container or context that allows us to apply functions to the values inside without affecting the structure. For examples of functor instances, see Lists and List Comprehensions, Algebraic Data Types, and Introduction to IO.

The Functor Typeclass
```
class Functor f where
  fmap :: (a -> b) -> f a -> f b
```
fmap applies a function to the value(s) inside the functor, preserving the structure.

There’s also an infix operator for fmap:
```
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap
```
Functor Laws

For a type to be a valid functor, it must satisfy two laws. These laws are analogous to the monad laws (see Monad Laws) and ensure predictable behavior.
1. Identity Law: fmap id = id
  - Mapping the identity function should not change anything
2. Composition Law: fmap (f . g) = fmap f . fmap g
  - Mapping a composition of functions should be the same as mapping one function after the other
Common Functors

List Functor
```
instance Functor [] where
  fmap = map
```
Example:
```
fmap (*2) [1, 2, 3]  -- [2, 4, 6]
(*2) <$> [1, 2, 3]   -- [2, 4, 6]
```
Maybe Functor
```
instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just a) = Just (f a)
```
Example:
```
fmap (*2) (Just 3)   -- Just 6
fmap (*2) Nothing    -- Nothing
```
Either Functor
```
instance Functor (Either a) where
  fmap _ (Left e) = Left e
  fmap f (Right x) = Right (f x)
```
Example:
```
fmap (*2) (Right 3)   -- Right 6
fmap (*2) (Left "error")  -- Left "error"
```
IO Functor
```
instance Functor IO where
  fmap f action = do
    result <- action
    return (f result)
```
Example:
```
fmap length getLine   -- IO Int - reads a line and returns its length
```
Creating Custom Functors

Any type with a single type parameter can potentially be a functor. For more on custom data types, see Algebraic Data Types.
```
data Tree a = Leaf | Node a (Tree a) (Tree a)
 
instance Functor Tree where
  fmap _ Leaf = Leaf
  fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)
```
Practical Uses of Functors
1. Transforming wrapped values:
```
fmap show (Just 42)  -- Just "42"
```
2. Working with computations:
```
userInput <- fmap read getLine  -- Read user input as a number
```
3. Applying functions to containers:
```
fmap (filter even) [[1,2,3], [4,5,6]]  -- [[2], [4,6]]
```
Applicative Functors

Applicative functors extend the concept of functors by allowing functions wrapped in a context to be applied to values in the same context. Applicative is a superclass of Monad (see Monads Basics).

The Applicative Typeclass
```
class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
```
- pure wraps a value in the minimal context
- <*> (pronounced “apply”) applies a function in a context to a value in a context
Applicative Laws

Valid applicative instances must satisfy several laws, which are similar in spirit to the monad laws (Monad Laws).
1. Identity: pure id <*> v = v
2. Homomorphism: pure f <*> pure x = pure (f x)
3. Interchange: u <*> pure y = pure ($ y) <*> u
4. Composition: pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
Common Applicatives

Maybe Applicative
```
instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  (Just f) <*> something = fmap f something
```
Example:
```
(+1) <$> Just 3
pure +) <*> Just 3        -- Just 4
Just (+1) <*> Just 3        -- Just 4
Just (+) <*> Just 3 <*> Just 5  -- Just 8
Nothing <*> Just 3          -- Nothing
```
List Applicative
```
instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]
```
Example:
```
[(*2), (+3)] <*> [1, 2, 3]  -- [2, 4, 6, 4, 5, 6]
```
The list applicative produces all possible combinations of applying each function to each value.

IO Applicative
```
instance Applicative IO where
  pure = return
  aF <*> aX = do
    f <- aF
    x <- aX
    return (f x)
```
Example:
```
pure (+) <*> getLine <*> getLine  -- Reads two lines and adds them as numbers
```
Helper Functions for Applicatives
```
-- Apply a function to two applicative values
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f a b = f <$> a <*> b
 
-- Sequential application
(*>) :: Applicative f => f a -> f b -> f b
a *> b = (id <$ a) <*> b
 
-- Sequence actions, discard value from the right
(<*) :: Applicative f => f a -> f b -> f a
a <* b = liftA2 const a b
```
Practical Uses of Applicatives

Applicative functors are used extensively in parser combinators (Parser Combinators), property-based testing (Property-Based Testing), and in composing effects in functional programs (Monads Basics, Common Monads).
1. Combining independent computations:
```
data Person = Person { name :: String, age :: Int }
 
validatePerson :: String -> Int -> Maybe Person
validatePerson name age =
  Person <$> validateName name <*> validateAge age
```
2. Working with multiple Maybe values:
```
lookupUser :: UserId -> Maybe User
lookupSetting :: SettingId -> Maybe Setting
 
combinedLookup :: UserId -> SettingId -> Maybe (User, Setting)
combinedLookup uid sid = (,) <$> lookupUser uid <*> lookupSetting sid
```
3. Parallel validation:
```
data Validation e a = Failure e | Success a
 
instance Semigroup e => Applicative (Validation e) where
  pure = Success
  Failure e1 <*> Failure e2 = Failure (e1 <> e2)
  Failure e <*> _ = Failure e
  _ <*> Failure e = Failure e
  Success f <*> Success a = Success (f a)
```
4. Parsing with Applicatives:
```
-- Using a parser combinator library
parseFullName :: Parser FullName
parseFullName = FullName <$> parseFirstName <*> parseLastName
```
The Relationship Between Functors, Applicatives, and Monads

These typeclasses form a hierarchy with increasing power:
1. Functor: Ability to map functions over a context
```
fmap :: (a -> b) -> f a -> f b
```
2. Applicative: Ability to apply wrapped functions to wrapped values
```
(<*>) :: f (a -> b) -> f a -> f b
```
3. Monad: Ability to sequence computations that depend on previous results
```
(>>=) :: f a -> (a -> f b) -> f b
```
The relationship can be summarized as:
- Every Monad is an Applicative
- Every Applicative is a Functor
- Functors are the most general, Monads are the most specific
The key differences are in how they handle contexts and dependencies:
- Functors apply functions to values in a context
- Applicatives apply functions in a context to values in a context
- Monads use the result of one computation to determine the next computation
When to Use Each
- Use Functor when you just need to transform values inside a context
- Use Applicative when you need to combine independent values in contexts
- Use Monad when each step depends on the result of the previous step
Key Points to Remember
1. Functors let you apply a function to a value in a context, preserving the structure
2. The key functor operation is fmap or <$>
3. Applicative functors let you apply a function in a context to a value in a context
4. The key applicative operations are pure and <*>
5. Applicatives are more powerful than functors but less powerful than monads
6. Applicatives excel at combining independent computations
Haskell:
```
\x -> \y -> x + y
-- Or equivalently
\x y -> x + y
```
Many Haskell concepts can be traced back to lambda calculus:
- Anonymous functions (lambdas) (Functions and Equations)
- Higher-order functions (Higher-Order Functions)
- Currying (Functions and Equations)
- Lazy evaluation (similar to normal-order evaluation in lambda calculus; see Evaluation Strategies)
Evaluation Strategies

Normal Order Evaluation

In normal order evaluation (which Haskell uses a variant of), function arguments are substituted without being evaluated, and then the resulting expression is evaluated. For more, see Evaluation Strategies.

Church-Rosser Theorem

The Church-Rosser theorem states that if an expression can be reduced in two different ways, then there exists a common form that both reduction paths eventually reach. This property is also discussed in Expressions and Reduction.

Computability and the Lambda Calculus

The lambda calculus is Turing complete, meaning it can express any computable function. This was one of the key insights that led to the development of modern computers.

Examples in Haskell

…
Link to original
Lambda Calculus
Lambda calculus is a formal system in mathematical logic and computer science for expressing computation based on function abstraction and application. Developed by Alonzo Church in the 1930s, it forms the theoretical foundation of functional programming languages, including Haskell.

Core Concepts

The lambda calculus consists of three basic components:
1. Variables: Symbols that represent parameters or values (e.g., x, y, z)
2. Function abstraction: Creating a function that maps an input to an output
3. Function application: Applying a function to an argument
Syntax

The syntax of the lambda calculus can be defined as:
```
<expr> ::= <variable>             -- Variable
         | λ<variable>.<expr>     -- Abstraction (creating a function)
         | <expr> <expr>          -- Application (applying a function)
```
Examples
- Variable: x
- Abstraction: λx.x (the identity function)
- Application: (λx.x) y (applying the identity function to y)
Rewrite Rules

α-conversion (Alpha Conversion)

Alpha conversion allows renaming bound variables as long as no free variables are captured:
```
λx.M ≡ λy.M[y/x]
```
where M[y/x] means “substitute y for x in M”, and y is not already a free variable in M.

Example:
```
λx.x ≡ λy.y
```
β-reduction (Beta Reduction)

Beta reduction represents function application - substituting the argument for the parameter in the function body:
```
(λx.M) N → M[N/x]
```
Example:
```
(λx.x+1) 5 → 5+1 → 6
```
η-conversion (Eta Conversion)

Eta conversion captures the idea that two functions are equivalent if they give the same result for all inputs:
```
λx.(f x) ≡ f
```
where x does not appear free in f.

Church Encodings

Since lambda calculus has only functions, we need to encode data using functions.

Booleans
```
true = λx.λy.x
false = λx.λy.y
```
These encode the behavior of true and false in an if-then-else construct:
- true returns the first argument
- false returns the second argument
Natural Numbers (Church Numerals)

Church numerals represent natural numbers by applying a function n times:
```
0 = λf.λx.x
1 = λf.λx.f x
2 = λf.λx.f (f x)
3 = λf.λx.f (f (f x))
...
n = λf.λx.f^n x  (f applied n times to x)
```
Arithmetic Operations
```
succ = λn.λf.λx.f (n f x)      -- Successor function
add = λm.λn.λf.λx.m f (n f x)  -- Addition
mult = λm.λn.λf.m (n f)        -- Multiplication
```
Fixed Point Combinators

Fixed point combinators allow us to define recursive functions in the lambda calculus, where recursion isn’t directly supported.

The Y combinator is a classic fixed point combinator:
```
Y = λf.(λx.f (x x)) (λx.f (x x))
```
Given a function f, Y f is a fixed point of f, meaning that:
```
Y f = f (Y f)
```
This allows us to create recursive functions.

Connection to Haskell

Haskell’s syntax is directly inspired by lambda calculus. For example:

Lambda calculus:
```
λx.λy.x + y
```
Haskell:
```
\x -> \y -> x + y
-- Or equivalently
\x y -> x + y
```
Many Haskell concepts can be traced back to lambda calculus:
- Anonymous functions (lambdas)
- Higher-order functions
- Currying
- Lazy evaluation (similar to normal-order evaluation in lambda calculus)
Evaluation Strategies

Normal Order Evaluation

In normal order evaluation (which Haskell uses a variant of), function arguments are substituted without being evaluated, and then the resulting expression is evaluated.

Example:
```
(λx.x+x) (1+2)
→ (1+2)+(1+2)
→ 3+3
→ 6
```
Applicative Order Evaluation

In applicative order evaluation, function arguments are evaluated before being substituted.

Example:
```
(λx.x+x) (1+2)
→ (λx.x+x) 3
→ 3+3
→ 6
```
Church-Rosser Theorem

The Church-Rosser theorem states that if an expression can be reduced in two different ways, then there exists a common form that both reduction paths eventually reach.

This ensures that the lambda calculus is confluent, meaning the order of reductions doesn’t affect the final result (if it exists).

Computability and the Lambda Calculus

The lambda calculus is Turing complete, meaning it can express any computable function. This was one of the key insights that led to the development of modern computers.

Examples in Haskell

Encoding Church Numerals in Haskell
```
-- Church numeral type
type Church a = (a -> a) -> a -> a
 
-- Converting from Integer to Church
toChurch :: Integer -> Church a
toChurch 0 = \f x -> x
toChurch n = \f x -> f (toChurch (n-1) f x)
 
-- Converting from Church to Integer
fromChurch :: Church Integer -> Integer
fromChurch n = n (+1) 0
 
-- Church arithmetic
churchSucc :: Church a -> Church a
churchSucc n = \f x -> f (n f x)
 
churchAdd :: Church a -> Church a -> Church a
churchAdd m n = \f x -> m f (n f x)
 
churchMult :: Church a -> Church a -> Church a
churchMult m n = \f -> m (n f)
```
Y Combinator in Haskell
```
-- Y combinator (with a type annotation to make it work in Haskell)
y :: (a -> a) -> a
y f = (\x -> f (x x)) (\x -> f (x x))
 
-- Using Y to define factorial
factorial = y $ \f n -> if n <= 0 then 1 else n * f (n-1)
```
Note: This won’t actually work in Haskell due to the type system, but it illustrates the concept.

Key Points to Remember
1. Lambda calculus consists of variables, abstractions (functions), and applications
2. Alpha conversion renames bound variables
3. Beta reduction substitutes arguments into function bodies
4. Church encodings represent data as functions
5. Fixed point combinators enable recursion
6. The lambda calculus is Turing complete
7. Haskell’s syntax and semantics are directly inspired by lambda calculus
Link to original

Equational Reasoning
Equational reasoning is a powerful technique for analyzing and proving properties of functional programs. In pure functional languages like Haskell, it’s particularly effective due to referential transparency. For more on purity and referential transparency, see Expressions and Reduction and Functions and Equations.

The Foundations: Referential Transparency

A program is referentially transparent if any expression can be replaced with its value without changing the program’s behavior. This property is what makes equational reasoning possible and is central to Haskell’s design (Expressions and Reduction).

Basic Principles of Equational Reasoning

Equational reasoning allows us to:

Substitute equals for equals

Transform programs step by step

Prove properties about our code

Optimize implementations

For more on substitution and transformation, see Lambda Calculus and Pattern Matching and Recursion.

Example of Simple Substitution
let x = 5 + 3 in x * 2
= let x = 8 in x * 2
= 8 * 2
= 16
Each step replaces an expression with its equivalent value.

Proof Techniques

Direct Substitution

Directly substitute definitions and simplify:
-- Define a function
double x = x + x
 
-- Prove: double (a + b) = double a + double b
double (a + b)
= (a + b) + (a + b)    -- By definition of double
= a + b + a + b        -- Associativity of (+)
= a + a + b + b        -- Commutativity and associativity of (+)
= double a + double b  -- By definition of double
Induction

For recursive functions and data structures, induction is a powerful technique. For more on recursion and induction, see Pattern Matching and Recursion and Algebraic Data Types.

Example: Proving Length of Append
-- Prove: length (xs ++ ys) = length xs + length ys
 
-- Base case: xs = []
length ([] ++ ys)
= length ys                  -- By definition of (++)
= 0 + length ys             -- By definition of (+)
= length [] + length ys     -- By definition of length
 
-- Inductive case: xs = (x:xs')
-- Assume: length (xs' ++ ys) = length xs' + length ys
 
length ((x:xs') ++ ys)
= length (x:(xs' ++ ys))    -- By definition of (++)
= 1 + length (xs' ++ ys)    -- By definition of length
= 1 + (length xs' + length ys)  -- By induction hypothesis
= (1 + length xs') + length ys  -- By associativity of (+)
= length (x:xs') + length ys    -- By definition of length
Structural Induction

For recursive data types, we use structural induction (Algebraic Data Types).

Example: Tree Depth
data Tree a = Leaf | Node a (Tree a) (Tree a)
 
depth :: Tree a -> Int
depth Leaf = 0
depth (Node _ l r) = 1 + max (depth l) (depth r)
 
-- Prove: depth (mirror t) = depth t
-- where mirror is:
mirror :: Tree a -> Tree a
mirror Leaf = Leaf
mirror (Node x l r) = Node x (mirror r) (mirror l)
 
-- Base case: t = Leaf
depth (mirror Leaf)
= depth Leaf       -- By definition of mirror
= 0                -- By definition of depth
 
-- Inductive case: t = Node x l r
-- Assume: depth (mirror l) = depth l and depth (mirror r) = depth r
 
depth (mirror (Node x l r))
= depth (Node x (mirror r) (mirror l))  -- By definition of mirror
= 1 + max (depth (mirror r)) (depth (mirror l))  -- By definition of depth
= 1 + max (depth r) (depth l)  -- By induction hypothesis
= 1 + max (depth l) (depth r)  -- By commutativity of max
= depth (Node x l r)  -- By definition of depth
Working with Higher-Order Functions

Equational reasoning extends to higher-order functions, which is particularly useful for understanding and optimizing functional code (Higher-Order Functions, Functions and Equations).

Example: Map Fusion
-- Prove: map f (map g xs) = map (f . g) xs
 
-- Base case: xs = []
map f (map g [])
= map f []         -- By definition of map
= []               -- By definition of map
= map (f . g) []   -- By definition of map
 
-- Inductive case: xs = (x:xs')
-- Assume: map f (map g xs') = map (f . g) xs'
 
map f (map g (x:xs'))
= map f (g x : map g xs')    -- By definition of map
= f (g x) : map f (map g xs')  -- By definition of map
= (f . g) x : map f (map g xs')  -- By definition of (.)
= (f . g) x : map (f . g) xs'    -- By induction hypothesis
= map (f . g) (x:xs')  -- By definition of map
Case Studies

Proving Properties of Recursive Functions

For more on recursion and proofs, see Pattern Matching and Recursion.
-- Prove: reverse (reverse xs) = xs
 
-- Base case: xs = []
reverse (reverse [])
= reverse []       -- By definition of reverse
= []               -- By definition of reverse
 
-- Inductive case: xs = (x:xs')
-- Assume: reverse (reverse xs') = xs'
 
reverse (reverse (x:xs'))
= reverse (reverse xs' ++ [x])  -- By definition of reverse
= reverse [x] ++ reverse (reverse xs')  -- reverse distributes over (++)
= [x] ++ xs'        -- By definition of reverse and induction hypothesis
= x:xs'             -- By definition of (:) and (++)
Optimizing with Equational Reasoning

For optimization techniques and laws, see also Evaluation Strategies and Monad Laws.
-- Original function
sum (filter p xs)
 
-- Optimization
sum (filter p (xs ++ ys))
= sum (filter p xs ++ filter p ys)  -- filter distributes over (++)
= sum (filter p xs) + sum (filter p ys)  -- sum distributes over (++)
This optimization allows for parallel computation of the sums.

Common Laws for Standard Functions

Knowing these laws helps in equational reasoning. For more on standard functions and their properties, see Lists and List Comprehensions, Higher-Order Functions, and Property-Based Testing.

List Functions
-- Map laws
map id = id
map f . map g = map (f . g)
 
-- Filter laws
filter p . filter q = filter (\x -> p x && q x)
filter p . map f = map f . filter (p . f)
 
-- Fold laws
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
foldr f z (map g xs) = foldr (\x acc -> f (g x) acc) z xs
Functor Laws
-- Identity
fmap id = id
 
-- Composition
fmap f . fmap g = fmap (f . g)
Applicative Laws
-- Identity
pure id <*> v = v
 
-- Composition
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
 
-- Homomorphism
pure f <*> pure x = pure (f x)
 
-- Interchange
u <*> pure y = pure ($ y) <*> u
Monad Laws
-- Left identity
return a >>= f = f a
 
-- Right identity
m >>= return = m
 
-- Associativity
(m >>= f) >>= g = m >>= (\x -> f x >>= g)
Free Theorems

Parametricity in Haskell leads to “free theorems” - properties that must hold based solely on a function’s type signature.

For example, any function of type [a] -> [a] (that doesn’t use undefined or similar) must satisfy:
map f . g = g . map f
for any function f. This is because g can’t inspect, create, or modify the elements - it can only rearrange, drop, or duplicate them.

Tooling Support

Haskell’s ecosystem provides tools to aid equational reasoning:

QuickCheck: Property-based testing to verify equations

LiquidHaskell: Refinement types that can express and verify properties

Coq/Agda integration: For formal verification of Haskell code

Link to original

Quartz 4

Explorer

Functional Programming Printable

Haskell Fundamentals

Expressions and Reduction

Expressions vs. Statements

Key Points

Examples

Reduction

Church-Rosser Property

Example of Reduction

Types

Type Inference

Summary

Functions and Equations

Function Definitions

Lambda (Anonymous) Functions

Named Functions with Equations

Type Signatures

Currying

Benefits of Currying

Function Application

Function Composition

Equations are not Assignments

Key Principles

Key Points to Remember

Common Mistakes

Lists and List Comprehensions

List Basics

Syntax

List Construction

List Manipulation

List Comprehensions

Basic Syntax

Examples

List Operations

List Concatenation

List Zipping

Lists vs. Tuples

Key Points to Remember

Algebraic Data Types

Basic Syntax

Types of ADTs

Sum Types (Enumerations)

Product Types

Mixed Sum and Product Types

Record Syntax

Recursive Data Types

Parameterized Types

Type Synonyms

Newtype

Pattern Matching with ADTs

The Maybe Type

Deriving Typeclasses

Key Points to Remember

Pattern Matching and Recursion

Pattern Matching

Basic Syntax

Patterns for Different Types

Matching on Numbers and Characters

Matching on Lists

Matching on Tuples

Matching on Algebraic Data Types

Pattern Guards

case Expressions

Recursion

Anatomy of Recursive Functions

List Processing with Recursion

Recursive Numerical Functions

Tree Traversal with Recursion

Mutual Recursion

Tail Recursion

Key Points to Remember

Higher-Order Functions

Core Concepts

Definition

Benefits

Common Higher-Order Functions on Lists

map

filter

The `Maybe` Type

`case` Expressions

`map`

`filter`

Folds (`foldr` and `foldl`)

Right Fold (`foldr`)

Left Fold (`foldl`)

Differences Between `foldl` and `foldr`

`zipWith`

Example: Functions of Type `a -> a`

`Eq` - Equality Testing

`Ord` - Ordering