1.

Introduction to Haskell

What is Haskell?
Haskell is a functional programming language where you describe what you want (not how to do
it step-by-step). It’s like giving a recipe instead of cooking instructions. Key features:

• Pure Functions: Functions always give the same output for the same input and don’t
change anything else.

• Static Typing: Haskell checks data types (e.g., numbers vs. words) before running.

• Lazy Evaluation: Calculations happen only when needed.

Example:

-- A function to square a number

square :: Int -> Int

square x = x * x

main :: IO ()

main = print (square 5) -- Output: 25

• Explanation: square takes an integer (Int), multiplies it by itself, and returns the result.
main is the starting point of the program, and print shows the result on the screen.

• :: Int -> Int means the function takes an integer and returns an integer.

• What is main?

• In Haskell, main is the starting point of a program. When you run a Haskell program, the
computer looks for main to know what to do first.
• The :: IO () part is a type signature. It tells Haskell that main is a special function that
does input/output (I/O) actions, like printing to the screen. The IO part means it handles
interactions with the outside world, and () (called "unit") means it doesn’t return a useful
value—it just performs actions.
• The line main = print (square 5) defines what main does. It uses the print function, which
is built into Haskell, to display a value on the screen.

Self-Study Exercise:
1. Write a function cube that takes a number and returns its cube (e.g., cube 3 should return
27).
2. Modify the main function to print cube 4.
2. Defining Functions: Guards, Pattern Matching, and Recursion

Concepts:

• Guards: Conditional rules (like “if this, then that”) to decide what a function does.

• Pattern Matching: Different rules for specific inputs (e.g., a special case for zero).
• Recursion: A function calls itself with a smaller input to solve a problem.

Example:

-- Calculate factorial (e.g., 4! = 4 * 3 * 2 * 1 = 24)

factorial :: Int -> Int

factorial 0 = 1 -- Pattern matching: if input is 0, return 1

factorial n | n > 0 = n * factorial (n - 1) -- Guard: if n > 0, multiply n by factorial of (n-1)

| otherwise = error "Negative input" -- Guard: error for negative numbers

main :: IO ()
main = print (factorial 4) -- Output: 24

1. What are Guards?

o Guards in Haskell are like "if-then" conditions that let a function choose what to do
based on the input. They’re written with a | symbol followed by a condition, and if
the condition is true, the expression after = is used.

o Guards are part of the function’s definition and are checked in order, top to bottom.

2. Line: factorial n | n > 0 = n * factorial (n - 1)

o What it does: This line defines what factorial does when the input n is greater
than 0.

o Breakdown:

▪ factorial n: The function factorial takes a parameter n. This line applies

to any input n that isn’t matched by an earlier pattern (like factorial 0).

▪ | n > 0: This is the guard. It checks if n is greater than 0 (e.g., 1, 2, 3,

etc.). If true, the expression to the right of = is used.

▪ = n * factorial (n - 1): If n > 0 is true, compute n multiplied by the

factorial of n - 1. This is recursion, where the function calls itself with
a smaller input (n - 1).
 ▪ Comment: -- Guard: if n > 0, multiply n by factorial of (n-1) explains
the purpose. Comments starting with -- are ignored by Haskell and are
there to help you understand.

o Example: For factorial 4:

▪ Since 4 > 0, use this guard.

▪ Compute: 4 * factorial (4 - 1) = 4 * factorial 3.

▪ Then: factorial 3 = 3 * factorial 2, and so on, until reaching factorial 0.

3. Line: | otherwise = error "Negative input"

o What it does: This is another guard that handles all cases not covered by
previous guards or patterns (i.e., when n is not 0 and not greater than 0, so n
is negative).

o Breakdown:

▪ | otherwise: The keyword otherwise is like "else" in other languages—

it’s a catch-all condition that’s true if no earlier guards match. Here, it
applies to negative numbers (e.g., -1, -2).

▪ = error "Negative input": If this guard is reached, the function calls

error, a built-in Haskell function that stops the program and displays
the message "Negative input". This prevents calculating factorials for
invalid inputs.
▪ Comment: -- Guard: error for negative numbers explains that this
handles negative inputs by throwing an error.
o Example: If you try factorial (-1), since -1 is not 0 (misses the factorial 0
pattern) and not greater than 0 (misses the n > 0 guard), it hits otherwise and
stops with an error message: Negative input.

4. How It Fits into the Full Function

o The full factorial function has three cases:

▪ Pattern Matching: factorial 0 = 1 (base case for recursion).

▪ Guard 1: | n > 0 = n * factorial (n - 1) (recursive case for positive

numbers).
▪ Guard 2: | otherwise = error "Negative input" (error for negatives).
o Haskell checks these in order:
 ▪ If the input is 0, use factorial 0 = 1.

