λ Tony's blog λ
The weblog of Tony Morris

Haskell exercises for beginners

Posted on July 17, 2008, in Programming

The exercises below are similar to my previous ‘Scala exercises for beginners’, except the rules a little clearer. For those of who have emailed me or submitted responses here on the blog, I will get around to providing you feedback, however, I’d prefer to do so on the revised version of the Exercises since then I can maintain a bit of clarity in explaining the solutions; specifically, why one may be preferred over another. I hope you don’t mind.

If you have not used Haskell before, download and install GHC, start up the interpreter (ghci) and load the source file. e.g. :load Exercises.hs If you are on Debian, you can install GHC and start the interpreter with: apt-get install ghc6 && ghci.

The source file below can be found here.

-- + Complete the 10 exercises below by filling out the function bodies.
--   The code currently compiles, but none of the tests pass (the test function).
--   Replace the function bodies (error "todo") with an appropriate solution.
-- + These exercises may be done in any order, however:
--   Exercises are generally increasing in difficulty, though some people may find later exercise easier.
--   The tests are written to execute in the order 1 to 10, so you need to have Exercise n passing before Exercise (n+1) passes.
-- + Note the existence of the library function max :: Int -> Int -> Int which will help you with Exercise 9.
-- + Bonus for using the provided functions or for using one exercise solution to help solve another.
-- + Approach with your best available intuition; just dive in and do what you can!

-- TOTAL marks:    /66

module L02.List where

import Prelude hiding (sum, length, map, filter, maximum, reverse)

-- BEGIN Helper functions and data types

-- The custom list type
data List t = Nil | t :| List t deriving Eq

-- Right-associative
infixr 5 :|

instance (Show t) => Show (List t) where
  show = show . foldRight (:) []

-- functions over List that you may consider using
foldRight :: (a -> b -> b) -> b -> List a -> b
foldRight _ b Nil      = b
foldRight f b (h :| t) = f h (foldRight f b t)

foldLeft :: (b -> a -> b) -> b -> List a -> b
foldLeft _ b Nil      = b
foldLeft f b (h :| t) = let b' = f b h in b' `seq` foldLeft f b' t

reduceRight :: (a -> a -> a) -> List a -> a
reduceRight _ Nil      = error "bzzt. reduceRight on empty list"
reduceRight f (h :| t) = foldRight f h t

reduceLeft :: (a -> a -> a) -> List a -> a
reduceLeft _ Nil      = error "bzzt. reduceLeft on empty list"
reduceLeft f (h :| t) = foldLeft f h t

-- END Helper functions and data types

-- BEGIN Exercises

-- Exercise 1
-- Relative Difficulty: 1
-- Correctness: 2.0 marks
-- Performance: 0.5 mark
-- Elegance: 0.5 marks
-- Total: 3
headOr :: List a -> a -> a
headOr = error "todo"

-- Exercise 2
-- Relative Difficulty: 2
-- Correctness:   2.5 marks
-- Performance: 1 mark
-- Elegance: 0.5 marks
-- Total: 4
sum :: List Int -> Int
sum = error "todo"

-- Exercise 3
-- Relative Difficulty: 2
-- Correctness: 2.5 marks
-- Performance: 1 mark
-- Elegance: 0.5 marks
-- Total: 4
length :: List a -> Int
length = error "todo"

-- Exercise 4
-- Relative Difficulty: 5
-- Correctness: 4.5 marks
-- Performance: 1.0 mark
-- Elegance: 1.5 marks
-- Total: 7
map :: (a -> b) -> List a -> List b
map = error "todo"

-- Exercise 5
-- Relative Difficulty: 5
-- Correctness: 4.5 marks
-- Performance: 1.5 marks
-- Elegance: 1 mark
-- Total: 7
filter :: (a -> Bool) -> List a -> List a
filter = error "todo"

-- Exercise 6
-- Relative Difficulty: 5
-- Correctness: 4.5 marks
-- Performance: 1.5 marks
-- Elegance: 1 mark
-- Total: 7
append :: List a -> List a -> List a
append = error "todo"

