H
Haskell: List Operations
Exam Intel Practice -- Reversal, manipulation, sorting, and more

Table of Contents

01 List Reversal -- Three Ways 02 Find First Occurrence (Exam Topic) 03 The Accumulator Pattern 04 zip & unzip 05 take, drop, splitAt 06 List Rotation 07 Palindrome Check 08 Interleave Two Lists 09 Run-Length Encoding 10 Insertion Sort 11 Merge Two Sorted Lists 12 DOMjudge I/O Template 13 Practice Problems

1. List Reversal -- Three Ways (EXAM TOPIC)

This was literally on the exam. You must know all three approaches cold. Each one teaches a different fundamental Haskell concept.

Approach A: Naive Recursive

The most intuitive version. Peel off the head, reverse the tail, then stick the head at the end.

myReverse :: [a] -> [a]
myReverse []     = []
myReverse (x:xs) = myReverse xs ++ [x]
O(n^2) because ++ traverses the entire left list each time it is called. Fine for small lists and exams, but know the better way.

Approach B: Accumulator Version (O(n))

Use a helper function go that carries an accumulator. Each element is consed onto the front of the accumulator, naturally reversing the order.

myReverse :: [a] -> [a]
myReverse xs = go xs []
  where
    go []     acc = acc
    go (x:xs) acc = go xs (x:acc)
Trace: myReverse [1,2,3]
go [1,2,3] []
go [2,3] [1]
go [3] [2,1]
go [] [3,2,1]
= [3,2,1]
Mnemonic: Stacking Plates
Take plates off one stack, put each on a new stack. When done, the new stack is reversed.

Approach C: foldl Version

foldl processes the list left-to-right. At each step, we cons the current element onto the front of the accumulator. Since the last element processed ends up at the front, the list gets reversed.

myReverse :: [a] -> [a]
myReverse = foldl (flip (:)) []
-- or equivalently:
-- myReverse = foldl (\acc x -> x:acc) []

flip (:) takes acc and x, and returns x:acc. This is exactly what the accumulator version does, just written point-free.

Three Reversal Recipes
  • Naive: myReverse xs ++ [x] -- easy to write, O(n^2)
  • Accumulator: go + where -- O(n), tail-recursive
  • foldl: foldl (flip (:)) [] -- one-liner, same O(n) behavior

Try It — Copy & Test

-- === Save as reverse.hs ===

-- Approach A: Naive Recursive
rev1 :: [a] -> [a]
rev1 []     = []
rev1 (x:xs) = rev1 xs ++ [x]

-- Approach B: Accumulator
rev2 :: [a] -> [a]
rev2 xs = go xs []
  where
    go []     acc = acc
    go (x:xs) acc = go xs (x:acc)

-- Approach C: foldl
rev3 :: [a] -> [a]
rev3 = foldl (flip (:)) []

-- === Test in GHCi ===
-- $ ghci reverse.hs

ghci> rev1 [1,2,3,4,5]
[5,4,3,2,1]

ghci> rev2 "hello"
"olleh"

ghci> rev3 []
[]

2. Find First Occurrence (Session 2 Exam Topic)

Session 2 asked: “Given a list and a number, find the first occurrence of that number.” The main challenge was I/O. Here are three ways to implement it:

Naive Recursive Version

findIndex :: Eq a => a -> [a] -> Int
findIndex _ [] = -1
findIndex x (y:ys)
    | x == y    = 0
    | otherwise = let idx = findIndex x ys
                  in if idx == -1 then -1 else 1 + idx
This works but is awkward — the if idx == -1 check is error-prone. The accumulator version below is cleaner.

Accumulator Version (Recommended)

findIndex :: Eq a => a -> [a] -> Int
findIndex x xs = go xs 0
  where
    go [] _     = -1
    go (y:ys) i
        | x == y    = i
        | otherwise = go ys (i + 1)
Mental Trace: findIndex 7 [3, 5, 7, 9]
go [3,5,7,9] 0 → 3 /= 7, so go [5,7,9] 1
go [5,7,9] 1 → 5 /= 7, so go [7,9] 2
go [7,9] 2 → 7 == 7, return 2

Using Data.List (if imports are allowed)

import Data.List (elemIndex)
import Data.Maybe (fromMaybe)