▪ If the input is not 0, check the guards:

▪ If n > 0, use the recursive case.

▪ If not (i.e., n is negative), use the otherwise case and throw an

error.

5. How It Works in Action

o Let’s trace factorial 4:

▪ Input: n = 4. Not 0, so skip factorial 0.

▪ Check guards: 4 > 0 is true, so use 4 * factorial (4 - 1) = 4 * factorial 3.

▪ For factorial 3: 3 > 0, so 3 * factorial (3 - 1) = 3 * factorial 2.

▪ For factorial 2: 2 > 0, so 2 * factorial (2 - 1) = 2 * factorial 1.

▪ For factorial 1: 1 > 0, so 1 * factorial (1 - 1) = 1 * factorial 0.

▪ For factorial 0: Matches pattern factorial 0 = 1, so return 1.

▪ Now compute back up: 1 * 1 = 1, 2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24.

▪ Result: factorial 4 = 24.

o For factorial (-1):

▪ Not 0, so skip pattern.

▪ Guards: -1 > 0 is false, so use otherwise.

▪ Result: error "Negative input" stops the program.

Self-Study Exercise:

1. Write a function sumToN that adds numbers from 1 to n (e.g., sumToN 3 returns 1 + 2 +
3 = 6) using recursion and pattern matching.

2. Add a guard to handle negative inputs by returning 0.

3. Lists, Strings, and Tuples

Concepts:

• Lists: Ordered collections of the same type (e.g., [1, 2, 3] for numbers or ['h', 'i'] for
characters). Strings are lists of characters (e.g., "hi" = ['h', 'i']).
 • Tuples: Fixed-size collections that can hold different types (e.g., (1, "hello")).

• String: A list of characters.

• Common operations: head (first item), tail (rest of the list), ++ (join lists).

Example:
-- Pair the first number and first letter

pairFirst :: [Int] -> [Char] -> (Int, Char)

pairFirst numbers letters = (head numbers, head letters)

main :: IO ()

main = do

let nums = [5, 6, 7]

let chars = "abc" -- Same as ['a', 'b', 'c']

print (pairFirst nums chars) -- Output: (5, 'a')

print (chars ++ "de") -- Output: "abcde"

• Explanation:

o nums is a list of numbers; chars is a string (list of characters).

o pairFirst takes the first number and first letter, returning them as a tuple.

o ++ joins the string "abc" with "de" to make "abcde".

Self-Study Exercise:

1. Write a function secondItem that returns the second item of a list or 0 if the list is too
short.

2. Create a tuple with your age and name, and print it.

4. Types and Polymorphism

What is Polymorphism in Haskell?

Polymorphism means a function can work with many types of data without needing separate
versions for each type. In Haskell, parametric polymorphism uses type variables (like a or
b) to make functions flexible, so they work with any type, as long as the type fits the function’s
logic. This is powerful because it lets you write one function that works for numbers, strings,
booleans, or even custom types, without rewriting it.
Polymorphic Function

Haskell function that demonstrates polymorphism by swapping the elements of a pair

(tuple). It works with any types for the pair’s elements:

haskell

-- Swap the elements of a pair

swap :: (a, b) -> (b, a)

swap (x, y) = (y, x)

main :: IO ()
main = do

print (swap (1, "hello")) -- Output: ("hello", 1)

print (swap (True, 42)) -- Output: (42, True)

print (swap ("yes", "no")) -- Output: ("no", "yes")

This function swaps the two elements in a pair, and it’s polymorphic because it works with
pairs containing any types (e.g., a number and a string, or a boolean and a number). Let’s
break it down.

Detailed Explanation of the Code

1. Type Signature: swap :: (a, b) -> (b, a)

o What it means:

▪ :: says “this is the type of the function.”

▪ (a, b) is the input: a tuple (pair) where the first element is type a and
the second is type b. Here, a and b are type variables, meaning they
can be any type (e.g., Int, String, Bool).
▪ -> means the function returns something.

▪ (b, a) is the output: a tuple with the second element (type b) first and
the first element (type a) second.

o Polymorphism: The use of a and b makes swap flexible. It can swap pairs
like (Int, String), (Bool, Int), or (String, String)—the function doesn’t care
what a or b are, as long as the input is a pair and the output reverses it.
 o Example: For (1, "hello"), a is Int, b is String, so the type becomes (Int,
String) -> (String, Int).

2. Function Definition: swap (x, y) = (y, x)

o What it does: This defines how swap works. It uses pattern matching to take
a tuple (x, y) and return a new tuple (y, x).

o Breakdown:

▪ (x, y) is the input pattern: x is the first element (type a), y is the second
(type b).

▪ = defines what to return: (y, x), a new tuple with y first and x second.

