Your exam gives you a Haskell template with undefined functions. You fill them in. The entire assignment is about a MinHeap data structure. This guide builds from "what is Haskell" all the way to implementing every function. Look for purple Memory Anchor boxes.
Haskell is pure functional. That means three things that will feel alien at first:
x = 5 doesn't "assign" 5 to x — it says "x IS 5, forever." You can't write x = x + 1.if/then/else RETURNS a value. Functions always return something.-- single line or {- block -}add x y = x + y -- takes two numbers, returns their sum double x = x * 2 -- takes one number, returns double greet name = "Hello " ++ name -- ++ concatenates strings
No parentheses around arguments. No commas between them. No return. Just name args = result.
result = add 3 5 -- 8. Juxtaposition = function call. result2 = add (2 + 1) 5 -- parentheses ONLY for grouping, not for calling result3 = double (add 3 5) -- double 8 = 16
add 3 5 works. add(3, 5) is a syntax error. Parentheses are ONLY for grouping sub-expressions, NOT for calling functions.
In Haskell, every function has a type. You write it above the definition:
add :: Int -> Int -> Int -- takes Int, takes Int, returns Int
add x y = x + y
-> as "and then takes." Int -> Int -> Int = "takes an Int, and then takes an Int, and then produces an Int." The last thing after the final -> is always the return type. Everything before it is an input.| Type | What it is | Example |
|---|---|---|
Int | Integer (fixed size) | 42 |
Bool | Boolean | True, False |
String | Text (= list of Char) | "hello" |
[a] | List of type a | [1,2,3] |
(a, b) | Tuple (pair) | (1, "hi") |
a (lowercase) | Any type (generic/template) | [a] = "list of anything" |
Instead of if/else chains, Haskell lets you define a function with multiple equations, one for each possible shape of the input. Haskell tries them top to bottom.
factorial :: Int -> Int factorial 0 = 1 -- if input is 0, return 1 factorial n = n * factorial (n - 1) -- otherwise, n * factorial(n-1)
-- Multiple patterns on values: describe :: Int -> String describe 0 = "zero" describe 1 = "one" describe _ = "something else" -- _ = wildcard (matches anything)
-- List pattern: (x:xs) means "first element : rest" myHead :: [a] -> a myHead (x:_) = x -- x is first element, _ = don't care about rest myLength :: [a] -> Int myLength [] = 0 -- empty list has length 0 myLength (_:xs) = 1 + myLength xs -- ignore head, count tail + 1
(x:xs) is EXACTLY like Prolog's [H|T]. Different syntax, same idea: x = head, xs = tail. If you learned the Prolog section, you already know this. The colon : in Haskell is the | in Prolog.
_ matches anything (wildcard). Use when you don't need the value.(x:xs) matches a non-empty list. Fails on [].[] matches only the empty list.(x:y:rest) matches a list with at least 2 elements.When you need conditions beyond pattern matching (like numeric comparisons), use guards:
absoluteValue :: Int -> Int
absoluteValue n
| n >= 0 = n -- pipe + condition = result
| otherwise = -n -- otherwise = else (always true)
classify :: Int -> String
classify n
| n < 0 = "negative"
| n == 0 = "zero"
| otherwise = "positive"
otherwise is literally defined as True. It's just readable syntax for "in all other cases."
circleArea :: Double -> Double
circleArea r = pi * rSquared
where rSquared = r * r -- defined after, used above
bmi :: Double -> Double -> String
bmi weight height
| index < 18.5 = "underweight"
| index < 25.0 = "normal"
| otherwise = "overweight"
where index = weight / height^2 -- available in all guards
circleArea2 r = let rSq = r * r in pi * rSq
where and let do the same thing. where goes at the bottom (more common). let goes inline.
-- \x -> ... means "a function that takes x and returns ..." double = \x -> x * 2 -- same as: double x = x * 2 addPair = \x y -> x + y -- same as: addPair x y = x + y
\ is supposed to look like the Greek letter lambda (λ). \x -> x + 1 = "a function that takes x and returns x+1, but I'm too lazy to give it a name." You'll see these inside map, filter, and foldl calls.
[1, 2, 3] -- a list of Ints [] -- empty list "hello" -- String = [Char] = ['h','e','l','l','o'] -- The : operator prepends an element (like cons in Lisp) 1 : [2, 3] -- [1, 2, 3] 'h' : "ello" -- "hello" -- ++ concatenates two lists [1,2] ++ [3,4] -- [1,2,3,4] -- Ranges [1..5] -- [1,2,3,4,5] [2,4..10] -- [2,4,6,8,10] (step of 2)
Like Python's list comprehensions or set-builder notation in math:
-- [expression | generator, filter] evens = [x | x <- [1..10], even x] -- [2,4,6,8,10] squares = [x*x | x <- [1..5]] -- [1,4,9,16,25] -- Multiple generators (nested loop): pairs = [(x,y) | x <- [1..3], y <- [1..2]] -- [(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)]
[x*x | x <- [1..5], even x] reads like math: {x² | x ∈ {1..5}, x is even} = {4, 16}.<- means "drawn from." The stuff after the comma is a filter.
| Function | What it does | Example |
|---|---|---|
head [1,2,3] | First element | 1 |
tail [1,2,3] | Everything except first | [2,3] |
length [1,2,3] | Length | 3 |
null [] | Is it empty? | True |
reverse [1,2,3] | Reverse | [3,2,1] |
sum [1,2,3] | Sum | 6 |
elem 2 [1,2,3] | Is 2 in the list? | True |
words "a b c" | Split on spaces | ["a","b","c"] |
Functions that take other functions as arguments. This is where Haskell gets powerful.
map (*2) [1,2,3] -- [2,4,6] (* 2 is a "section": multiply by 2) map show [1,2,3] -- ["1","2","3"] (show converts anything to String) map length ["hi","bye"] -- [2,3]
filter even [1,2,3,4,5] -- [2,4] filter (>3) [1,2,3,4,5] -- [4,5]
foldl (+) 0 [1,2,3] -- 6. Start with 0, add each element. foldl (*) 1 [1,2,3,4] -- 24. Start with 1, multiply each element.
foldl f init list = start with an empty belly (init), eat the first piece (f belly piece1), then the next piece (f newBelly piece2), and so on until the plate is empty. Final state of your belly = the result.foldl (+) 0 [1,2,3]: belly=0, eat 1→belly=1, eat 2→belly=3, eat 3→belly=6.
You'll need foldl in the exam to build a heap from a list of numbers:
-- Build a heap by inserting elements one by one buildHeap nums = foldl (\heap x -> insertHeap x heap) Empty nums -- start: Empty -- eat 5: insertHeap 5 Empty = Node 5 Empty Empty -- eat 3: insertHeap 3 (Node 5 ..) = Node 3 (Node 5 ..) Empty -- ... and so on
-- $ means "everything to my right goes in parentheses" putStrLn (show (length [1,2,3])) -- ugly nested parens putStrLn $ show $ length [1,2,3] -- same thing, cleaner -- f $ g $ h x = f (g (h x))
$ eats everything to its right. Think of it as an opening parenthesis where the closing paren is at the end of the line. f $ g x = f (g x). That's it. Nothing deeper.
In Haskell, you define new types with data. Think of it as a tagged union (C) or a variant — "this value is ONE of these possible shapes."
-- A Shape is EITHER a Circle with a radius, -- OR a Rectangle with width and height. data Shape = Circle Double | Rectangle Double Double -- Pattern match to handle each shape: area :: Shape -> Double area (Circle r) = pi * r * r area (Rectangle w h) = w * h
The | means "or." Circle and Rectangle are called constructors — they create values of type Shape.
std::variant that the compiler forces you to handle every case for.The magic: a type can reference itself. This is how you build trees.
-- A tree of integers is either: -- Empty (nothing), or -- a node with a value, a left tree, and a right tree data Tree = Leaf | Branch Int Tree Tree
This is exactly what your MinHeap will be. Let's look at it now.
This is the type definition from your assignment template:
data MinHeap a = Empty | Node a (MinHeap a) (MinHeap a) deriving (Show, Eq)
Let's unpack every piece:
| Piece | Meaning |
|---|---|
data | Keyword: "I'm defining a new type" |
MinHeap a | Type name. a is a type variable (like C++ template <T>) |
Empty | Constructor #1: an empty heap (like null) |
| | "or" |
Node a (MinHeap a) (MinHeap a) | Constructor #2: a value of type a, left subtree, right subtree |
deriving (Show, Eq) | Auto-generate show (print) and == (equality) |
Empty), or it contains a value and two smaller dolls (Node value left right). Each smaller doll is ALSO either empty or contains a value and two even smaller dolls. Dolls all the way down.
emptyHeap = Empty -- nothing singleNode = Node 5 Empty Empty -- just a 5 smallHeap = Node 1 (Node 3 Empty Empty) -- 1 (Node 5 Empty Empty) -- / \ -- 3 5
Some functions need to compare elements (to maintain min-heap order). Those need the Ord constraint:
-- "For any type 'a' that supports comparison..." merge :: Ord a => MinHeap a -> MinHeap a -> MinHeap a -- Functions that DON'T compare don't need Ord: isEmpty :: MinHeap a -> Bool -- just checks Empty vs Node size :: MinHeap a -> Int -- just counts
Ord a => is like a C++ template constraint: "this function only works for types that have <, >, == defined." Ints are Ord. Strings are Ord. Your custom type might not be.<= or compare, it needs Ord a =>. If it doesn't, leave it off.
Every MinHeap function follows the exact same skeleton. Learn this template, and you can write any of the 12 functions:
-- TEMPLATE: someFunction Empty = {- base case: what to return for an empty heap -} someFunction (Node val left right) = {- combine val with recursive calls on left and right -}
isEmpty :: MinHeap a -> Bool isEmpty Empty = True -- yes, it's empty isEmpty _ = False -- anything else = not empty
size :: MinHeap a -> Int size Empty = 0 -- empty heap has 0 nodes size (Node _ left right) = 1 + size left + size right -- this node (1) + everything in left subtree + everything in right
size (Node 1 (Node 3 Empty Empty) (Node 5 Empty Empty))findMin :: MinHeap a -> a
findMin (Node val _ _) = val -- root IS the minimum (it's a min-heap!)
No recursion needed. The minimum is always at the top. That's the whole point of a min-heap.
heapToList :: MinHeap a -> [a]
heapToList Empty = []
heapToList (Node val left right) =
val : heapToList left ++ heapToList right
-- root first, then all of left, then all of right
mapHeap :: (a -> a) -> MinHeap a -> MinHeap a
mapHeap _ Empty = Empty
mapHeap f (Node val left right) =
Node (f val) (mapHeap f left) (mapHeap f right)
-- apply f to root, recurse on both children
The min-heap property: every node's value must be ≤ both its children's values. We need to check this at every level.
isHeap :: Ord a => MinHeap a -> Bool isHeap Empty = True -- an empty heap is valid isHeap (Node v left right) = checkChild v left -- root ≤ left child? && checkChild v right -- root ≤ right child? && isHeap left -- left subtree valid? && isHeap right -- right subtree valid? where checkChild _ Empty = True -- no child = no violation checkChild parent (Node cv _ _) = parent <= cv -- parent must be ≤ child
The where block defines checkChild as a helper that's only visible inside isHeap. It compares a parent value against a child's root.
isHeap (Node 5 (Node 2 Empty Empty) Empty)&&. Returns False.merge combines two min-heaps into one. It's the foundation: insert and deleteMin are both one-liners that call merge.
merge :: Ord a => MinHeap a -> MinHeap a -> MinHeap a merge Empty h = h -- merging with empty = the other heap merge h Empty = h -- same thing merge h1@(Node v1 l1 r1) h2@(Node v2 l2 r2) | v1 <= v2 = Node v1 (merge r1 h2) l1 | otherwise = Node v2 (merge h1 r2) l2
h1@(Node v1 l1 r1) means "call the whole thing h1, AND also unpack it into v1, l1, r1." It's a name AND a pattern at the same time. Useful when you need both the whole value and its parts.
Look at the third equation carefully. When v1 ≤ v2:
v1 becomes the new root (it's smaller)r1 gets merged with the losing heap h2 → becomes the new LEFT childl1 becomes the new RIGHT childThe children swap! Old left becomes right, merged right becomes left. This keeps the tree roughly balanced over time.
merge (Node 3 Empty Empty) (Node 1 (Node 5 Empty Empty) Empty)Node 1 (Node 3 Empty Empty) (Node 5 Empty Empty)1 / \ 3 5
This is where the beauty of merge pays off. Both operations are trivial:
insertHeap :: Ord a => a -> MinHeap a -> MinHeap a insertHeap x heap = merge (Node x Empty Empty) heap
Wrap the new value in a single-node heap, then merge it in. That's it. One line.
deleteMin :: Ord a => MinHeap a -> MinHeap a deleteMin Empty = Empty deleteMin (Node _ left right) = merge left right
Throw away the root (the minimum). Now you have two orphan subtrees. Merge them back together. One line.
merge) to see who becomes the new king. The one with the smaller value wins.
insertHeap 2 (Node 5 Empty Empty)merge (Node 2 Empty Empty) (Node 5 Empty Empty)Node 2 (merge Empty (Node 5 Empty Empty)) EmptyNode 2 (Node 5 Empty Empty) Empty2 / 5
These functions extract data from the heap using list comprehension (section 5).
evenHeap :: MinHeap Int -> [Int] evenHeap heap = [x | x <- heapToList heap, even x] -- Step 1: heapToList converts the heap to a flat list -- Step 2: list comprehension filters for even values
processHeap :: MinHeap Int -> [Int] processHeap heap = [x * x | x <- evenHeap heap] -- Step 1: evenHeap gives us the even elements -- Step 2: list comprehension squares each one
These are intentionally simple. The hard part (heap operations) is in merge/insert/delete. The list processing just chains together functions you already have.
evenHeap and processHeap use MinHeap Int (not MinHeap a) because even only works on integers. You can't check if a String is even.Ord because they never compare heap elements — they just extract and filter.Haskell is "pure" — functions can't have side effects. But reading input and printing output ARE side effects. So Haskell quarantines them in a special IO zone using do notation.
main :: IO () main = do line <- getLine -- read a line from stdin let nums = map read (words line) :: [Int] -- parse into numbers let heap = foldl (\h x -> insertHeap x h) Empty nums putStrLn (show (size heap)) -- print result
<- vs let — THE confusion point<- = "reach out to the outside world and grab something." (I/O: getLine, readFile)let = "figure something out in your head." (Pure computation: parsing, math)line <- getLine = "go ask the user for a line" (talks to the outside)let nums = ... = "now compute the numbers from that line" (pure math, no I/O)
| Function | Type | What it does |
|---|---|---|
getLine | IO String | Read one line from stdin |
putStrLn s | String -> IO () | Print string + newline |
print x | Show a => a -> IO () | Print anything (calls show) |
getContents | IO String | Read ALL of stdin |
-- "3 5 1" → [3, 5, 1] words "3 5 1" -- ["3", "5", "1"] map read (words "3 5 1") :: [Int] -- [3, 5, 1] -- read converts a String to any type (you must specify which!): read "42" :: Int -- 42 read "3.14" :: Double -- 3.14 -- show converts anything to a String: show 42 -- "42" show [1,2,3] -- "[1,2,3]"
read without a type annotation is an error. Always add :: [Int] or :: Int after the read expression to tell Haskell what type to parse into.
module Main where -- (paste your MinHeap data type and functions here) main :: IO () main = do line <- getLine let nums = map read (words line) :: [Int] let heap = foldl (\h x -> insertHeap x h) Empty nums putStrLn $ "Heap: " ++ show heap putStrLn $ "Size: " ++ show (size heap) putStrLn $ "Min: " ++ show (findMin heap) putStrLn $ "List: " ++ show (heapToList heap) putStrLn $ "isHeap: " ++ show (isHeap heap) putStrLn $ "Even: " ++ show (evenHeap heap) putStrLn $ "Processed: " ++ show (processHeap heap)
Here's everything in one place. This IS your exam prep — the exam will be a variant of these functions.
module Main where data MinHeap a = Empty | Node a (MinHeap a) (MinHeap a) deriving (Show, Eq) -- 1. isEmpty isEmpty :: MinHeap a -> Bool isEmpty Empty = True isEmpty _ = False -- 2. size size :: MinHeap a -> Int size Empty = 0 size (Node _ l r) = 1 + size l + size r -- 3. findMin findMin :: MinHeap a -> a findMin (Node v _ _) = v -- 4. heapToList (preorder) heapToList :: MinHeap a -> [a] heapToList Empty = [] heapToList (Node v l r) = v : heapToList l ++ heapToList r -- 5. isHeap isHeap :: Ord a => MinHeap a -> Bool isHeap Empty = True isHeap (Node v l r) = checkChild v l && checkChild v r && isHeap l && isHeap r where checkChild _ Empty = True checkChild p (Node cv _ _) = p <= cv -- 6. merge (THE key function) merge :: Ord a => MinHeap a -> MinHeap a -> MinHeap a merge Empty h = h merge h Empty = h merge h1@(Node v1 l1 r1) h2@(Node v2 l2 r2) | v1 <= v2 = Node v1 (merge r1 h2) l1 | otherwise = Node v2 (merge h1 r2) l2 -- 7. insertHeap (one-liner using merge) insertHeap :: Ord a => a -> MinHeap a -> MinHeap a insertHeap x heap = merge (Node x Empty Empty) heap -- 8. deleteMin (one-liner using merge) deleteMin :: Ord a => MinHeap a -> MinHeap a deleteMin Empty = Empty deleteMin (Node _ l r) = merge l r -- 9. evenHeap evenHeap :: MinHeap Int -> [Int] evenHeap heap = [x | x <- heapToList heap, even x] -- 10. mapHeap mapHeap :: (a -> a) -> MinHeap a -> MinHeap a mapHeap _ Empty = Empty mapHeap f (Node v l r) = Node (f v) (mapHeap f l) (mapHeap f r) -- 11. processHeap processHeap :: MinHeap Int -> [Int] processHeap heap = [x * x | x <- evenHeap heap] -- 12. main main :: IO () main = do line <- getLine let nums = map read (words line) :: [Int] let heap = foldl (\h x -> insertHeap x h) Empty nums putStrLn $ "Heap: " ++ show heap putStrLn $ "Size: " ++ show (size heap) putStrLn $ "Min: " ++ show (findMin heap) putStrLn $ "List: " ++ show (heapToList heap) putStrLn $ "isHeap: " ++ show (isHeap heap) putStrLn $ "Even: " ++ show (evenHeap heap) putStrLn $ "Processed: " ++ show (processHeap heap)
Write height :: MinHeap a -> Int that returns the height of the heap. Empty has height 0. A single node has height 1. (Uses: tree recursion template — section 9)
-- height (Node 1 (Node 2 Empty Empty) Empty) = 2 -- height Empty = 0
height :: MinHeap a -> Int height Empty = 0 height (Node _ l r) = 1 + max (height l) (height r)
Same template: Empty = base, Node = 1 + max of children. max picks the taller subtree.
Write heapSort :: Ord a => [a] -> [a] that sorts a list using a heap. Insert all elements, then repeatedly extract the minimum. (Uses: foldl, insertHeap, deleteMin, findMin — sections 6, 11, 12)
-- heapSort [3,1,4,1,5] = [1,1,3,4,5]
heapSort :: Ord a => [a] -> [a]
heapSort xs = extractAll (buildHeap xs)
where
buildHeap = foldl (\h x -> insertHeap x h) Empty
extractAll Empty = []
extractAll heap = findMin heap : extractAll (deleteMin heap)
Build a heap with foldl. Then keep pulling the minimum and recursing until empty. This gives you a sorted list!
Write filterHeap :: Ord a => (a -> Bool) -> MinHeap a -> MinHeap a that keeps only elements satisfying a predicate, returning a new valid heap. (Uses: heapToList, filter, foldl, insertHeap — sections 5, 6, 9)
-- filterHeap (>2) (Node 1 (Node 3 Empty Empty) (Node 5 Empty Empty)) -- = Node 3 (Node 5 Empty Empty) Empty
filterHeap :: Ord a => (a -> Bool) -> MinHeap a -> MinHeap a
filterHeap p heap = foldl (\h x -> insertHeap x h) Empty kept
where kept = filter p (heapToList heap)
Convert to list, filter, rebuild. Not efficient, but correct and simple. foldl + insertHeap is the standard way to build a heap from a list.
Write countIf :: (a -> Bool) -> MinHeap a -> Int without converting to a list. (Uses: tree recursion directly — section 9)
-- countIf even (Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty)) = 2
countIf :: (a -> Bool) -> MinHeap a -> Int
countIf _ Empty = 0
countIf p (Node v l r)
| p v = 1 + countIf p l + countIf p r
| otherwise = countIf p l + countIf p r
Tree recursion template + guard. If p v is true, count 1 + children. Otherwise, just count children.