Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 57 ยท Practice and interviews

Practice: Functions, Lists and Recursion

Fifteen Haskell exercises with solutions on map, filter, folds, recursion and lazy lists, plus runnable JavaScript checks to test your ideas.

Reading about Haskell is not the same as writing it. These fifteen exercises cover the basics you have met so far: functions, pattern matching, lists, recursion, higher-order functions and laziness. They start easy and grow.

How to use this page: try each exercise yourself before reading the solution. If you have GHC installed (see Installing GHC and using GHCi), save your attempt in a file and load it with :r; the type signature is the contract, so the compiler tells you quickly when you are off. The Haskell blocks here are read-only because the site cannot run Haskell, but the two runnable blocks translate the exercises to JavaScript so you can check the logic and compare outputs with the examples shown.

How to practise

Try first Write your own answer before looking.
Types first Start with the signature.
Compare Read the solution and spot differences.
Redo Solve it again a different way.

A second solution teaches more than the first.

1 / 2

Part 1: Warm-ups

1. Double every element

Write doubleAll :: [Int] -> [Int] that doubles each number: doubleAll [1,2,3] is [2,4,6].

HASKELL
doubleAll :: [Int] -> [Int]
doubleAll = map (* 2)

(* 2) is an operator section (see Expressions, Functions and Application). Because map f is already a function waiting for a list, we can omit the list argument.

2. Sum of squares

Write sumSquares :: [Int] -> Int. sumSquares [1,2,3] is 14.

HASKELL
sumSquares :: [Int] -> Int
sumSquares = sum . map (^ 2)

The composition operator . builds a pipeline from right to left: first square each element, then add them up (see Lambdas, Composition and the $ Operator).

3. Keep the evens

Write evensOnly :: [Int] -> [Int].

HASKELL
evensOnly :: [Int] -> [Int]
evensOnly = filter even

An equivalent list comprehension is [x | x <- xs, even x]; see List Comprehensions.

4. Your own length

Write myLength :: [a] -> Int without using length. Use pattern matching.

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

The empty list is the base case; the other clause makes the problem smaller. This is the shape of most list recursion (see Recursion).

5. Reverse with an accumulator

Write myReverse :: [a] -> [a] that runs in linear time. The naive myReverse (x:xs) = myReverse xs ++ [x] takes quadratic time because ++ walks the whole left list every time.

HASKELL
myReverse :: [a] -> [a]
myReverse = go []
  where
    go acc []       = acc
    go acc (x : xs) = go (x : acc) xs

The helper go carries the reversed prefix in acc, adding each element to the front in constant time.

6. Palindromes

Write isPalindrome :: String -> Bool that ignores case, spaces and punctuation. isPalindrome "A man, a plan, a canal: Panama" is True.

HASKELL
import Data.Char (isAlpha, toLower)

isPalindrome :: String -> Bool
isPalindrome text = cleaned == reverse cleaned
  where
    cleaned = map toLower (filter isAlpha text)

7. FizzBuzz

Write fizzBuzz :: Int -> String: "FizzBuzz" for multiples of 15, "Fizz" for multiples of 3, "Buzz" for multiples of 5, otherwise the number.

HASKELL
fizzBuzz :: Int -> String
fizzBuzz n
  | n `mod` 15 == 0 = "FizzBuzz"
  | n `mod` 3  == 0 = "Fizz"
  | n `mod` 5  == 0 = "Buzz"
  | otherwise       = show n

Order matters: the 15 test must come first, or multiples of 15 would match the 3 case. Print the first 15 with mapM_ (putStrLn . fizzBuzz) [1 .. 15].

8. Factorial

Write factorial :: Integer -> Integer. Use Integer so large values do not overflow: factorial 20 is 2432902008176640000.

HASKELL
factorial :: Integer -> Integer
factorial n = product [1 .. n]

The range [1 .. 0] is empty and product [] is 1, so factorial 0 is correctly 1 with no special case.

JS Check Part 1 in JavaScript

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Part 2: Recursion and lazy lists

9. Fibonacci, the lazy way

Define the infinite list fibs :: [Integer] of Fibonacci numbers. take 10 fibs is [0,1,1,2,3,5,8,13,21,34].

HASKELL
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

The list is defined in terms of itself: each element is the sum of the two before it. Laziness computes only the elements you ask for (see Lazy Evaluation). Exercise: use takeWhile (< 100) fibs to get all Fibonacci numbers below 100.

