Haskell exercises for beginners
Thursday, July 17th, 2008The 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.
{-
The 'Scala exercises for beginners' set rules about what you were not permitted to use.
This is because you were permitted to use some functions, but not others. This led to
some amount of confusion (sorry). Instead, this time, I will define my own data types.
One is equivalent to Haskell's list [], although without the syntactic support and the
other is the set of natural numbers (0 onward). I will also predefine some useful
functions that you might consider using to solve each problem. That way, I needn't set
any rules; you are very much free to do what you want (Although, converting between
this type and [] is considered cheating, as you might expect 
.
I will consider converting the Scala exercises to use a similar strategy in a second
revision to prevent this confusion.
TOTAL marks: /66
-}
module Exercises where
import Prelude hiding (sum, length, map, filter, maximum, reverse, succ, pred)
-- The custom list type
data List t = Nil | Cons t (List t)
instance (Show t) => Show (List t) where
show = show . toList
where
-- unfoldr, but let's not import Data.List
toList Nil = []
toList (Cons h t) = h : toList t
-- the custom numeric type
data Natural = Zero | Succ Natural
one = Succ Zero
two = Succ one
instance Show Natural where
show = show . toInt
where
toInt Zero = 0
toInt (Succ x) = 1 + toInt x
-- functions over Natural that you may consider using
succ :: Natural -> Natural
succ = Succ
pred :: Natural -> Natural
pred Zero = error "bzzt. Zero has no predecessor in naturals"
pred (Succ x) = x
-- functions over List that you may consider using
foldRight :: (a -> b -> b) -> b -> List a -> b
foldRight _ b Nil = b
foldRight f b (Cons h t) = f h (foldRight f b t)
foldLeft :: (b -> a -> b) -> b -> List a -> b
foldLeft _ b Nil = b
foldLeft f b (Cons 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 (Cons h t) = foldRight f h t
reduceLeft :: (a -> a -> a) -> List a -> a
reduceLeft _ Nil = error "bzzt. reduceLeft on empty list"
reduceLeft f (Cons h t) = foldLeft f h t
unfold :: (b -> Maybe (a, b)) -> b -> List a
unfold f b = case f b of Just (a, b') -> a `Cons` unfold f b'
Nothing -> Nil
-- Exercises
-- Exercise 1
-- Relative Difficulty: 1
-- Correctness: 2.0 marks
-- Performance: 0.5 mark
-- Elegance: 0.5 marks
-- Total: 3
add :: Natural -> Natural -> Natural
add = 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 :: List a -> (a -> List b) -> 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"
