Chapter 12: Signaling adversity¶

12.1 Signaling adversity¶

This chapter is all about dealing with failure conditions using datatypes like Maybe and Either, and how to expose functions that guard against invalid input that will typecheck when constructing datatypes. It also has some things to say about higher-kindness and anamorphisms.

12.2 How I learned to stop worrying and love Nothing¶

Maybe represents the potential of failure when computing a result. It is used to express that something can be in one of two states: defined or undefined. Another way to think of this is that the result is partial; that is, not defined for all values of arguments. To get around this, we use Maybe to return eithther a constructor that wraps the result type, or the Nothing data constructor, which acts as an explicit signal of failure.

So, what does it look like?

data Maybe a = Nothing | Just a

Here is a simple example of its use:

ifEvenAdd2 :: Integer -> Maybe Integer
ifEvenAdd2 n = if even n then Just (n+2) else Nothing

12.2.1 Smart constructors for datatypes¶

Let’s consider a Person type that keeps track of two things, a name and age.

type Name = String
type Age = Integer
data Person = Person Name Age deriving Show

There are a few problems here. One is that we could construct a Person with an empty string for a name, or make a person who is negative years old. We’ll create a smart constructor, a function to construct values of type Person, that will filter out invalid inputs for us.

mkPerson :: Name -> Age -> Maybe Person
mkPerson name age
  | name /= "" && age >= 0  =  Just (Person name age)
  | otherwise               =  Nothing

12.3 Bleating Either¶

Either is mostly used as a generalization of Maybe in which Left not only encodes failure but is accompanied by an error message. Right encodes success and the accompanying value. As you can see by the type variables a and b, Left and Right may each wrap different types:

data Either a b = Left a | Right b

Treating Left as a failure state has a few motivations, but it’s mostly just a convention. One reason to adhere to this convention is how pre-defined type class instances have chosen to implement behaviour for Left. For example, Functor will not map over the left type argument.

Around this section, the book has an example where mkPerson is incrementally modified so that it uses Either to return an indication of possible failure modes for constructing a Person. You can view these in the figures/13.{2,3} directories.

12.4 Kinds, a thousand stars in your types¶

In this section there are many detail about kinds. There are also two long ghci sessions where you inspect kind signatures. I haven’t included this in my notes because I can’t answer the following questions:

Why is this important?
How is this relevant to getting shit done?
Why should I care?

Without that, this seems like useless trivia, and I’m pretty sure I’ll forget it all. That’s OK, though, I can look it up when I need to. Search engines exist.

12.5 Chapter Exercises¶

12.5.1 Determine the kinds¶

Given id :: a -> a, what is the kind of a?

Since a must be a concrete type, it’s *.
Given r :: a -> f a, what are the kinds of a and f?

The type variable a is *, and f is * -> *.

12.5.2 String processing¶

Write a recursive function named replaceThe which takes a string, breaks it into words, and replaces each instance of “the” with “a”. It’s intended only to replace exactly the word “the”.

notThe is a suggested helper function for accomplishing this:

notThe :: String -> Maybe String
notThe = undefined

Example GHCi session of the above functions:

·∾  notThe "the"
Nothing

·∾  notThe "blahtheblah"
Just "blahtheblah"

·∾  notThe "woot"
Just "woot"

The main function:

replaceThe :: String -> String
replaceThe = undefined

A simple example of its use:

·∾  replaceThe "the cow loves us"
"a cow loves us"

Ok, are you ready? Bear witness to the abomination that I’ve created!

-- helper function
notThe :: String -> Maybe String
notThe s = if s == "the" then Nothing else Just s

-- primary function
replaceThe :: String -> String
replaceThe s =
  words s &
  map notThe &
  map (\x -> case x of {Nothing -> Just "a"; Just y -> Just y}) &
  map (\(Just x) -> x) &
  intercalate " "

-- With Data.Text I could write ``replaceThe s = replace "the" "a" s``
-- instead, but that feels like cheating.

Write a recursive function that takes a string, breaks it into words, and counts the number of instances of “the” followed by a vowel-initial word.

A stub of the function declaration:

countTheBeforeVowel :: String -> Integer
countTheBeforeVowel = undefined

Simple demonstration of its use:

·∾  countTheBeforeVowel "the cow"
0

·∾  countTheBeforeVowel "the evil cow"
1

I can’t believe you’ve done this!

countTheBeforeVowel :: String -> Integer
countTheBeforeVowel s =
  let
    idxOfThes = if length (words s) > 1
                then Just $ elemIndices "the" (init (words s))
                else Nothing
  in
    if idxOfThes == Nothing
    then
      0
    else
      map (\x -> (words s) !! (x+1)) ((\(Just x) -> x) idxOfThes) &
      filter (\x -> (head x) `elem` "aeiou") &
      length &
      toInteger

Return the number of letters that are vowels in a word. Hint: it’s helpful to break this into steps. Add any helper functions necessary to achieve your objectives.
1. Test for vowelhood
2. Return the vowels of a string
3. Count the number of elements returned
Function stub:
```
countVowels :: String -> Integer
countVowels = undefined
```
Example use:
```
·∾  countVowels "the cow"
2

·∾  countVowels "Mikolajczak"
4
```
General Kenobi …
```
countVowels :: String -> Integer
countVowels s = filter (\x -> x `elem` "aeiou") s & length & toInteger
```

12.5.3 Validate the word¶

Use the Maybe type to write a function that counts the number of vowels in a string and the number of consonants. If the number of vowels exceeds the number of consonants, the function returns Nothing. In many human languages, vowels rarely exceed the number of consonants so when they do, it may indicate the input isn’t a word (that is, a valid input to your dataset):

newtype Word' = Word' String
  deriving (Eq, Show)

vowels = "aeiou"

mkWord :: String -> Maybe Word'
mkWord = undefined

Ok, here’s your function. Have fun.

module Lib where

newtype Word' = Word' String deriving (Eq, Show)