-- elemIndex returns Maybe Int
-- elemIndex 7 [3,5,7,9] = Just 2
-- elemIndex 1 [3,5,7,9] = Nothing

findIndex :: Eq a => a -> [a] -> Int
findIndex x xs = fromMaybe (-1) (elemIndex x xs)
DOMjudge may or may not allow Data.List imports. Always have the manual version ready. If the exam template already imports it, great. If not, write your own.

The I/O Part (Where People Struggled)

The exam gives input like: a list on line 1, target on line 2. You need to read both and print the index.

import System.IO

main :: IO ()
main = do
    line1 <- getLine                          -- "3 5 7 9"
    line2 <- getLine                          -- "7"
    let xs     = map read (words line1) :: [Int]  -- [3, 5, 7, 9]
        target = read line2 :: Int               -- 7
    print (findIndex target xs)               -- 2
I/O Gotchas Cheatsheet
  • getLine returns a String — you must read to convert to Int
  • words "3 5 7" gives ["3","5","7"] — splits on spaces
  • map read (words line) :: [Int] — the type annotation is REQUIRED or Haskell won’t know what to parse
  • print x = putStrLn (show x) — use for numbers
  • putStrLn for strings, print for numbers
  • Use <- for I/O actions, let for pure computations inside do
Memory Anchor: The I/O Recipe
Every DOMjudge Haskell solution follows the same skeleton:
1. getLine to read raw strings
2. let ... = map read (words line) :: [Int] to parse
3. Call your pure function on the parsed data
4. print or putStrLn the result
The pure function is the easy part. The I/O wrapper is what trips people up.

Try It — Copy & Test

-- === Save as find_index.hs ===

findIndex :: Eq a => a -> [a] -> Int
findIndex x xs = go xs 0
  where
    go [] _     = -1
    go (y:ys) i
        | x == y    = i
        | otherwise = go ys (i + 1)

-- === Test in GHCi ===
-- $ ghci find_index.hs

ghci> findIndex 7 [3, 5, 7, 9]
2

ghci> findIndex 1 [3, 5, 7, 9]
-1

ghci> findIndex 3 [3, 5, 7, 9]
0

3. The Accumulator Pattern

The accumulator is THE most important Haskell pattern for exam problems. Almost every list-processing function can be written this way. Learn the template and you can derive any function on the spot.

General Template

myFunction xs = go xs initialValue
  where
    go []     acc = acc  -- or some transformation of acc
    go (x:xs) acc = go xs (combine x acc)

The idea: carry a running result (acc) through the recursion. At each step, combine the current element with the accumulator. When the list is empty, the accumulator holds the final answer.

Reverse (you already saw this)

myReverse xs = go xs []
  where
    go []     acc = acc
    go (x:xs) acc = go xs (x:acc)

Length

myLength :: [a] -> Int
myLength xs = go xs 0
  where
    go []     n = n
    go (_:xs) n = go xs (n + 1)

Sum

mySum :: Num a => [a] -> a
mySum xs = go xs 0
  where
    go []     s = s
    go (x:xs) s = go xs (s + x)

Product

myProduct :: Num a => [a] -> a
myProduct xs = go xs 1
  where
    go []     p = p
    go (x:xs) p = go xs (p * x)
The accumulator is a snowball rolling downhill. Each element adds to it. When you reach the bottom (empty list), the snowball IS your answer.
Accumulator Pattern Checklist
  • Pick your initial value: 0 for sum/length, 1 for product, [] for reverse
  • Pick your combine function: (+) for sum, (*) for product, (:) for reverse
  • Base case returns the accumulator (or a transformation of it)
  • Recursive case calls go on the tail with updated accumulator

Try It — Copy & Test

-- === Save as accum.hs ===

myLength :: [a] -> Int
myLength xs = go xs 0
  where
    go []     n = n
    go (_:xs) n = go xs (n + 1)

mySum :: Num a => [a] -> a
mySum xs = go xs 0
  where
    go []     s = s
    go (x:xs) s = go xs (s + x)

myProduct :: Num a => [a] -> a
myProduct xs = go xs 1
  where
    go []     p = p
    go (x:xs) p = go xs (p * x)

-- === Test in GHCi ===
-- $ ghci accum.hs

