Min Heap in Haskell

What Was Given

A template file (Assignment_5_template.hs) defining a polymorphic min-heap data type and 12 function signatures with = undefined bodies. You must implement all 12 functions. The file also includes doctest-format comments showing expected inputs and outputs for each function.

The data type definition (given)

data MinHeap a = Empty | Node a (MinHeap a) (MinHeap a)
    deriving (Show, Eq)

How to Install & Run

GHC (the Glasgow Haskell Compiler) is not installed on macOS by default. Install it via Homebrew, then load the file in GHCi (the interactive REPL).

# Step 1: Install GHC via Homebrew
brew install ghc

# Step 2: Navigate to the assignment directory
cd /Users/hansrajpatel/Dev-IITG/cs331/cs331_a5_170101025/problem

# Step 3: Load in the GHCi REPL (interactive mode)
ghci Assignment_5_template.hs

# Or compile to a standalone binary:
ghc -o heap Assignment_5_template.hs && ./heap

Testing individual functions in GHCi

Once GHCi loads the file, you get a prompt where you can call any function directly:

-- Test isEmpty
*Assignment_5> isEmpty Empty
True

-- Test insertHeap
*Assignment_5> insertHeap 3 (insertHeap 5 Empty)
Node 3 (Node 5 Empty Empty) Empty

-- Build a heap step by step
*Assignment_5> let h = foldl (flip insertHeap) Empty [5,3,8,1]
*Assignment_5> h
Node 1 (Node 3 (Node 5 Empty Empty) Empty) (Node 8 Empty Empty)

-- Reload after editing the file (no need to quit)
*Assignment_5> :r

The Data Type Explained

Definition

data MinHeap a = Empty | Node a (MinHeap a) (MinHeap a)
    deriving (Show, Eq)

This is an algebraic data type with two constructors:

• Empty — represents an empty heap (a leaf / null node).
• Node a (MinHeap a) (MinHeap a) — a node holding a value of type a, a left subtree, and a right subtree.

Visual examples

-- 1. Empty heap:
Empty                         -- Nothing at all

-- 2. Single-node heap:
Node 1 Empty Empty            --     1
                              --    / \
                              --   .   .       (dots = Empty)

-- 3. Multi-node heap:
Node 1
  (Node 3 Empty Empty)       --       1
  (Node 5 Empty Empty)       --      / \
                              --     3   5

-- 4. Deeper heap (after inserting 1,3,5,8):
Node 1                        --         1
  (Node 3                     --        / \
    (Node 5 Empty Empty)      --       3   8
    Empty)                    --      /
  (Node 8 Empty Empty)       --     5

Key language concepts in this definition

• Polymorphism (a): The type variable a means this heap can hold any type — MinHeap Int, MinHeap String, etc. Functions that compare values require the Ord a constraint.
• Ord constraint: Written as Ord a => before the type. Means a must support <, <=, >, >=. Needed for merge, insertHeap, deleteMin, isHeap.
• deriving (Show, Eq): The compiler auto-generates show (for printing, e.g., Node 1 Empty Empty) and == (for equality comparison). Without this, you could not print heaps in GHCi.

Functions 1–3: isEmpty, size, findMin

These are the simplest functions — straightforward pattern matching on the two constructors.

isEmpty

isEmpty :: MinHeap a -> Bool
isEmpty Empty    = True       -- pattern matches Empty constructor
isEmpty (Node _ _ _) = False  -- anything else is not empty

-- Tests:
> isEmpty Empty
True
> isEmpty (Node 5 Empty Empty)
False

_ is a wildcard — it matches anything but we don't need the value. We have two clauses: one for each constructor of MinHeap.

size

size :: MinHeap a -> Int
size Empty          = 0                  -- base case: empty has 0 elements
size (Node _ l r)   = 1 + size l + size r -- 1 (this node) + left + right

-- Tests:
> size Empty
0
> size (Node 5 (Node 3 Empty Empty) Empty)
2
> size (Node 5 Empty Empty)
1

This is the standard recursive tree-size formula. The _ ignores the node's value since we only care about counting.

