Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 57 ยท Practice and interviews

Practice: Types, Classes and Monads

Twelve Haskell exercises with solutions on algebraic data types, Maybe and Either, type classes, folds and monad chaining, with runnable JS checks.

The first practice page (Functions, Lists and Recursion) trained your hands on everyday functions. This second set trains the part that makes Haskell special: its type system. You will define data types, model absence and failure with Maybe and Either, write a type class, fold over a tree and chain computations with the monad machinery.

Work the same way as before: read the problem, write the type signature, try an implementation, then compare. The Haskell here is read-only on this site, so the two runnable blocks are JavaScript stand-ins (tagged objects for data types, small helper functions for >>=) that let you check the behaviour of each exercise against the results given in the text.

What these exercises train

Data types Sum and product types, trees.
Safety Maybe and Either instead of crashes.
Classes Instances and Semigroup.
Chaining Monads and traverse.

Let the types guide you.

1 / 2

Part 1: Data types and classes

1. Shapes

Define data Shape = Circle Double | Rect Double Double | Triangle Double Double Double and a function area :: Shape -> Double. For the triangle use Heron's formula: with s = (a + b + c) / 2, the area is sqrt (s * (s - a) * (s - b) * (s - c)).

HASKELL
data Shape
  = Circle Double
  | Rect Double Double
  | Triangle Double Double Double
  deriving (Show, Eq)

area :: Shape -> Double
area (Circle r)       = pi * r * r
area (Rect w h)       = w * h
area (Triangle a b c) = sqrt (s * (s - a) * (s - b) * (s - c))
  where s = (a + b + c) / 2

area (Triangle 3 4 5) is 6.0 and area (Rect 2 3) is 6.0. Each constructor is one case; if you add a Square later, -Wall warns about every function that forgot it (see Algebraic Data Types).

2. A cyclic weekday

Define data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun deriving Show, Eq, Enum and Bounded, and write next :: Day -> Day where next Sun wraps around to Mon.

HASKELL
data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
  deriving (Show, Eq, Enum, Bounded)

next :: Day -> Day
next d
  | d == maxBound = minBound
  | otherwise     = succ d

Deriving Enum gives succ, pred and ranges like [Mon ..]; deriving Bounded gives minBound and maxBound. Using them avoids a seven-line case.

3. Safe head and division

Write safeHead :: [a] -> Maybe a and safeDiv :: Int -> Int -> Maybe Int that return Nothing instead of crashing.

HASKELL
safeHead :: [a] -> Maybe a
safeHead []      = Nothing
safeHead (x : _) = Just x

safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv a b = Just (a `div` b)

4. Chaining lookups

You have two association lists: phone numbers to owner names, and names to cities. Write cityOf :: String -> Maybe String that finds the city for a phone number, giving Nothing if either lookup fails.

HASKELL
phones :: [(String, String)]
phones = [("555-0100", "Ada"), ("555-0101", "Bob")]

cities :: [(String, String)]
cities = [("Ada", "London")]

cityOf :: String -> Maybe String
cityOf number = lookup number phones >>= \name -> lookup name cities

cityOf "555-0100" is Just "London", cityOf "555-0101" is Nothing (Bob has no city) and cityOf "000" is Nothing. The same thing in do notation reads do { name <- lookup number phones; lookup name cities } (see do-Notation Demystified).

5. Validation with Either

Write validateAge :: Int -> Either String Int that rejects negative numbers and numbers above 150, with a message for each case.

HASKELL
validateAge :: Int -> Either String Int
validateAge n
  | n < 0     = Left "age cannot be negative"
  | n > 150   = Left "age is unrealistic"
  | otherwise = Right n

6. Your own type class

Define a class Describable with a method describe :: a -> String, and instances for Bool and for the Shape of exercise 1.

HASKELL
class Describable a where
  describe :: a -> String

instance Describable Bool where
  describe True  = "yes"
  describe False = "no"

instance Describable Shape where
  describe (Circle r)       = "a circle of radius " ++ show r
  describe (Rect w h)       = "a " ++ show w ++ " by " ++ show h ++ " rectangle"
  describe (Triangle _ _ _) = "a triangle"

A class is a set of operations; an instance gives the implementation for one type. You could add instance Describable a => Describable [a] to describe lists by joining the descriptions of the elements (see Defining Your Own Type Classes and Instances).

JS Check Part 1 in JavaScript

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

No output.

Part 2: Trees, folds and monoids

7. A binary search tree

Define data Tree a = Leaf | Node (Tree a) a (Tree a), then write insert :: Ord a => a -> Tree a -> Tree a, contains :: Ord a => a -> Tree a -> Bool and toList :: Tree a -> [a] that returns the values in sorted order.

HASKELL
data Tree a = Leaf | Node (Tree a) a (Tree a)
  deriving Show

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x node@(Node left v right)
  | x < v     = Node (insert x left) v right
  | x > v     = Node left v (insert x right)
  | otherwise = node

contains :: Ord a => a -> Tree a -> Bool
contains _ Leaf = False
contains x (Node left v right)
  | x < v     = contains x left
  | x > v     = contains x right
  | otherwise = True

toList :: Tree a -> [a]
toList Leaf                = []
toList (Node left v right) = toList left ++ [v] ++ toList right

foldr insert Leaf [5, 3, 8, 1, 4, 3] builds a tree with no duplicates, and toList of it is [1,3,4,5,8]. The in-order traversal is what makes the output sorted (see Recursive Data Types and Trees).

8. map and filter from foldr

Define myMap :: (a -> b) -> [a] -> [b] and myFilter :: (a -> Bool) -> [a] -> [a] using only foldr.