ghci> myLength [1,2,3,4]
4

ghci> mySum [1,2,3,4]
10

ghci> myProduct [1,2,3,4]
24

4. zip & unzip

zip pairs up corresponding elements from two lists. It stops at the shorter list. unzip is the inverse: it splits a list of pairs into two separate lists.

myZip

myZip :: [a] -> [b] -> [(a,b)]
myZip [] _          = []
myZip _ []          = []
myZip (x:xs) (y:ys) = (x,y) : myZip xs ys

Note the two base cases: if either list is empty, we stop. This means zip always produces a list whose length equals the shorter input.

Trace: myZip [1,2,3] ["a","b"]
myZip [1,2,3] ["a","b"]
= (1,"a") : myZip [2,3] ["b"]
= (1,"a") : (2,"b") : myZip [3] []
= (1,"a") : (2,"b") : []
= [(1,"a"), (2,"b")]

myUnzip

myUnzip :: [(a,b)] -> ([a],[b])
myUnzip []         = ([], [])
myUnzip ((a,b):ps) = (a:as, b:bs)
  where (as, bs) = myUnzip ps

The where clause pattern-matches on the recursive result. We extract both halves and cons the current pair's components onto each.

Key Points
  • zip stops at the shorter list -- no index-out-of-bounds errors
  • unzip uses pattern matching in where to split the recursive result
  • unzip . zip does NOT always give you back the originals (if lengths differ)

Try It — Copy & Test

-- === Save as zip_unzip.hs ===

myZip :: [a] -> [b] -> [(a,b)]
myZip [] _          = []
myZip _ []          = []
myZip (x:xs) (y:ys) = (x,y) : myZip xs ys

myUnzip :: [(a,b)] -> ([a],[b])
myUnzip []         = ([], [])
myUnzip ((a,b):ps) = (a:as, b:bs)
  where (as, bs) = myUnzip ps

-- === Test in GHCi ===
-- $ ghci zip_unzip.hs

ghci> myZip [1,2,3] ["a","b","c"]
[(1,"a"),(2,"b"),(3,"c")]

ghci> myZip [1,2] [10,20,30]
[(1,10),(2,20)]

ghci> myUnzip [(1,'a'),(2,'b')]
([1,2],"ab")

5. take, drop, splitAt

These three functions are building blocks for many list operations. They split a list at a given index.

myTake

myTake :: Int -> [a] -> [a]
myTake _ []     = []
myTake 0 _      = []
myTake n (x:xs) = x : myTake (n-1) xs

myDrop

myDrop :: Int -> [a] -> [a]
myDrop _ []     = []
myDrop 0 xs     = xs
myDrop n (_:xs) = myDrop (n-1) xs

mySplitAt

mySplitAt :: Int -> [a] -> ([a],[a])
mySplitAt n xs = (myTake n xs, myDrop n xs)

Note the defensive base cases: both myTake and myDrop handle the empty list first, so you never crash on short inputs. If n exceeds the list length, take returns the whole list and drop returns [].

Trace: myTake 2 [10,20,30,40]
myTake 2 [10,20,30,40]
= 10 : myTake 1 [20,30,40]
= 10 : 20 : myTake 0 [30,40]
= 10 : 20 : []
= [10,20]
Pattern Summary
  • take -- keep the first n, discard the rest
  • drop -- discard the first n, keep the rest
  • splitAt n xs == (take n xs, drop n xs)
  • Both are safe on short lists: no crashes, just shorter results

Try It — Copy & Test

-- === Save as take_drop.hs ===

myTake :: Int -> [a] -> [a]
myTake _ []     = []
myTake 0 _      = []
myTake n (x:xs) = x : myTake (n-1) xs

myDrop :: Int -> [a] -> [a]
myDrop _ []     = []
myDrop 0 xs     = xs
myDrop n (_:xs) = myDrop (n-1) xs

mySplitAt :: Int -> [a] -> ([a],[a])
mySplitAt n xs = (myTake n xs, myDrop n xs)

-- === Test in GHCi ===
-- $ ghci take_drop.hs

ghci> myTake 3 [1,2,3,4,5]
[1,2,3]

ghci> myDrop 2 [1,2,3,4,5]
[3,4,5]