-- Exercise 7
-- Relative Difficulty: 5
-- Correctness: 4.5 marks
-- Performance: 1.5 marks
-- Elegance: 1 mark
-- Total: 7
flatten :: List (List a) -> List a
flatten = error "todo"

-- Exercise 8
-- Relative Difficulty: 7
-- Correctness: 5.0 marks
-- Performance: 1.5 marks
-- Elegance: 1.5 mark
-- Total: 8
flatMap :: (a -> List b) -> List a -> List b
flatMap = error "todo"

-- Exercise 9
-- Relative Difficulty: 8
-- Correctness: 3.5 marks
-- Performance: 3.0 marks
-- Elegance: 2.5 marks
-- Total: 9
maximum :: List Int -> Int
maximum = error "todo"

-- Exercise 10
-- Relative Difficulty: 10
-- Correctness: 5.0 marks
-- Performance: 2.5 marks
-- Elegance: 2.5 marks
-- Total: 10
reverse :: List a -> List a
reverse = error "todo"

-- END Exercises

-- BEGIN Tests for Exercises

test :: IO ()
test =
  let showNil = show (Nil :: List Int)
      results =
        [
        -- headOr
        ("headOr",
         show (headOr (1 :| 2 :| 3 :| Nil) 7)
       , show 1),

        ("headOr",
         show (headOr Nil 8)
       , show 8),

        -- sum
        ("sum",
         show (sum (1 :| 2 :| 3 :| Nil))
       , show 6),

        ("sum",
         show (sum Nil)
       , show 0),

        -- length
        ("length",
         show (length ('a' :| 'b' :| 'c' :| Nil))
       , show 3),

        ("length",
         show (length Nil)
       , show 0),

        -- map
        ("map",
         show (map (+1) (1 :| 2 :| 3 :| Nil))
       , show (2 :| 3 :| 4 :| Nil)),

        ("map",
         show (map (+1) Nil)
       , showNil),

        -- filter
        ("filter",
         show (filter even (1 :| 2 :| 3 :| Nil))
       , show (2 :| Nil)),

        ("filter",
         show (filter even Nil)
       , showNil),

        -- append
        ("append",
         show (append (1 :| 2 :| 3 :| Nil) (4 :| Nil))
       , show (1 :| 2 :| 3 :| 4 :| Nil)),

        ("append",
         show (append (1 :| 2 :| 3 :| Nil) Nil)
       , show (1 :| 2 :| 3 :| Nil)),

        -- flatten
        ("flatten",
         show (flatten ((1 :| 2 :| Nil) :| ((3 :| 4 :| Nil) :| Nil)))
       , show (1 :| 2 :| 3 :| 4 :| Nil)),

        -- flatMap
        ("flatMap",
         show (flatMap (\n -> (n+1) :| (n+2) :| Nil) (1 :| 2 :| 3 :| Nil))
       , show (2 :| 3 :| 3 :| 4 :| 4 :| 5 :| Nil)),

        -- maximum
        ("maximum",
         show (maximum (3 :| 1 :| 2 :| Nil))
       , show 3),

        -- reverse
        ("reverse",
         show (reverse (1 :| 2 :| 3 :| Nil))
       , show (3 :| 2 :| 1 :| Nil))
        ]
      check (n, a, b) = do print ("=== " ++ n ++ " ===")
                           print (if a == b then "PASS" else "FAIL Expected: " ++ b ++ " Actual: " ++ a)

  in mapM_ check results

-- END Tests for Exercises

-- Utility

all ::
  (a -> Bool)
  -> List a
  -> Bool
all p =
  foldRight (&&) True . map p

isEmpty ::
  List a
  -> Bool
isEmpty Nil    = True
isEmpty (_:|_) = False

contains ::
  Eq a =>
  List a
  -> a
  -> Bool
contains Nil    _ = False
contains (h:|t) e = h == e || contains t e