HASKELL
myMap :: (a -> b) -> [a] -> [b]
myMap f = foldr (\x acc -> f x : acc) []

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter p = foldr (\x acc -> if p x then x : acc else acc) []

foldr f z replaces every : in a list with f and the final [] with z. Thinking that way explains why foldr can build lists, and why it works on infinite lists when f is lazy in its second argument (see Higher-Order Functions).

9. A safe average in one pass

Write mean :: [Double] -> Maybe Double that returns Nothing for an empty list. Walk the list only once, keeping a running sum and a count with a strict fold.

HASKELL
import Data.List (foldl')

mean :: [Double] -> Maybe Double
mean [] = Nothing
mean xs = Just (total / fromIntegral count)
  where
    (total, count) = foldl' step (0, 0 :: Int) xs
    step (s, c) x  = (s + x, c + 1)

mean [1, 2, 3, 4] is Just 2.5. With foldl' the accumulator is forced at each step, so the sum does not build a chain of thunks (see Strictness, Bang Patterns and seq). Strictly speaking the tuple's components stay lazy; for large lists a real solution adds bang patterns, but the pair is enough for this exercise.

10. An expression evaluator

Define data Expr = Num Double | Add Expr Expr | Div Expr Expr and eval :: Expr -> Either String Double. Division by zero must return a Left, and the first error stops evaluation.

HASKELL
data Expr
  = Num Double
  | Add Expr Expr
  | Div Expr Expr
  deriving Show

eval :: Expr -> Either String Double
eval (Num n)   = Right n
eval (Add a b) = do
  x <- eval a
  y <- eval b
  pure (x + y)
eval (Div a b) = do
  x <- eval a
  y <- eval b
  if y == 0
    then Left "division by zero"
    else pure (x / y)

eval (Add (Num 1) (Div (Num 6) (Num 3))) is Right 3.0; replace the 3 with 0 and the result is Left "division by zero". Compare with the longer version in Project: Expression Calculator.

11. A semigroup for min and max

Define data MinMax = MinMax Int Int and a Semigroup instance that combines two ranges into the range covering both. Use it to find the smallest and largest of a non-empty list in one fold.

HASKELL
data MinMax = MinMax Int Int
  deriving (Show, Eq)

instance Semigroup MinMax where
  MinMax lo1 hi1 <> MinMax lo2 hi2 = MinMax (min lo1 lo2) (max hi1 hi2)

range :: [Int] -> Maybe MinMax
range []       = Nothing
range (x : xs) = Just (foldr (\y acc -> MinMax y y <> acc) (MinMax x x) xs)

range [3, 9, 1, 7] is Just (MinMax 1 9). The <> operation is associative, which is why combining in any grouping gives the same answer; that is the rule a Semigroup promises (see Semigroups and Monoids). There is no Monoid instance because there is no sensible identity value for Int bounds without maxBound tricks.

12. Parsing a list, all or nothing

Write parseAll :: [String] -> Maybe [Int] that turns every string into an Int, returning Nothing if any one fails. Then write mkUser :: String -> String -> Either String (String, Int) that validates a name and an age using do.

HASKELL
import Text.Read (readMaybe)

parseAll :: [String] -> Maybe [Int]
parseAll = traverse readMaybe

mkUser :: String -> String -> Either String (String, Int)
mkUser name ageText = do
  n <- if null name then Left "name is empty" else Right name
  a <- maybe (Left ("bad age: " ++ ageText)) Right (readMaybe ageText)
  age <- validateAge a
  pure (n, age)

parseAll ["1","2","3"] is Just [1,2,3] and parseAll ["1","x","3"] is Nothing. traverse runs the Maybe-returning function over the list and collects the results, stopping at the first failure (see Foldable and Traversable). mkUser reuses validateAge from exercise 5, and each <- line stops the whole block on Left.

JS Check Part 2 in JavaScript

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

No output.

Going further

  • Add a Mul constructor to Expr, and a Var String constructor that evaluates against an environment Map String Double, returning Left "unbound variable" when missing.
  • Write height :: Tree a -> Int and size :: Tree a -> Int, then make Tree an instance of Functor and Foldable (see Functors).
  • Collect all validation errors for mkUser instead of the first one, using applicative style (see Applicative Functors).
  • Give MinMax a Monoid instance by wrapping it in Maybe: Maybe MinMax is a monoid whenever MinMax is a semigroup.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does deriving (Enum, Bounded) give the Day type?

    Enum provides succ, pred and enumeration ranges; Bounded provides minBound and maxBound.
  2. 2. What does traverse readMaybe ["1", "x"] return?

    traverse collects the results in Maybe; a single Nothing makes the whole result Nothing.
  3. 3. Why can foldr define both map and filter?

    foldr replaces each cons cell with a function and the empty list with a starting value, so it can rebuild a list.
  4. 4. In the Either-based eval, what happens when the left operand of Add returns Left?

    do-notation in Either short-circuits at the first Left.
  5. 5. What property must the <> of a Semigroup satisfy?

    Associativity: (a <> b) <> c equals a <> (b <> c). An identity element is the extra requirement of Monoid.

Summary

  • Algebraic data types plus pattern matching make each case explicit and checked by the compiler.
  • Maybe and Either turn crashes into values; >>=, do and traverse chain them.
  • A type class is an interface; an instance supplies it for a type.
  • foldr and foldl' capture most list recursion; recursive types are folded with the same shape of code.
  • Semigroup captures "combine two things associatively", which makes folds composable.

Next: Common Mistakes and Error Messages.