findMin

findMin :: MinHeap a -> a
findMin (Node v _ _) = v   -- the root IS the minimum in a min-heap

-- Tests:
> findMin (Node 2 Empty Empty)
2
> findMin (Node 1 (Node 3 Empty Empty) Empty)
1

No Empty case is defined — the assignment says "assume the heap is not empty." Calling findMin Empty will crash with a pattern-match error, which is acceptable.

Function 4: heapToList — Preorder Traversal

Code

heapToList :: MinHeap a -> [a]
heapToList Empty          = []                              -- empty heap = empty list
heapToList (Node v l r)   = [v] ++ heapToList l ++ heapToList r  -- root, left, right

-- Test:
> heapToList (Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty))
[1,2,3]

Why preorder?

Preorder traversal visits: root first, then left subtree, then right subtree. This is the most natural traversal for a heap because the minimum (root) appears first in the resulting list.

Operators used

• [v] — wraps the single value v into a one-element list.
• ++ — list concatenation. [1] ++ [2,3] gives [1,2,3].

An equivalent way to write this uses the cons operator : instead:

heapToList (Node v l r) = v : heapToList l ++ heapToList r  -- : prepends one element

v : xs prepends element v onto list xs. It's more efficient than [v] ++ xs because : is O(1) while ++ is O(n) in the length of the left operand.

Function 5: isHeap — Validate Min-Heap Property

Code

isHeap :: Ord a => MinHeap a -> Bool
isHeap Empty            = True                     -- empty is trivially a valid heap
isHeap (Node v l r)     = check v l && check v r   -- both children must satisfy property
  where
    check _ Empty           = True                 -- empty child is always OK
    check parent (Node cv cl cr)
      = parent <= cv                              -- parent must be <= child value
        && check cv cl                             -- recurse: child becomes parent for its children
        && check cv cr

-- Tests:
> isHeap (Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty))
True
> isHeap (Node 5 (Node 2 Empty Empty) Empty)
False   -- 5 > 2, violates min-heap property

How it works

1. An empty heap is trivially valid.
2. For a Node v l r, we use a helper function check defined in a where block.
3. check parent child verifies that the parent value is <= the child's value, then recurses on the child's own children.
4. Both left and right subtrees must pass (&& = logical AND).

Function 6: merge — The Key Function

This is the most important and hardest function in the assignment. Everything else (insertHeap, deleteMin) is built on top of merge.

Code

merge :: Ord a => MinHeap a -> MinHeap a -> MinHeap a
merge Empty h2 = h2                                -- merging with empty returns the other
merge h1 Empty = h1                                -- same, symmetric case
merge h1@(Node v1 l1 r1) h2@(Node v2 l2 r2)
  | v1 <= v2   = Node v1 (merge r1 h2) l1         -- v1 is smaller: keep v1 as root
  | otherwise   = Node v2 (merge r2 h1) l2         -- v2 is smaller: keep v2 as root

Step-by-step walkthrough

1. Base cases: If either heap is Empty, the result is the other heap. Nothing to merge.
2. Compare roots: If v1 <= v2, the smaller value v1 becomes the new root (preserving the min-heap property).
3. Recursive merge: We merge the right subtree (r1) with the entire other heap (h2). This pushes the heavier work into one subtree.
4. Swap children for balance: The result of the merge becomes the left child, and the original left subtree (l1) becomes the right child. This left-biased swapping keeps the tree roughly balanced over many operations.

Visual example

-- merge (Node 2 Empty Empty) (Node 5 Empty Empty)
-- v1=2, v2=5. Since 2 <= 5:
--   root = 2
--   left = merge Empty (Node 5 Empty Empty) = Node 5 Empty Empty
--   right = Empty  (was l1)
-- Result:
Node 2 (Node 5 Empty Empty) Empty
--       2
--      / \
--     5   .

The @ pattern syntax (as-pattern)

merge h1@(Node v1 l1 r1) h2@(Node v2 l2 r2)
--    ^^                  ^^
-- h1 binds to the ENTIRE first heap
-- (Node v1 l1 r1) destructures it into parts
-- We get BOTH: the whole thing AND the pieces