10. The Collatz sequence

Write collatz :: Int -> [Int]: from n, repeat "halve if even, otherwise triple and add one" until you reach 1. collatz 6 is [6,3,10,5,16,8,4,2,1].

HASKELL
collatz :: Int -> [Int]
collatz 1 = [1]
collatz n
  | even n    = n : collatz (n `div` 2)
  | otherwise = n : collatz (3 * n + 1)

Nobody has proved that this always terminates, but it does for every number ever tried. The type signature says nothing about termination; that is the programmer's job.

11. Run-length encoding

Write rle :: String -> [(Char, Int)]. rle "aaabccdddd" is [('a',3),('b',1),('c',2),('d',4)].

HASKELL
import Data.List (group)

rle :: String -> [(Char, Int)]
rle = map (\run -> (head run, length run)) . group

group splits a list into runs of equal neighbours: group "aaabcc" is ["aaa","b","cc"]. head is safe here because group never produces an empty run. Exercise: write unrle as the inverse using concatMap.

12. Primes up to n

Write primesUpTo :: Int -> [Int]. primesUpTo 30 is [2,3,5,7,11,13,17,19,23,29].

HASKELL
primesUpTo :: Int -> [Int]
primesUpTo n = filter isPrime [2 .. n]

isPrime :: Int -> Bool
isPrime x = all (\d -> x `mod` d /= 0) (takeWhile (\d -> d * d <= x) [2 ..])

A number is prime if no divisor up to its square root divides it. [2 ..] is infinite, and takeWhile cuts it off, which only works because of laziness.

13. Chunking a list

Write chunksOf :: Int -> [a] -> [[a]] that splits a list into pieces of size n (the last may be shorter). chunksOf 3 [1..8] is [[1,2,3],[4,5,6],[7,8]]. Assume n > 0.

HASKELL
chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs = take n xs : chunksOf n (drop n xs)

14. Remove consecutive duplicates

Write compress :: Eq a => [a] -> [a] so that compress "aabccaa" is "abca".

HASKELL
import Data.List (group)

compress :: Eq a => [a] -> [a]
compress = map head . group

The Eq a constraint is needed because we compare elements (see Type Classes: Eq, Ord, Show, Read, Num).

15. Binary digits

Write toBinary :: Int -> String for non-negative numbers. toBinary 10 is "1010" and toBinary 0 is "0".

HASKELL
import Data.Char (intToDigit)

toBinary :: Int -> String
toBinary 0 = "0"
toBinary n = go n ""
  where
    go 0 acc = acc
    go k acc = go (k `div` 2) (intToDigit (k `mod` 2) : acc)

The remainders come out least-significant first, so consing each digit onto the front of the accumulator produces the right order.

JS Check Part 2 in JavaScript

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Going further

When you finish, try these variations to deepen the skills:

  • Write myMap, myFilter and myFoldr from scratch with pattern matching, then redefine sum, length and reverse with foldr or foldl' (see Higher-Order Functions).
  • Rewrite exercises 4, 5 and 13 so that they fail loudly on bad input using Maybe.
  • Write isPrime with a list comprehension and compare the two versions for readability.
  • Time collatz for the numbers up to 100,000 in GHCi with :set +s and find the longest sequence.
  • Run each solution in GHCi with :t to see the most general type, and notice when GHC infers something more general than your signature.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does fibs = 0 : 1 : zipWith (+) fibs (tail fibs) work?

    Lazy evaluation computes list elements on demand, so a list can be defined in terms of itself.
  2. 2. What is the benefit of the accumulator in myReverse?

    Consing onto an accumulator is constant time, whereas appending with ++ at the end costs time proportional to the list length each step.
  3. 3. In fizzBuzz, why must the test for 15 come before the tests for 3 and 5?

    Guards are tried in order; multiples of 15 would otherwise match the 3 guard and print only Fizz.
  4. 4. Which function groups equal neighbours into runs, as used in rle and compress?

    Data.List.group turns "aabccc" into ["aa","b","ccc"].

Summary

  • Start every function with its type signature; it guides the implementation.
  • map, filter, sum and function composition replace many loops.
  • Recursion needs a base case and a smaller problem; accumulators avoid quadratic ++.
  • Laziness lets you define infinite lists and cut them with take and takeWhile.
  • group is the key to run-length encoding and removing consecutive duplicates.

Next: Practice: Types, Classes and Monads.