mkWord :: String -> Maybe Word'
mkWord s =
  let
    numVowels = length $ filter (`elem` "aeiou") s
    numConsonants = length $ filter (`elem` "bcdfghjklmnpqrstvwxzy") s
  in
    if   numVowels > numConsonants
    then Nothing
    else Just (Word' s)

12.5.4 It’s only Natural¶

You’ll be presented with a datatype to represent the natural numbers. The only values representable with the naturals are whole numbers from zero to infinity.

Your task will be to implement functions to convert Naturals to Integers and Integers to Naturals.

Any Natural can be represented by an Integer, but the same is not true of any Integer. Negative numbers are not valid natural numbers.

The conversion from Naturals to Integers won’t return Maybe because Integer is a strict superset of Natural.

First, the datatype:

data Nat = Zero | Succ Nat
  deriving (Eq, Show)

Here is a stub for natToInteger:

natToInteger :: Nat -> Integer
natToInteger = undefined

Along with it’s expected output:

·∾ natToInteger Zero
0

·∾ natToInteger (Succ Zero)
1

·∾ natToInteger (Succ (Succ Zero))
2

A function to convert integers to Nats:

integerToNat :: Integer -> Maybe Nat
integerToNat = undefined

Example output:

·∾  integerToNat 0
Just Zero

·∾  integerToNat 1
Just (Succ Zero)

·∾  integerToNat 2
Just (Succ (Succ Zero))

·∾  integerToNat (-1)
Nothing

Ok, here is my attempt.

module Lib where

data Nat = Zero | Succ Nat
  deriving (Eq, Show)

natToInteger :: Nat -> Integer
natToInteger Zero = 0
natToInteger (Succ x) = 1 + natToInteger x

integerToNat :: Integer -> Maybe Nat
integerToNat x = case signum x of
  (-1) -> Nothing
  0    -> Just Zero
  1    -> Just (go x)
  where
    go :: Integer -> Nat
    go 0 = Zero
    go n = Succ (go (n-1))

12.5.5 Small library for Maybe¶

Write the following functions. This may take some time.

Simple boolean checks for Maybe values.

Function stub:

isJust :: Maybe a -> Bool

GHCi session:

·∾  isJust (Just 1)
True

·∾  isJust Nothing
False

Function stub:

isNothing :: Maybe a -> Bool

GHCi session:

·∾  isNothing (Just 1)
False

·∾  isNothing Nothing
True

Here is my attempt:

isJust :: Maybe a -> Bool
isJust (Just _) = True
isJust Nothing  = False

isNothing :: Maybe a -> Bool
isNothing = not . isJust

The following is the Maybe catamorphism. You can turn a Maybe value into anything else with this.

Function stub:

mayybee :: b -> (a -> b) -> Maybe a -> b

Examples of its use:

·∾  mayybee 0 (+1) Nothing
0

·∾  mayybee 0 (+1) (Just 1)
2

Here is my attempt:

mayybee :: b -> (a -> b) -> Maybe a -> b
mayybee b f m = case m of
  Just a   ->  f a
  Nothing  ->  b

In case you just want to provide a fallback value.

Function stub:

-- Try writing it in terms of the maybe catamorphism
fromMaybe :: a -> Maybe a -> a

Example usage:

·∾  fromMaybe 0 Nothing
0

·∾  fromMaybe 0 (Just 1)
1

Here is my attempt:

fromMaybe :: a -> Maybe a -> a
-- fromMaybe i Nothing = i
-- fromMaybe _ (Just x) = x
fromMaybe i m = mayybee i id m

Converting between List and Maybe.

Stub:

listToMaybe :: [a] -> Maybe a

Usage:

·∾  listToMaybe [1, 2, 3]
Just 1

·∾  listToMaybe []
Nothing

Stub:

maybeToList :: Maybe a -> [a]

Usage of maybeToList:

·∾  maybeToList (Just 1)
[1]

·∾  maybeToList Nothing
[]

Here is my attempt:

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

maybeToList :: Maybe a -> [a]
maybeToList m = case m of
  Just x   ->  [x]
  Nothing  ->   []

For when we want to drop the Nothing values from our list.

Stub:

catMaybes :: [Maybe a] -> [a]

Usage:

·∾  catMaybes [Just 1, Nothing, Just 2]
[1, 2]

·∾  let xs = take 3 $ repeat Nothing

·∾  catMaybes xs
[]

Here is my attempt:

catMaybes :: [Maybe a] -> [a]
catMaybes ((Just a):xs)  =  a : catMaybes xs
catMaybes  (Nothing:xs)  =      catMaybes xs
catMaybes            []  =                []

You’ll see this called “sequence” later.

Stub:

flipMaybe :: [Maybe a] -> Maybe [a]

Usage:

·∾  flipMaybe [Just 1, Just 2, Just 3]
Just [1, 2, 3]

·∾  flipMaybe [Just 1, Nothing, Just 3]
Nothing

Here is my attempt:

flipMaybe :: [Maybe a] -> Maybe [a]
flipMaybe l =
  if all isJust l
  then Just (catMaybes l)
  else Nothing

12.5.6 Small library for Either¶

Write each of the following functions. If more than one possible unique function exists for the type, use common sense to determine what it should do.

Try to eventually arrive at a solution that uses foldr, even if earlier versions don’t use foldr.

lefts' :: [Either a b] -> [a]

Here is my attempt:

-- Try to arrive at a solution that uses
-- foldr, even if earlier versions don't.

-- Non-foldr version
-- lefts' :: [Either a b] -> [a]
-- lefts'  ((Left x):xs) = x : lefts' xs
-- lefts' ((Right _):xs) = lefts' xs
-- lefts'             [] = []

-- Using foldr...
lefts' :: [Either a b] -> [a]
lefts' = foldr (\e xs ->
  case e of
    Left x  -> x : xs
    Right _ -> xs) []

Same as the last one. Use foldr eventually.

rights' :: [Either a b] -> [b]

Here is my attempt:

-- Same as the last one, use foldr
-- eventually.
rights' :: [Either a b] -> [b]
rights' = foldr (\e xs ->
  case e of
    Right x -> x : xs
    Left _  -> xs) []

partitionEithers' :: [Either a b] -> ([a], [b])

Here is my attempt:

partitionEithers' :: [Either a b] -> ([a], [b])
partitionEithers' l = (lefts' l, rights' l)

eitherMaybe' :: (b -> c) -> Either a b -> Maybe c

Here is my attempt:

eitherMaybe' :: (b -> c) -> Either a b -> Maybe c
eitherMaybe' f x = case x of
  Right b -> Just (f b)
  Left _  -> Nothing

This is a general catamorphism for Either values.

either' :: (a -> c) -> (b -> c) -> Either a b -> c

Here is my attempt:

-- This is a general catamorphism for
-- Either values.
either' :: (a -> c) -> (b -> c) -> Either a b -> c
either' f g e = case e of
  Left a -> (f a)
  Right b -> (g b)

Same as before, but use the either' function you just wrote.

eitherMaybe'' :: (b -> c) -> Either a b -> Maybe c

Here is my attempt:

-- Same as before, but use the either
-- function you just wrote.
eitherMaybe'' :: (b -> c) -> Either a b -> Maybe c
eitherMaybe'' f x = either' (\_ -> Nothing) (Just . f) x

Most of the functions you just saw are in the Prelude, Data.Maybe, or Data.Either but you should strive to write them yourself without looking at existing implementations. You will deprive yourself if you cheat.

12.5.7 Unfolds¶

While the idea of catamorphisms is still relatively fresh in our minds, let’s turn our attention to their dual: anamorphisms. If folds, or catamorphisms, let us break data structures down, then unfolds let us build them up. There are, as with folds, a few different ways to unfold a data structure. We can use them to create finite and infinite data structures alike.

iterate is like a limited unfold that never ends:

·∾ :t iterate
iterate :: (a -> a) -> a -> [a]

Because it never ends, we must use take to get a finite list:

·∾ take 10 $ iterate (+1) 0
[0,1,2,3,4,5,6,7,8,9]

unfoldr is more general:

·∾ :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

Using unfoldr to do the same thing as iterate:

·∾ take 10 $ unfoldr (\b -> Just (b, b+1)) 0
[0,1,2,3,4,5,6,7,8,9]

Alright, here is my attempt.

For iterate:

iterate'' :: (a -> a) -> a -> [a]
iterate'' f x = x : iterate'' f (f x)

…and unfoldr:

unfoldr'' :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr'' f x = case f x of
  Just (a,b) -> a : unfoldr'' f b
  Nothing -> []

12.5.8 Why bother?¶

We bother with this [Ed: by “this”, the author probably means defining convenience functions such as those found in Data.Either and Data.Maybe like lefts and fromMaybe ] for the same reason we abstracted direct recursion into folds, such as with sum, product, and concat.

import Data.List

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

niceSum :: Num a => [a] -> a
niceSum = foldl' (+) 0

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

niceProduct :: Num a => [a] -> a
niceProduct = foldl' (*) 1

Remember the redundant structure when we looked at folds?

mehConcat :: [[a]] -> [a]
mehConcat xs = go [] xs
  where go :: [a] -> [[a]] -> [a]
        go xs' [] = xs'
        go xs' (x:xs) = (go (xs' ++ x) xs)

niceConcat :: [[a]] -> [a]
niceConcat = foldr (++) []

This may have given you a mild headache, but you may also see that this same principle of abstracting out common patterns and giving them names applies as well to unfolds as it does to folds.

Ok, I’ve read the code, experimented with it, and think I understand the point. Is there anything else I should do with this?

12.5.9 Write your own iterate and unfoldr¶

Write the function myIterate using direct recursion. Compare the behavior with the built-in iterate to gauge correctness. Do not look at the source or any examples of iterate so that you are forced to do this yourself.
```
myIterate :: (a -> a) -> a -> [a]
myIterate = undefined
```
Here’s my attempt:
```
myIterate :: (a -> a) -> a -> [a]
myIterate f x = x : myIterate f (f x)
```

Write the function myUnfoldr using direct recursion. Compare with the built-in unfoldr to check your implementation. Again, don’t look at implementations of unfoldr so that you figure it out yourself.

myUnfoldr :: (b -> Maybe (a, b)) -> b -> [a]
myUnfoldr = undefined