▪ No computation (like adding or multiplying) is needed—just

rearranging the elements.

o Why polymorphic?: The function doesn’t care about the types of x and y. It
just moves them, so it works for any pair of values, regardless of their types.

3. Main Function: main :: IO ()

o What it does: main is the starting point of the program, where we test swap
with different types.

o Type: IO () means it performs input/output (like printing) and returns no

useful value (unit, ()).

4. Main Body: main = do

o The do keyword starts a block to sequence multiple actions (here, multiple

print statements).

5. Test Case 1: print (swap (1, "hello"))

o What happens:

▪ Input: (1, "hello"), a tuple where a = Int, b = String.

▪ Pattern matches (x, y) with x = 1, y = "hello".

▪ Returns (y, x) = ("hello", 1).

▪ print displays ("hello", 1).

o Polymorphism: The function works with an Int and a String without needing
a special version.
6. Test Case 2: print (swap (True, 42))
 o What happens:

▪ Input: (True, 42), where a = Bool, b = Int.

▪ Matches x = True, y = 42.

▪ Returns (42, True).

▪ print displays (42, True).

o Polymorphism: Works with Bool and Int, showing flexibility.

7. Test Case 3: print (swap ("yes", "no"))

o What happens:

▪ Input: ("yes", "no"), where a = String, b = String.

▪ Matches x = "yes", y = "no".

▪ Returns ("no", "yes").

▪ print displays ("no", "yes").

o Polymorphism: Works when both elements are the same type (String).

8. Comments: -- Output: ...

o These are notes (ignored by Haskell) showing what each print will display,
helping you understand the results.

Why This Shows Polymorphism

The swap function is polymorphic because:

• It uses type variables a and b, allowing it to work with any types in the tuple.

• It handles different combinations (Int and String, Bool and Int, String and String) without
changing the function’s code.

• Haskell’s type system ensures safety: If you try swap (1, 2, 3) (not a pair), it won’t compile
because the input must be a tuple (a, b).

This is parametric polymorphism, as the function’s logic (swapping elements) is the same
regardless of the types.

Self-Study Exercise:
1. Write a polymorphic function lastOrDefault that returns the last item of a list or a default
value if empty.
 2. Test it with a list of numbers and a list of characters.

5. Higher-Order Functions on Lists: Map, Filter, List Comprehension

• Higher-Order Functions: Functions that take other functions as inputs.

• Map: Applies a function to every item in a list.

• Filter: Picks items that meet a condition.

• List Comprehension: A shortcut to create lists by transforming or filtering.

A. Map

The map function applies a given function to every item in a list, producing a new list with the
results. It’s a built-in higher-order function in Haskell, commonly used to transform lists.

Example: This example uses map to triple each number in a list.

haskell

-- Triple a number

triple :: Int -> Int

triple x = x * 3

main :: IO ()

main = do

let numbers = [1, 2, 3, 4]

print (map triple numbers) -- Output: [3, 6, 9, 12]

Detailed Explanation:

• Function triple:
o triple :: Int -> Int: Takes an integer, returns an integer.

o triple x = x * 3: Multiplies input by 3 (e.g., triple 2 = 6).

• Main Function:

o main :: IO (): I/O entry point.

o let numbers = [1, 2, 3, 4]: Defines a list of integers.

o print (map triple numbers):
 ▪ map is a built-in function with type (a -> b) -> [a] -> [b], meaning it
takes a function (here, triple) and a list, applies the function to each
element, and returns a new list.

▪ map triple [1, 2, 3, 4] applies triple to each element:

▪ triple 1 = 3

▪ triple 2 = 6

▪ triple 3 = 9

▪ triple 4 = 12

▪ Result: [3, 6, 9, 12], which print displays.

What is Filter in Haskell?

Filter is a built-in Haskell function that takes a list and a condition (called a predicate function)
and returns a new list containing only the elements that satisfy the condition. It’s a higher-order
function because it takes a function as an input. Think of filter as a gatekeeper who checks each
item in a list and only lets through the ones that pass a test.

• Type Signature: filter :: (a -> Bool) -> [a] -> [a]

o (a -> Bool): A function that takes any type a and returns True or False.
o [a]: The input list of type a.
o [a]: The output list containing only elements where the predicate returns True.
• Polymorphism: filter works with any type (a), as long as the predicate function returns a
boolean.

Example Code: Filter

This example uses filter to select short strings (length ≤ 3) from a list of strings.

haskell
-- Check if a string has length <= 3
isShort :: String -> Bool
isShort str = length str <= 3

main :: IO ()
main = do
 let words = ["cat", "dog", "elephant", "hi", "rhinoceros"]
print (filter isShort words) -- Output: ["cat", "dog", "hi"]