The @ (read "as") lets you bind a name to the entire value while also pattern-matching its internals. We need h1 and h2 as wholes (to pass into the recursive call) and their parts (to extract v1, l1, r1).

Functions 7–8: insertHeap & deleteMin

Both are elegant one-liners that delegate to merge. This is the power of defining a good merge operation.

insertHeap

insertHeap :: Ord a => a -> MinHeap a -> MinHeap a
insertHeap x heap = merge (Node x Empty Empty) heap  -- insert = merge a singleton

-- Test:
> insertHeap 2 (Node 5 Empty Empty)
Node 2 (Node 5 Empty Empty) Empty

Why it works: A single element is just a one-node heap: Node x Empty Empty. Merging it with the existing heap places x in the correct position, maintaining the min-heap property. The merge function handles all the comparison and restructuring logic.

deleteMin

deleteMin :: Ord a => MinHeap a -> MinHeap a
deleteMin (Node _ l r) = merge l r  -- remove root, merge its two children

-- Test:
> deleteMin (Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty))
Node 2 (Node 3 Empty Empty) Empty

Why it works: The minimum is always the root. To remove it, we just discard it (the _) and merge the left and right subtrees back together. The merge ensures the next-smallest element rises to the new root.

Functions 9–11: evenHeap, mapHeap, processHeap

These demonstrate list comprehensions and higher-order functions in Haskell.

evenHeap — Extract even elements

evenHeap :: MinHeap Int -> [Int]
evenHeap heap = [x | x <- heapToList heap, even x]  -- list comprehension with filter

-- Test:
> evenHeap (Node 1 (Node 2 Empty Empty) (Node 4 Empty Empty))
[2,4]

How it works: First, heapToList heap converts the heap to a flat list via preorder traversal. Then the list comprehension [x | x <- list, even x] filters to keep only even numbers. Read it as: "give me every x from the list where x is even."

mapHeap — Apply a function to every element

mapHeap :: (a -> a) -> MinHeap a -> MinHeap a
mapHeap _ Empty          = Empty                        -- nothing to map over
mapHeap f (Node v l r)   = Node (f v) (mapHeap f l) (mapHeap f r)  -- apply f to each node

-- Tests:
> mapHeap (*2) (Node 1 Empty Empty)
Node 2 Empty Empty
> mapHeap (*2) (Node 1 (Node 4 Empty Empty) Empty)
Node 2 (Node 8 Empty Empty) Empty

How it works: This is like Haskell's built-in map for lists, but for our tree structure. Apply f to the current node's value, then recurse on both subtrees. (*2) is a section — a partially applied operator meaning "multiply by 2."

processHeap — Filter evens, then square them

processHeap :: MinHeap Int -> [Int]
processHeap heap = [x * x | x <- heapToList heap, even x]  -- filter + transform in one

-- Test:
> processHeap (Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty))
[4,16]   -- 2^2=4, 4^2=16 (3 is odd, skipped)

This combines evenHeap's filtering with a transformation. The list comprehension [x * x | x <- ..., even x] reads: "give me x squared for each x from the list where x is even."

Function 12: main — Interactive IO

The main function reads numbers from stdin, builds a heap, and prints results. This introduces Haskell's IO monad and do notation.

Code

main :: IO ()
main = do
    putStrLn "Enter numbers separated by spaces:"
    input <- getLine                                     -- read a line of input
    let nums = map read (words input) :: [Int]           -- parse into list of Int
    let heap = foldl (flip insertHeap) Empty nums        -- build heap by inserting each
    putStrLn ("Heap: " ++ show heap)
    putStrLn ("Size: " ++ show (size heap))
    putStrLn ("Min: " ++ show (findMin heap))
    putStrLn ("Heap as list: " ++ show (heapToList heap))
    putStrLn ("Is valid heap: " ++ show (isHeap heap))
    putStrLn ("Even elements: " ++ show (evenHeap heap))
    putStrLn ("Processed (even squared): " ++ show (processHeap heap))