Here’s my attempt:

myUnfoldr :: (b -> Maybe (a, b)) -> b -> [a]
myUnfoldr f x = case f x of
  Just (a,b) -> a : myUnfoldr f b
  Nothing    -> []

Rewrite myIterate into betterIterate using myUnfoldr. A hint — we used unfoldr to produce the same results as iterate earlier. Do this with different functions and see if you can abstract the structure out.

-- It helps to have the types in front of you
-- myUnfoldr :: (b -> Maybe (a, b)) -> b -> [a]
betterIterate :: (a -> a) -> a -> [a]
betterIterate f x = myUnfoldr ...?

Remember, your betterIterate should have the same results as iterate.

·∾ take 10 $ iterate (+1) 0
[0,1,2,3,4,5,6,7,8,9]

·∾ take 10 $ betterIterate (+1) 0
[0,1,2,3,4,5,6,7,8,9]

Here’s my attempt:

-- Use myUnfoldr to implement this.
betterIterate :: (a -> a) -> a -> [a]
betterIterate f x = myUnfoldr (\i -> Just (i,f i)) x

12.5.10 Finally something other than a list!¶

Given the BinaryTree from last chapter, complete the following exercises. Here’s that datatype again:

data BinaryTree a =
  Leaf | Node (BinaryTree a) a (BinaryTree a)
  deriving (Eq, Ord, Show)

Write unfold for BinaryTree.

unfold :: (a -> Maybe (a,b,a)) -> a -> BinaryTree b
unfold = undefined

Ok, here is my attempt:

unfold :: (a -> Maybe (a,b,a)) -> a -> BinaryTree b
unfold f x = case f x of
  Just (l, m, r) -> Node (unfold f l) m (unfold f r)
  Nothing -> Leaf

Make a tree builder.

Using the unfold function you’ve made for BinaryTree, write the following function:

treeBuild :: Integer -> BinaryTree Integer
treeBuild n = undefined

You should be producing results that look like the following:

·∾  treeBuild 0
Leaf

·∾  treeBuild 1
Node Leaf 0 Leaf

·∾  treeBuild 2
Node (Node Leaf 1 Leaf)
     0
     (Node Leaf 1 Leaf)

·∾  treeBuild 3
Node (Node (Node Leaf 2 Leaf)
           1
           (Node Leaf 2 Leaf))
     0
     (Node (Node Leaf 2 Leaf)
           1
           (Node Leaf 2 Leaf))

Or in a slightly different representation:

Ok, here is my attempt:

treeBuild :: Integer -> BinaryTree Integer
treeBuild n =
  unfold (\x -> if   x >= n
                then Nothing
                else Just (x+1, x, x+1)) 0

Good work.

12.6 Follow-up resources¶

Julie Moronuki and Chris Martin wrote a book called Finding Success and Failure. Over the course of the book you build an input validation program. It makes extensive use of Maybe, Either, and smart constructors. My impressions is that this book starts where the chapter leaves off, though I haven’t read it yet.
Thomas Heartman has notes about this chapter on his blog, here.
Stephen Diehl has a good example of smart constructors in his section about algebraic datatypes. Control-F for “smart constructors”.
Bartoz wrote an article about error handling.
Data.Either and Data.Maybe contain convenience functions for their respective types.

Chapter 12: Signaling adversity¶

12.1 Signaling adversity¶

12.2 How I learned to stop worrying and love Nothing¶

12.2.1 Smart constructors for datatypes¶

12.3 Bleating Either¶

12.4 Kinds, a thousand stars in your types¶

12.5 Chapter Exercises¶

12.5.1 Determine the kinds¶

12.5.2 String processing¶

12.5.3 Validate the word¶

12.5.4 It’s only Natural¶

12.5.5 Small library for Maybe¶

12.5.6 Small library for Either¶

12.5.7 Unfolds¶

12.5.8 Why bother?¶

12.5.9 Write your own iterate and unfoldr¶

12.5.10 Finally something other than a list!¶

12.6 Follow-up resources¶

hpfp

Navigation

Related Topics