Detailed Explanation of the Code

1. Function: isShort :: String -> Bool

o What it does: This is the predicate function that checks if a string’s length is 3 or
less.
o Breakdown:
▪ :: String -> Bool: The type signature says isShort takes a String (a list of
characters) and returns a Bool (True or False).
▪ isShort str = length str <= 3:
▪ str is the input string.
▪ length str (built-in function) counts the characters in str.
▪ <= 3 checks if the length is less than or equal to 3.
▪ Returns True if the condition is met, else False.
▪ Examples:
▪ isShort "cat" → length "cat" = 3, 3 <= 3 is True.
▪ isShort "elephant" → length "elephant" = 8, 8 <= 3 is False.

What is List Comprehension in Haskell?

List comprehension is a concise way to create a new list in Haskell by transforming or filtering
elements from an existing list. It’s like a shortcut that combines the ideas of map (transforming
elements) and filter (selecting elements) in a single expression. The syntax is inspired by
mathematical set notation, making it readable and expressive.

• Syntax: [output | variable <- inputList, condition]

o output: What to produce for each element (e.g., transform it).
o variable <- inputList: Draws each element from the input list.
o condition: Optional filter to keep only certain elements (must return True or False).
• Purpose: It’s a powerful way to process lists without writing explicit loops, aligning with
Haskell’s functional programming style.

Example Code: List Comprehension

This example creates a list of lengths of strings that start with the letter 'b' from a given list of
strings.

haskell
 main :: IO ()

main = do

let words = ["bear", "cat", "ball", "dog", "banana"]

print [length word | word <- words, head word == 'b'] -- Output: [4, 4]

Detailed Explanation of the Code

1. Main Function: main :: IO ()

o What it does: This is the program’s entry point, where we test the list
comprehension.
o Type: IO () indicates it performs input/output actions (like printing) and returns no
useful value (unit, ())
2. Main Body: main = do
o The do keyword starts a block for sequencing I/O actions (here, a single print
statement).
3. List Definition: let words = ["bear", "cat", "ball", "dog", "banana"]
o What it does: Defines a list of strings using let. In Haskell, a String is a list of
characters ( “Lists, Strings, and Tuples”).
o The list contains: ["bear", "cat", "ball", "dog", "banana"].
o Example: "bear" is equivalent to ['b', 'e', 'a', 'r'].
4. List Comprehension: print [length word | word <- words, head word == 'b']
o What it does: Creates a new list by:
▪ Taking each string (word) from words.
▪ Keeping only strings where the first character is 'b' (using head word == 'b').
▪ Computing the length of each kept string (using length word).
▪ Printing the resulting list.
o Breakdown of the Comprehension:
▪ length word: The output expression. length (built-in function) counts the
characters in word (e.g., length "bear" = 4).
▪ word <- words: Draws each word from the input list words, one at a time
(e.g., "bear", "cat", etc.).
▪ head word == 'b': The condition (predicate). head ( “Lists, Strings, and
Tuples”) returns the first character of word (e.g., head "bear" = 'b'). The ==
'b' checks if it equals 'b', returning True or False.
o Execution:
▪ For word = "bear":
▪ head "bear" = 'b', 'b' == 'b' → True.
▪ Compute length "bear" = 4, keep 4.
▪ For word = "cat":
▪ head "cat" = 'c', 'c' == 'b' → False, skip.
▪ For word = "ball":
 ▪ head "ball" = 'b', 'b' == 'b' → True.
▪ Compute length "ball" = 4, keep 4.
▪ For word = "dog":
▪ head "dog" = 'd', 'd' == 'b' → False, skip.
▪ For word = "banana":
▪ head "banana" = 'b', 'b' == 'b' → True.
▪ Compute length "banana" = 6, keep 6.
▪ Result: [4, 4, 6], which print displays.

6. Computation as Rewriting

Concept: Haskell solves problems by rewriting expressions, like simplifying a math equation. It
replaces function calls with their definitions until it gets a final answer (called “reduction”).
Example:

-- Multiply two numbers

multiply :: Int -> Int -> Int

multiply x y = x * y

main :: IO ()

main = print (multiply (2 + 1) 3) -- Output: 9

• How It Rewrites:

1. multiply (2 + 1) 3

2. multiply 3 3 (compute 2 + 1)

3. 3 * 3 (apply multiply definition)

4. 9 (final result)

• Explanation: Haskell simplifies (2 + 1) to 3, then applies multiply to get 3 * 3 = 9.

Self-Study Exercise:
1. Write a function addThree that adds three numbers.

2. Trace the rewriting steps for addThree 2 3 4 by hand.

7. Lazy Evaluation and Infinite Data Structures

Lazy evaluation: Covered