ghci> mySplitAt 3 [1,2,3,4,5]
([1,2,3],[4,5])

6. List Rotation

Rotation moves the first n elements to the end. It combines take and drop in a clever way.

rotate :: Int -> [a] -> [a]
rotate _ [] = []
rotate n xs = drop m xs ++ take m xs
  where m = n `mod` length xs

The mod ensures we handle rotations larger than the list length. Rotating by length xs gives back the original list.

Trace: rotate 2 [1,2,3,4,5]
m = 2 `mod` 5 = 2
drop 2 [1,2,3,4,5] = [3,4,5]
take 2 [1,2,3,4,5] = [1,2]
result = [3,4,5] ++ [1,2]
= [3,4,5,1,2]
rotate n xs = drop n xs ++ take n xs (with mod for safety)

Try It — Copy & Test

-- === Save as rotate.hs ===

myTake :: Int -> [a] -> [a]
myTake _ []     = []
myTake 0 _      = []
myTake n (x:xs) = x : myTake (n-1) xs

myDrop :: Int -> [a] -> [a]
myDrop _ []     = []
myDrop 0 xs     = xs
myDrop n (_:xs) = myDrop (n-1) xs

rotate :: Int -> [a] -> [a]
rotate _ [] = []
rotate n xs = myDrop m xs ++ myTake m xs
  where m = n `mod` length xs

-- === Test in GHCi ===
-- $ ghci rotate.hs

ghci> rotate 2 [1,2,3,4,5]
[3,4,5,1,2]

ghci> rotate 0 [1,2,3]
[1,2,3]

ghci> rotate 7 [1,2,3,4,5]
[3,4,5,1,2]

7. Palindrome Check

A palindrome reads the same forwards and backwards. The Haskell solution is beautifully simple.

isPalindrome :: Eq a => [a] -> Bool
isPalindrome xs = xs == reverse xs

Or, if you want to use your own reverse:

isPalindrome :: Eq a => [a] -> Bool
isPalindrome xs = xs == myReverse xs
  where
    myReverse = foldl (flip (:)) []
Important Detail
  • Note the Eq a => type class constraint -- we need equality comparison on elements
  • Without Eq, there is no way to compare list elements, so == would not compile
  • Works on strings too: isPalindrome "racecar" returns True

Try It — Copy & Test

-- === Save as palindrome.hs ===

isPalindrome :: Eq a => [a] -> Bool
isPalindrome xs = xs == reverse xs

-- === Test in GHCi ===
-- $ ghci palindrome.hs

ghci> isPalindrome [1,2,3,2,1]
True

ghci> isPalindrome "racecar"
True

ghci> isPalindrome [1,2,3]
False

8. Interleave Two Lists

Interleaving alternates elements from two lists. When one list runs out, the remainder of the other list is appended.

interleave :: [a] -> [a] -> [a]
interleave [] ys     = ys
interleave xs []     = xs
interleave (x:xs) (y:ys) = x : y : interleave xs ys
Trace: interleave [1,3,5] [2,4]
interleave [1,3,5] [2,4]
= 1 : 2 : interleave [3,5] [4]
= 1 : 2 : 3 : 4 : interleave [5] []
= 1 : 2 : 3 : 4 : [5]
= [1,2,3,4,5]

Notice how the third base case (interleave xs []) handles different-length lists gracefully by returning the remaining elements of the non-empty list.

Key Points
  • Two base cases handle either list being empty -- no elements lost
  • The recursive case takes one from each list per step
  • Unlike zip, interleave preserves all elements from both lists

Try It — Copy & Test

-- === Save as interleave.hs ===

interleave :: [a] -> [a] -> [a]
interleave [] ys     = ys
interleave xs []     = xs
interleave (x:xs) (y:ys) = x : y : interleave xs ys

-- === Test in GHCi ===
-- $ ghci interleave.hs

ghci> interleave [1,2,3] [10,20,30]
[1,10,2,20,3,30]

ghci> interleave [1,2] [10,20,30,40]
[1,10,2,20,30,40]

ghci> interleave [] [1,2,3]
[1,2,3]

9. Run-Length Encoding

Run-length encoding compresses consecutive duplicate elements into (count, element) pairs. This is a classic exam problem.

Encode