Line-by-line explanation

1. do notation: Lets you write sequential IO actions that look imperative. Each line is an action executed in order.
2. putStrLn: Prints a string followed by a newline.
3. input <- getLine: Reads one line from stdin. The <- arrow extracts the String from the IO String action.
4. words input: Splits the string by whitespace. words "5 3 8 1" gives ["5","3","8","1"].
5. map read: Applies read to each string, converting it to an Int. The :: [Int] type annotation tells Haskell what type to parse into.
6. foldl (flip insertHeap) Empty nums: This is the key line. It builds the heap by folding over the list of numbers:
   • foldl processes the list left-to-right, accumulating a result.
   • Starts with Empty as the initial accumulator.
   • flip insertHeap swaps the arguments: insertHeap takes (value, heap) but foldl provides (heap, value), so flip fixes the order.
7. show: Converts any Show-able value to a String. Works because we derived Show for MinHeap.

Complete Implementation

All 12 functions together, ready to copy into Assignment_5.hs.

module Assignment_5 where

-- | A simple polymorphic Min Heap
data MinHeap a = Empty | Node a (MinHeap a) (MinHeap a)
    deriving (Show, Eq)


-- | Check whether the heap is empty.
isEmpty :: MinHeap a -> Bool
isEmpty Empty        = True
isEmpty (Node _ _ _) = False


-- | Compute the total number of elements in the heap.
size :: MinHeap a -> Int
size Empty        = 0
size (Node _ l r) = 1 + size l + size r


-- | Return the minimum element (root) of the heap.
findMin :: MinHeap a -> a
findMin (Node v _ _) = v


-- | Convert the heap into a list using preorder traversal.
heapToList :: MinHeap a -> [a]
heapToList Empty        = []
heapToList (Node v l r) = v : heapToList l ++ heapToList r


-- | Check whether a heap satisfies the min-heap property.
isHeap :: Ord a => MinHeap a -> Bool
isHeap Empty        = True
isHeap (Node v l r) = check v l && check v r
  where
    check _ Empty              = True
    check parent (Node cv cl cr) =
        parent <= cv && check cv cl && check cv cr


-- | Merge two heaps into one, maintaining the heap property.
merge :: Ord a => MinHeap a -> MinHeap a -> MinHeap a
merge Empty h2 = h2
merge h1 Empty = h1
merge h1@(Node v1 l1 r1) h2@(Node v2 l2 r2)
  | v1 <= v2   = Node v1 (merge r1 h2) l1
  | otherwise   = Node v2 (merge r2 h1) l2


-- | Insert an element into the heap.
insertHeap :: Ord a => a -> MinHeap a -> MinHeap a
insertHeap x heap = merge (Node x Empty Empty) heap


-- | Delete the minimum element (root) from the heap.
deleteMin :: Ord a => MinHeap a -> MinHeap a
deleteMin (Node _ l r) = merge l r


-- | Return all even elements from the heap.
evenHeap :: MinHeap Int -> [Int]
evenHeap heap = [x | x <- heapToList heap, even x]


-- | Apply a function to every element in the heap.
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)


-- | Extract even elements and square them.
processHeap :: MinHeap Int -> [Int]
processHeap heap = [x * x | x <- heapToList heap, even x]


-- | Interactive program: read numbers, build heap, print results.
main :: IO ()
main = do
    putStrLn "Enter numbers separated by spaces:"
    input <- getLine
    let nums = map read (words input) :: [Int]
    let heap = foldl (flip insertHeap) Empty nums
    putStrLn ("Heap: " ++ show heap)
    putStrLn ("Size: " ++ show (size heap))
    putStrLn ("Min: " ++ show (findMin heap))
    putStrLn ("Heap as list: " ++ show (heapToList heap))
    putStrLn ("Is valid heap: " ++ show (isHeap heap))
    putStrLn ("Even elements: " ++ show (evenHeap heap))
    putStrLn ("Processed (even squared): " ++ show (processHeap heap))

Key Concepts for Viva