encode :: Eq a => [a] -> [(Int, a)]
encode [] = []
encode (x:xs) = (1 + length prefix, x) : encode rest
  where (prefix, rest) = span (== x) xs

span is the key function here. span (== x) xs splits xs into two parts: a prefix of elements equal to x, and the rest. For example, span (== 'a') "aab" gives ("aa", "b"). We add 1 to the prefix length because x itself is the first occurrence.

Trace: encode "aaabbc"
encode "aaabbc"
span (== 'a') "aabbc" = ("aa", "bbc")
= (3, 'a') : encode "bbc"
span (== 'b') "bc" = ("b", "c")
= (3, 'a') : (2, 'b') : encode "c"
span (== 'c') "" = ("", "")
= (3, 'a') : (2, 'b') : (1, 'c') : encode ""
= [(3,'a'), (2,'b'), (1,'c')]

Decode

decode :: [(Int, a)] -> [a]
decode [] = []
decode ((n,x):rest) = replicate n x ++ decode rest

replicate n x creates a list of n copies of x. For example, replicate 3 'a' gives "aaa". We concatenate each expanded run and recurse on the rest.

Key Functions
  • span p xs -- splits list into (longest prefix satisfying p, the rest)
  • replicate n x -- creates a list of n copies of x
  • decode . encode == id for any list (round-trip property)
span splits, replicate repeats

Try It — Copy & Test

-- === Save as rle.hs ===

encode :: Eq a => [a] -> [(Int, a)]
encode [] = []
encode (x:xs) = (1 + length prefix, x) : encode rest
  where (prefix, rest) = span (== x) xs

decode :: [(Int, a)] -> [a]
decode [] = []
decode ((n,x):rest) = replicate n x ++ decode rest

-- === Test in GHCi ===
-- $ ghci rle.hs

ghci> encode "aaabbbcc"
[(3,'a'),(3,'b'),(2,'c')]

ghci> encode [1,1,2,3,3,3]
[(2,1),(1,2),(3,3)]

ghci> decode [(3,'a'),(2,'b'),(1,'c')]
"aaabbc"

10. Insertion Sort

Insertion sort in Haskell is elegant: recursively sort the tail, then insert the head into the correct position.

insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = insert x (insertionSort xs)

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
    | x <= y    = x : y : ys
    | otherwise = y : insert x ys

insert walks along a sorted list until it finds the right spot, then places the element there. insertionSort builds up the sorted list one element at a time from right to left.

Trace: insertionSort [3,1,4,2]
insertionSort [3,1,4,2]
= insert 3 (insertionSort [1,4,2])
= insert 3 (insert 1 (insertionSort [4,2]))
= insert 3 (insert 1 (insert 4 (insertionSort [2])))
= insert 3 (insert 1 (insert 4 [2]))
= insert 3 (insert 1 [2,4]) -- 4 > 2, so [2,4]
= insert 3 [1,2,4] -- 1 <= 2, so [1,2,4]
= [1,2,3,4] -- 3 <= 4, so [1,2,3,4]
= [1,2,3,4]
Mnemonic: Sorting Playing Cards
Like sorting a hand of playing cards -- pick up each card and slide it into the right spot in the already-sorted portion.
O(n^2) worst case, but perfectly fine for exam-sized inputs. On the exam, clarity beats performance.

Try It — Copy & Test

-- === Save as sort.hs ===

insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = insert x (insertionSort xs)

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
    | x <= y    = x : y : ys
    | otherwise = y : insert x ys

-- === Test in GHCi ===
-- $ ghci sort.hs

ghci> insertionSort [3,1,4,1,5,9,2,6]
[1,1,2,3,4,5,6,9]

ghci> insertionSort "hello"
"ehllo"

ghci> insert 4 [1,3,5,7]
[1,3,4,5,7]

11. Merge Two Sorted Lists

Merging two already-sorted lists into one sorted list. Compare the heads, take the smaller one, and recurse.

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
    | x <= y    = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys
Trace: merge [1,3,5] [2,4,6]
merge [1,3,5] [2,4,6]
= 1 : merge [3,5] [2,4,6] -- 1 <= 2
= 1 : 2 : merge [3,5] [4,6] -- 3 > 2
= 1 : 2 : 3 : merge [5] [4,6] -- 3 <= 4
= 1 : 2 : 3 : 4 : merge [5] [6] -- 5 > 4
= 1 : 2 : 3 : 4 : 5 : merge [] [6] -- 5 <= 6
= 1 : 2 : 3 : 4 : 5 : [6]
= [1,2,3,4,5,6]
This is the same merge you saw in MinHeap! Same pattern -- compare heads, take the smaller, recurse. The only difference is that here we are working with linked lists instead of arrays.
Key Points
  • O(n + m) where n and m are the lengths of the two lists
  • Both inputs must already be sorted for the result to be sorted
  • This is the merge step of merge sort
  • The base cases handle when either list runs out -- just return the other

Try It — Copy & Test

-- === Save as merge.hs ===

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
    | x <= y    = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

-- === Test in GHCi ===
-- $ ghci merge.hs

ghci> merge [1,3,5] [2,4,6]
[1,2,3,4,5,6]

ghci> merge [1,2,3] []
[1,2,3]

ghci> merge [1,1] [1,2]
[1,1,1,2]

12. DOMjudge I/O Template

DOMjudge problems require reading from stdin and writing to stdout. Here are the patterns you need.

Read a Single Line of Space-Separated Integers

import System.IO

main :: IO ()
main = do
    line <- getLine
    let nums = map read (words line) :: [Int]
    -- process nums
    putStrLn (unwords (map show result))

Read Multiple Lines Until EOF

import System.IO

main :: IO ()
main = do
    contents <- getContents
    let allLines = lines contents
    let results = map processLine allLines
    mapM_ putStrLn results

processLine :: String -> String
processLine line = let nums = map read (words line) :: [Int]
                   in show (sum nums)  -- example: sum each line

Read First Line as Count, Then That Many Lines

main :: IO ()
main = do
    n <- readLn :: IO Int
    inputLines <- sequence (replicate n getLine)
    let nums = map (\l -> map read (words l) :: [Int]) inputLines
    -- nums is [[Int]], one list per line
    mapM_ print (map processLine nums)
I/O Cheat Sheet
  • getLine -- read one line as String
  • getContents -- read all of stdin as one String (lazy)
  • words -- split string on whitespace into [String]
  • lines -- split string on newlines into [String]
  • read -- parse a String into a number (needs type annotation)
  • show -- convert a value to String
  • unwords / unlines -- join with spaces / newlines
  • mapM_ -- apply an IO action to each element in a list

Pattern: List on Line 1, Target on Line 2

This was the Session 2 exam pattern. Read a list and a single value separately.

main :: IO ()
main = do
    line1 <- getLine
    line2 <- getLine
    let xs     = map read (words line1) :: [Int]
        target = read line2 :: Int
    -- now use xs and target
    print (someFunction target xs)

Pattern: Number of Elements First, Then the List

Some problems give N on line 1, then N numbers on line 2.

main :: IO ()
main = do
    nStr <- getLine
    let n = read nStr :: Int
    line <- getLine
    let xs = take n (map read (words line) :: [Int])
    -- process xs
    print (someFunction xs)

Pattern: Multiple Lines of Input

main :: IO ()
main = do
    contents <- getContents              -- read ALL stdin at once
    let allLines = lines contents         -- split into lines
        nums = map read allLines :: [Int] -- parse each line as Int
    -- process nums
    mapM_ print (someFunction nums)

Try It — Copy & Test

-- === Save as solution.hs, compile & run ===
-- $ ghc -o solution solution.hs
-- $ echo "1 2 3 4 5" | ./solution

-- Or run interactively:
-- $ runghc solution.hs
-- (then type input and press Enter)

13. Practice Problems

Try each of these without looking at the solution. Write the code on paper if you can -- that is what the exam demands.

Problem 1: Reverse with Accumulator

Implement myReverse :: [a] -> [a] using an accumulator. Do NOT use ++.

Test: myReverse [1,2,3,4,5] = [5,4,3,2,1]
Show Solution 
myReverse :: [a] -> [a]
myReverse xs = go xs []
  where
    go []     acc = acc
    go (x:xs) acc = go xs (x:acc)

The accumulator starts empty. Each element is consed onto the front, naturally reversing the order. This runs in O(n) because (:) is O(1).

Problem 2: Implement zip

Write myZip :: [a] -> [b] -> [(a,b)] that pairs up corresponding elements from two lists. Stop at the shorter list.

Test: myZip [1,2,3] ["a","b"] = [(1,"a"),(2,"b")]
Show Solution 
myZip :: [a] -> [b] -> [(a,b)]
myZip [] _          = []
myZip _ []          = []
myZip (x:xs) (y:ys) = (x,y) : myZip xs ys

Two base cases handle either list being empty. The recursive case pairs the heads and recurses on the tails.

Problem 3: Rotate a List

Write rotate :: Int -> [a] -> [a] that rotates a list left by n positions.

Test: rotate 2 [1,2,3,4,5] = [3,4,5,1,2]
Show Solution 
rotate :: Int -> [a] -> [a]
rotate _ [] = []
rotate n xs = drop m xs ++ take m xs
  where m = n `mod` length xs

drop m gives everything after the first m elements, and take m gives the first m elements. Concatenating them achieves the rotation. The mod handles cases where n is larger than the list length.

Problem 4: Run-Length Encoding

Write encode :: Eq a => [a] -> [(Int, a)] that compresses consecutive duplicates into (count, element) pairs.

Test: encode "aaabbc" = [(3,'a'),(2,'b'),(1,'c')]
Show Solution 
encode :: Eq a => [a] -> [(Int, a)]
encode [] = []
encode (x:xs) = (1 + length prefix, x) : encode rest
  where (prefix, rest) = span (== x) xs

span (== x) xs splits xs into a prefix of elements equal to x and the rest. We add 1 to the prefix length to count x itself (the head we already removed).

Problem 5: Insertion Sort

Write insertionSort :: Ord a => [a] -> [a] and the helper insert :: Ord a => a -> [a] -> [a].

Test: insertionSort [3,1,4,1,5,9,2,6] = [1,1,2,3,4,5,6,9]
Show Solution 
insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = insert x (insertionSort xs)

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
    | x <= y    = x : y : ys
    | otherwise = y : insert x ys

insertionSort recursively sorts the tail, then inserts the head into its correct position. insert walks along the sorted list, comparing until it finds the right spot.

Problem 6: Check if Sorted

Write isSorted :: Ord a => [a] -> Bool that checks whether a list is in non-decreasing order. Do NOT use sort.

Test: isSorted [1,2,3,4] = True  |  isSorted [1,3,2] = False

Hint: Compare adjacent pairs. A list with 0 or 1 elements is always sorted.

Show Solution 
isSorted :: Ord a => [a] -> Bool
isSorted []       = True
isSorted [_]      = True
isSorted (x:y:xs) = x <= y && isSorted (y:xs)

Base cases: empty list and single-element list are trivially sorted. Recursive case: check that the first two elements are in order, then recurse with the second element still at the head (so we compare every adjacent pair).

Alternative using zip:

isSorted :: Ord a => [a] -> Bool
isSorted xs = and (zipWith (<=) xs (tail xs))

zipWith (<=) xs (tail xs) produces a list of Bools, one for each adjacent pair. and returns True only if all of them are True.

Problem 7: Find First Occurrence

Write findIndex :: Eq a => a -> [a] -> Int that returns the 0-based index of the first occurrence, or -1 if not found. Then write a main that reads a list of integers (line 1) and a target (line 2), and prints the result.

-- Input:    -- Output:
-- 10 20 30 40 50    -- 2
-- 30
Show Solution 
findIndex :: Eq a => a -> [a] -> Int
findIndex x xs = go xs 0
  where
    go [] _     = -1
    go (y:ys) i
        | x == y    = i
        | otherwise = go ys (i + 1)

main :: IO ()
main = do
    line1 <- getLine
    line2 <- getLine
    let xs     = map read (words line1) :: [Int]
        target = read line2 :: Int
    print (findIndex target xs)

The accumulator version is clean and efficient. The I/O is the standard recipe: getLine, words, map read, type annotate.

You have covered reversal, accumulator patterns, zip/unzip, take/drop, rotation, palindromes, interleaving, run-length encoding, insertion sort, merging, and I/O. Practice writing each on paper until it is automatic. Good luck on the exam.