9.1 Types

Remember the primitive types of Haskell? Here they are:

It’s possible to combine these primitive types in various ways to form more complex types. Function types, tuple types and list types are examples of types that combine other types.

There’s one more powerful mechanism for creating more types: Algebraic datatypes (ADTs). Some examples include:

-- Enumeration types
data Bool = True | False
data Color = Red | Green | Blue

-- Record types that contain fields
data Vector2d = MakeVector Double Double
data Person = Person Int String

-- Parameterized types. Note the type parameter `a`
data PairOf a = TwoValues a a

-- Recursive types
data IntList = Empty | Node Int IntList

-- Complex types which combine many of these features
data Maybe a = Nothing | Just a
data Either a b = Left a | Right b
data List a = Nil | Cons a (List a)             -- This is equivalent to the built-in [a] type
data Tree a = Leaf a | Node a (Tree a) (Tree a)
data MultiTree a = MultiTree a [MultiTree a]     -- Note the list

Values of these types include:

You can combine parameterized types in complex ways, for example with something like Either [String->String] (Maybe String, Int).

The names of concrete types start with capital letters. Lowercase letters are used for type variables which indicate parametric polymorphism: functions and values that can have multiple types. Here are some examples of polymorphic function types:

[a] -> [a]    -- function from list of any type, to list of the same type
[a] -> a      -- function from list of any type, to the element type
(a,b) -> [a]  -- function from tuple to list

9.2 Functions

The basic form of function definition is:

functionName :: argumentType -> returnType
functionName argument = returnValue

For example:

repeatString :: String -> String
repeatString s = s ++ s

Functions taking multiple arguments are defined in a similar manner. Note how the type of a multi-argument function looks like.

surroundString :: String -> String -> String
surroundString around s = around ++ s ++ around

Functions can be polymorphic, can take multiple arguments, and can even take functions as arguments. Here are more examples:

id :: a -> a
id x = x

const :: a -> b -> a
const x y = x

flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x

More sophisticated functions can be defined using pattern matching. We can pattern match on the constructors of algebraic datatypes like Maybe, and also lists with the constructors [] and (:).

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

maybe :: b -> (a -> b) -> Maybe a -> b
maybe def _ Nothing  = def
maybe _   f (Just x) = f x

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

Yet more sophistication can be achieved with guards. Guards let you define a function case-by-case based on tests of type Bool. Guards are useful in situations where pattern matching can’t be used. Of course, guards can also be combined with pattern matching:

myAbs :: Int -> Int
myAbs x
  | x < 0     = -x
  | otherwise = x

safeDiv :: Double -> Double -> Maybe Double
safeDiv x y
  | y == 0    = Nothing
  | otherwise = Just (x / y)

buy :: String -> Double -> String
buy "Banana" money
  | money < 3.2   = "You don't have enough money for a banana"
  | otherwise     = "You bought a banana"
buy product  _    = "No such product: " ++ product

Case expressions let us pattern match inside functions. They are useful in situations where the result of one function depends on the result of another and we want to match the pattern on the output of the other function:

divDefault :: Double -> Double -> Double -> Double
divDefault x y def = case safeDiv x y of
  Nothing -> def
  Just w  -> w

Let-expressions enable local definitions. Where-clauses work similarly to lets. For example:

circleArea :: Double -> Double
circleArea r = let pi = 3.1415926
                   square x = x * x
               in pi * square r

circleArea' :: Double -> Double
circleArea' r = pi * square r
    where pi = 3.1415926
          square x = x * x

Lambda expressions are another occasionally useful syntax for defining functions. Lambda expressions represent anonymous (unnamed) functions. They can be used for defining local functions that are typically used only once.

incrementAll :: [Int] -> [Int]
incrementAll xs = map (\x -> x + 1) xs

Note that f x = y is the same thing as f = \x -> y.

Finally, binary operators have sections. Sections are partially applied operators. The section of an operator is obtained by writing the operator and one of its arguments in parentheses. For example, (*2) multiplies its argument by 2 from the right, e.g. (*2) 5 ==> 5 * 2. A fractional number (e.g. a Double) can be inverted with the section (1/), e.g. (1/) 2 ==> 0.5.

incrementAll' :: [Int] -> [Int]
incrementAll' xs = map (+1) xs

9.3 Functional Programming

Haskell is a functional programming language, which means that functions can be passed in as arguments and returned from functions. As a programming paradigm, functional programming aims to build programs by combining simple functions together to form larger and larger ones.

The most often presented example of functional programming is functional list manipulation using higher-order functions (functions that take functions as arguments) like map and filter. Here’s one example from part 1:

-- a predicate that checks if a string is a palindrome
palindrome :: String -> Bool
palindrome str = str == reverse str

-- palindromes n takes all numbers from 1 to n, converts them to
-- strings using show, and keeps only palindromes
palindromes :: Int -> [String]
palindromes n = filter palindrome (map show [1..n])

palindromes 150
  ==> ["1","2","3","4","5","6","7","8","9",
       "11","22","33","44","55","66","77","88","99",
       "101","111","121","131","141"]

We also encountered other functional programming patterns in part 1, like partial application:

map (take 3) [[1,2,3,4,5],[6,7,8,9,0]]
  ==> [[1,2,3],[6,7,8]]

Also, function composition:

(map reverse . filter (/="Smith")) ["Jones","Smith","White"]
  ==> ["senoJ","etihW"]
map (negate . sum) [[1,2,3],[5]]
  ==> [-6,-5]

And finally, folds:

foldr (*) 1 [2,3,4]  ==> 24
foldr max 0 [1,3,7]  ==> 7
foldr (++) "" ["abc","de","f"] ==> "abcdef"

9.4 Recursion

To implement a function that uses repetition in Haskell, you need recursion. Haskell has no loops like other programming languages. Here are some simple recursive functions in Haskell:

repeatString :: Int -> String -> String
repeatString 0 s = ""
repeatString n s = s ++ repeatString (n-1) s

times :: Int -> Int -> Int
times 0 n = 0
times 1 n = n
times m n = n + times (m - 1) n

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

To consume or produce a list you often need recursion. Here are the implementations of map and filter as examples of recursive list processing:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

filter :: (a -> Bool) -> [a] -> [a]
filter _    []     = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

Sometimes, a recursive helper function is needed in case you need to keep track of multiple pieces of data.

sumNumbers :: [Int] -> Int
sumNumbers xs = go 0 xs
  where go sum [] = sum
        go sum (x:xs) = go (sum+x) xs

Here’s a final example utilizing guards, pattern matching, a helper function and recursion:

-- split a string into pieces at the given character
mySplit :: Char -> String -> [String]
mySplit c xs = helper [] xs
  where helper piece [] = [piece]
        helper piece (y:ys)
          | c == y    = piece : helper [] ys
          | otherwise = helper (piece++[y]) ys

mySplit '-' "a-bcd-ef"  ==>  ["a","bcd","ef"]

9.5 Type Classes

The following functions are parametrically polymorphic:

id :: a -> a
id x = x

head :: [a] -> a
head (x:_) = x

fst :: (a,b) -> a
fst (x,y) = x

Parametrically polymorphic functions always work the same way, no matter what types we’re working with. This means that we can’t define a special implementation of id just for the Int type, or fst for the type (Bool, String).

By contrast, ad hoc polymorphism allows different types to have different implementations of the same function. Ad hoc polymorphism in Haskell can be achieved by defining a type class and then declaring instances of that type class for various types. Ad hoc polymorphism is a handy way for expressing a common set of operations, even when the implementation of the operations depends on the type they’re acting on.

Functions that use ad hoc polymorphism have a class constraint in their types. Here are some examples:

negate :: Num a => a -> a
(==) :: Eq a => a -> a -> Bool
sort :: Ord a => [a] -> [a]

A type like Num a => a -> a means: for any type X that’s a member of the Num class, this function has type X -> X. In other words, we can invoke negate on any number type, but not on other types:

Prelude> negate 1
-1
Prelude> negate 1.0
-1.0
Prelude> negate True
<interactive>:3:1: error:
    • No instance for (Num Bool) arising from a use of ‘negate’

Here’s a summary of some useful type classes from the standard library.

• Comparison
  • Eq is for equality comparison. It contains the == operator
  • Ord is for order comparison. It contains the ordered comparison operators like < and =>, and functions like max and min.
• Numbers
  • Num is for all number types. It contains +, -, * and negate.
  • Integral is for whole number types. Most notably, it contains integer division div.
  • Fractional is for number types that support division, /
• Converting values to strings
  • Show contains the function show :: Show a => a -> String that converts values to strings
  • Read contains the function read :: Read a => String -> a that is the inverse of show

Sometimes, multiple class constraints are needed. For instance here:

sumTwoSmallest :: (Num a, Ord a) => [a] -> a
sumTwoSmallest xs = let (a:b:_) = sort xs
                    in a+b

Now that we’ve seen some classes and types, let’s look at the syntax of declaring classes and instances. Here are two class definitions:

class Sized a where
  empty :: a        -- a thing with size 0
  size :: a -> Int

class Eq a where
  (==) :: a -> a -> Bool

Consider the following data structures:

data Numbers = None | One Int | Two Int Int
data IntList = Nil | ListNode Int IntList
data Tree a = Leaf | Node a (Tree a) (Tree a)

All of these have sizes that we can count, but we need to perform the operation differently:

instance Sized Numbers where
  empty = None
  size None      = 0
  size (One _)   = 1
  size (Two _ _) = 2

instance Sized IntList where
  empty = Nil
  size Nil               = 0
  size (ListNode _ list) = 1 + size list

instance Sized (Tree a) where
  empty = Leaf
  size Leaf = 0
  size (Node _ left right) = 1 + size left + size right

We can also easily declare Eq instances for Numbers and IntList:

instance Eq Numbers where
  None      == None       = True
  (One x)   == (One y)    = x==y
  (Two x y) == (Two z w)  = x==z && y==w
  _         == _          = False         -- to handle cases like None == One 1

instance Eq IntList where
  Nil             == Nil               = True
  (ListNode x xs) == (ListNode y ys)   = x == y && xs == ys
  _               == _                 = False

However, since the Tree datatype is parameterized over the element type a, we need an Eq a instance in order to have an Eq (Tree a) instance. This is achieved by adding a class constraint to the instance declaration. This is called an instance hierarchy.

instance Eq a => Eq (Tree a) where
  Leaf         == Leaf              = True
  (Node x l r) == (Node x' l' r')   = x == x' && l == l' && r == r'
  _            == _                 = False

data Numbers = None | One Int | Two Int Int
  deriving (Show, Read, Eq, Ord)

None == One 1       ==> False
Two 1 2 == Two 1 2  ==> True
None < Two 1 2      ==> True
Two 1 3 < Two 1 2   ==> False
show (Two 1 3)      ==> "Two 1 3"

9.6 Quiz

What is the type of ('c',not)

1. [Char]
2. [Bool]
3. (Char,Bool -> Bool)
4. (Char,Bool)
5. It is a type error.

What is the type of ['c',not]

1. [Char]
2. [Bool]
3. (Char,Bool -> Bool)
4. (Char,Bool)
5. It is a type error.

Which of these is a value of the following type?

data T = X Int | Y String String | Z T

1. X "foo"
2. Y "foo"
3. Z (X 1)
4. X (Z 1)

What is the type of this function?

f (_:Just x:_) = x
f _            = False

1. Maybe a -> a
2. [Maybe a] -> a
3. [Maybe a] -> Bool
4. [Maybe Bool] -> Bool

What is the type of this function?

f x y = x-y == 0

1. (Num a, Eq a) => a -> a -> Bool
2. Num a => a -> a -> Bool
3. Eq a => a -> a -> Bool
4. a -> a -> Bool

Which of the following types can x have in order for x (&&) y to not be a type error?

1. Bool
2. Bool -> Bool -> Bool
3. (Bool -> Bool -> Bool) -> Bool -> Bool

9.7 Working on the Exercises

Here’s a short recap of how to work on the exercises. The system is the same as for part 1 of the course.

1. Clone the GitHub repository https://github.com/moocfi/haskell-mooc
2. Go to the exercises/ directory
3. Run stack build to download dependencies
4. Edit the file Set9a.hs
5. Check your answers by running stack runhaskell Set9aTest.hs
6. Return your answers on the Submit page
7. Repeat as necessary. You can work on the exercise sets in any order, and you can return the sets as many times as you want!
8. You can see total score on the My status page

9.8 Exercises

• Set9a - small exercises that recap part 1 of the course
• Set9b - let’s solve the N Queens puzzle!

10.1 Laziness & Purity

Purity and laziness were mentioned as key features of Haskell in the beginning of part 1. Let’s take a closer look at them.

Haskell is a pure functional language. This means that the value f x y is always the same for given x and y. In other words, the values of x and y uniquely determine the value of f x y. This property is also called referential transparency.

Purity also means that there are no side effects: you can’t have the evaluation of f x y read a line from the user - the line would be different on different invocations of f and would affect the return value, breaking referential transparency! Obviously you need side effects to actually get something done. We’ll get back to how Haskell handles side effects later.

Haskell is a lazy language. This means that a value is not evaluated if it is not needed. An example illustrates this best. Consider these two functions:

f x = f x   -- infinite recursion
g x y = x

Evaluating f 1 does not halt due to the infinite recursion. However, this works:

g 2 (f 1)  ==>  2

Laziness is not a problem because Haskell is pure. Only the result of the function matters, not the side effects. So if the result of a function is not used, we can simply not evaluate it without changing the meaning (semantics) of a program. Well okay, sometimes we get a terminating program instead of one that goes on for ever, but adding laziness never makes a functioning Haskell program break.

If you’re interested in the theory behind this, check out the Church-Rosser theorem or the Haskell Wiki article Lazy vs. non-strict.

10.2 Equational Reasoning

Referential transparency, the feature that an expression always returns the same value for the same inputs, is a very powerful property that we can leverage to reason about programs.

In a C-style language, we might write a procedure that may not always return the same value for the same arguments:

int c = 0;
int funny(int x) {
  return x + c++;
}

The expression c++ increments the value of c and returns the old value of c. The next time it is evaluated, the value of c has increased by one. This means that depending on the current value of c, funny(0) might return 0, 1, 2, or any other integer value. (It might even return negative values if c overflows!)

In some situations this kind of behaviour with side-effects may be useful, but there are also times when it is more important to be able to reason about the code easily. The advantage of pure functions is that they can be analyzed using basic mathematical techniques. Sometimes applying math to our functions can even reveal simplifications or optimisations we otherwise wouldn’t have thought about.

Consider the following expression:

map (+1) . reverse . map (-1)

This expression can be simplified to just reverse. We begin by establishing some helpful facts (or lemmas). First, suppose that we know

1. map id === id
2. map f . map g === map (f.g)
3. reverse . map f === map f . reverse

The fourth fact that we’re going to need is the following:

4. (+1) . (-1) === id

We can prove fact 4 by reasoning about how (+1) . (-1) behaves for an arbitrary input x:

((+1) . (-1)) x === ((+1) ((-1) x))
                === ((+1) (x - 1))
                === (x - 1) + 1
                === x
                === id x

Because we didn’t assume anything about x, we may conclude that the above chain of equations holds for every x. Thus,

(+1) . (-1) === id

For those who are familiar with the technique of proof by induction, it is a fun exercise to prove the first three facts also. This course doesn’t discuss induction proofs, though, so don’t sweat if you don’t know induction.

Now, from facts 1-4 it follows that

    map (+1) . reverse . map (-1)
=== map (+1) . (reverse . map (-1))    -- By associativity of (.)
=== map (+1) . (map (-1) . reverse)    -- By fact 3
=== (map (+1) . map (-1)) . reverse    -- By associativity of (.)
=== map ((+1) . (-1)) . reverse        -- By fact 2
=== map id . reverse                   -- By fact 4
=== id . reverse                       -- By fact 1
=== reverse                            -- By the definition of id

This course won’t go into details about proving things about programs, but it’s good to know that pure functional programming is very compatible with analysis like this.

10.3 Infinite Lists

The benefits of laziness are best demonstrated with some examples involving infinite lists. Let’s start with repeat 1, which generates an infinite list of 1s. If we try to tell GHCi to print the value repeat 1, it will just keep printing 1s for ever until we interrupt it using Control-C:

Prelude> repeat 1
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
^C

However, due to laziness, we can work with infinite lists and write computations that end. We just need to use a finite number of elements from the infinite list. Here are some examples:

Prelude> take 10 $ repeat 1
[1,1,1,1,1,1,1,1,1,1]
Prelude> take 20 $ repeat 1
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
Prelude> repeat 1 !! 13337
1

An infinite list that just repeats one element can sometimes be necessary, but it’s kind of pointless. Let’s look at some more useful infinite lists next. You can use the [n..] syntax to generate an infinite list of numbers, starting from n:

Prelude> take 20 [0..]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]
Prelude> take 10 . map (2^) $ [0..]
[1,2,4,8,16,32,64,128,256,512]

The function cycle repeats elements from the given list over and over again. It can be useful when dealing with rotations or cycles.

Prelude> take 21 $ cycle "asdf"
"asdfasdfasdfasdfasdfa"
Prelude> take 4 . map (take 4) . tails $ cycle "asdf"
["asdf","sdfa","dfas","fasd"]

digits:       1  1  6  1  2
              *  *  *  *  *
multipliers:  3  7  1  3  7
              3+ 7+ 6+ 3+14 = 33
check digit is 7, 33+7=40 is divisible by 10, valid

viitenumeroCheck :: [Int] -> Bool
viitenumeroCheck allDigits = mod (checksum+checkDigit) 10 == 0
  where (checkDigit:digits) = reverse allDigits
        multipliers = cycle [7,3,1]
        checksum = sum $ zipWith (*) multipliers digits

viitenumeroCheck [1,1,6,1,2,7]  ==> True
viitenumeroCheck [1,1,6,1,2,8]  ==> False

Prelude> head . filter (>100) $ map (3^) [0..]
243

    head (filter (>100) (map (3^) [0..]))
==> head (filter (>100) (map (3^) (0:[1..])))   -- evaluate first element of the lazy list
==> head (filter (>100) (1 : map (3^) [1..]))   -- map processes the element
==> head (filter (>100) (map (3^) [1..]))       -- filter drops the element
==> head (filter (>100) (map (3^) (1:[2..])))   -- evaluate second element of the lazy list
==> head (filter (>100) (3 : map (3^) [2..]))   -- map processes the element
==> head (filter (>100) (map (3^) [2..]))       -- filter drops the element
-- let's take bigger steps now
==> head (filter (>100) (9 : map (3^) [3..]))   -- map processes, filter will drop
==> head (filter (>100) (27 : map (3^) [4..]))  -- map processes, filter will drop
==> head (filter (>100) (81 : map (3^) [5..]))  -- map processes, filter will drop
==> head (filter (>100) (243 : map (3^) [6..])) -- map processes
==> head (243 : filter (>100) (map (3^) [6..])) -- filter lets the value through
==> 243                                         -- head returns the result

10.4 How does Haskell Work?

Laziness will probably feel a bit magical to you right now. You might wonder how it can be implemented. Haskell evaluation is remarkably simple, it’s just different than what you might be used to. Let’s dig in.

In most other programming languages (like Java, C or Python), evaluation proceeds inside-out. Arguments to functions are evaluated before the function.

Haskell evaluation proceeds outside-in instead of inside-out. The definition of the outermost function in an expression is applied without evaluating any arguments. Here’s a concrete example with toy functions f and g:

g :: Int -> Int -> Int
g x y = y+1
f :: Int -> Int -> Int -> Int
f a b c = g (a*1000) c

Inside-out (normal) evaluation:

f 1 (1234*1234) 2
  -- evaluate arguments to f
  ==> f 1 1522756 2
  -- evaluate f
  ==> g (1*1000) 2
  -- evaluate arguments to g
  ==> g 1000 2
  -- evaluate g
  ==> 2+1
  ==> 3

Haskell outside-in evaluation:

f 1 (1234*1234) 2
  -- evaluate f without evaluating arguments
  ==> g (1*1000) 2
  -- evaluate g without evaluating arguments
  ==> 2+1
  ==> 3

Note how the unused calculations 1234*1234 and 1*1000 didn’t get evaluated. This is why laziness is often helpful.

not True = False
not False = True
map f [] = []
map f (x:xs) = f x : map f xs
length [] = 0
length (x:xs) = 1+length xs

length (map not (True:False:[]))
  ==> length (not True : not False : [])  -- evaluate call to map
  ==> length (False:True:[])              -- evaluate calls to not
  ==> 2

length (map not (True:False:[]))
  -- We can't evaluate length since we don't know which equation of length applies,
  -- so we look at length's argument. We can apply the second equation of map, so we do.
  ==> length (not True : map not (False:[]))
  -- Now the argument of length has a (:) we can pattern match on, so we apply the
  -- second equation of length
  ==> 1 + length (map not (False:[]))
  -- The outermost function is now +, but it can't do anything unless both arguments
  -- are numbers. So we need to evaluate length. In order to pick an equation, we need
  -- to evaluate the argument of length again. We apply the second equation of map
  ==> 1 + length (not False : map not ([]))
  -- Now we can apply the second equation of length again.
  ==> 1 + (1 + length (map not []))
  -- The outermost + needs a number to be evaluated. The second + also needs a number.
  -- We need to evaluate length again, which means we need to pick an equation for length,
  -- which means we need to evaluate its argument. This time it is the first equation for
  -- map that applies.
  ==> 1 + (1 + length [])
  -- Now we can apply the first equation for length
  ==> 1 + (1 + 0)
  -- The outermost + still can't be evaluated, but the inner one can
  ==> 1 + 1
  -- Finally we evaluate the outer +
  ==> 2

square x = x*x

square (2+2)
  ==> (2+2) * (2+2)   -- definition of square
  ==>   4   * (2+2)   -- (*) forces left argument
  ==>   4   *   4     -- (*) forces right argument
  ==>      16         -- definition of (*)

square (2+2)
  ==> (2+2) * (2+2)
  ==>   4   *   4
  ==>      16

f :: Int -> Int
f i = if i>10 then 10 else i

                  _______shared________
                 |                     |
f (1+1) ==> if (1+1)>10 then 10 else (1+1)
        ==> if 2>10 then 10 else 2
        ==> if False then 10 else 2
        ==> 2

g :: Int -> Int
g i j = if i>10 then 10 else j

                        ______no sharing_____
                       |                     |
g (1+1) (1+1) ==> if (1+1)>10 then 10 else (1+1)
              ==> if 2>10 then 10 else (1+1)
              ==> if False then 10 else (1+1)
              ==> (1+1)
              ==> 2

not :: Bool -> Bool
not True = False
not False = True

(||) :: Bool -> Bool -> Bool
True || _ = True
_    || x = x

even :: Int -> Bool
even x  =  x == 0  ||  not (even (x-1))

even 2
==> 2 == 0  ||  not (even (2-1))                    -- apply definition of even
==> False   ||  not (even (2-1))                    -- || forces its first argument
==> not (even (2-1))                                -- second equation of ||
==> not ((2-1) == 0 || not (even ((2-1)-1)))        -- not forces its argument: apply definition of even
==> not (  1   == 0 || not (even (  1  -1)))        -- note sharing!
==> not (  False    || not (even (1-1)))
==> not (not (even (1-1)))
==> not (not ((1-1) == 0 || not (even ((1-1)-1))))
==> not (not (  0   == 0 || not (even (  0  -1))))  -- (sharing)
==> not (not (   True    || not (even (0-1))))
==> not (not True)
==> not False
==> True

even' x =  not (even' (x-1))  ||  x == 0

head (x:_) = x
head [] = -1

filter p [] = []
filter p (x:xs) = if p x
                  then x : filter p xs
                  else filter p xs

map f [] = []
map f (x:xs) = f x : map f xs

-- [0..] is syntax sugar for enumFrom 0
enumFrom n = n : enumFrom (n+1)

    head (filter (>100) (map (3^) [0..]))
=== head (filter (>100) (map (3^) (enumFrom 0)))
-- head forces filter, which forces map, which forces enumFrom. We apply the definition of enumFrom.
==> head (filter (>100) (map (3^) (0:[1..])))
-- head forces filter, which forces map. We apply the second equation of map.
==> head (filter (>100) ((3^0) : map (3^) [1..]))
-- head forces filter. We apply the second equation of filter
==> head (if ((3^0)>100)
          then (3^0) : filter (>100) (map (3^) [1..])
          else filter (>100) (map (3^) [1..]))
-- head forces if, if forces >, > forces ^. Note sharing!
==> head (if (1>100)
          then 1 : filter (>100) (map (3^) [1..])
          else filter (>100) (map (3^) [1..]))
-- head forces if, if forces >
==> head (if False
          then 1 : filter (>100) (map (3^) [1..])
          else filter (>100) (map (3^) [1..]))
-- apply definition of if
==> head (filter (>100) (map (3^) [1..]))
-- let's take slightly bigger steps now
==> head (filter (>100) (map (3^) (1:[2..])))
==> head (filter (>100) ((3^1) : map (3^) [2..]))
==> head (filter (>100) (3 : map (3^) [2..]))
==> head (filter (>100) (map (3^) [2..]))
-- and even bigger steps now
==> head (filter (>100) (9 : map (3^) [3..]))
==> head (filter (>100) (27 : map (3^) [4..]))
==> head (filter (>100) (81 : map (3^) [5..]))
==> head (filter (>100) (243 : map (3^) [6..]))
==> head (243 : filter (>100) (map (3^) [6..]))
==> 243

10.5 Working with Infinite Lists

Functions that work with lists often have the best performance when they’re written in such a way that they utilize laziness. One way to try to accomplish this is to write list-handling functions that work well with infinite lists.

To write a function that transforms an infinite list, you need to write a function that only looks at a limited prefix of the input list, then outputs a (:) constructor, and then recurses. Here’s a first example.

everySecond :: [a] -> [a]
everySecond [] = []
everySecond (x:y:xs) = x : everySecond xs

take 10 (everySecond [0..])  ==>  [0,2,4,6,8,10,12,14,16,18]

A good heuristic for writing functions that work well with infinite lists is: can the head of the result be evaluated cheaply? Here are two examples of functions that don’t work with infinite inputs. In the case of mapTailRecursive, the problem is that it needs to process the whole input before being in WHNF. In the case of myDrop, the problem is that it uses the function length, doesn’t work for infinite lists since it tries to iterate until the end of the list.

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

mapTailRecursive :: (a -> b) -> [a] -> [b]
mapTailRecursive f xs = go xs []
    where go (x:xs) res = go xs (res++[f x])
          go []     res = res

head (map inc [0..]) ==> head (inc 0 : map inc [1..]) ==> inc 0 ==> 1
head (mapTailRecursive inc [0..])
  ==> head (go [0..] [])
  ==> head (go [1..] ([]++[inc 0]))
  ==> head (go [2..] ([]++[inc 0]++[inc 1]))
  ==> head (go [3..] ([]++[inc 0]++[inc 1]++[inc 2]))
  --  never terminates

drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (x:xs) = drop (n-1) xs

myDrop :: Int -> [a] -> [a]
myDrop 0 xs = xs
myDrop n xs = if n > length xs then [] else myDrop (n-1) (tail xs)

head (drop 2 [0..]) ==> head (drop 1 [1..]) ==> head (drop 0 [2..]) ==> head [2..] ==> 2
head (myDrop 2 [0..])
  ==> head (if n > length [0..] then [] else myDrop (n-1) (tail [0..]))
  ==> head (if n > 1+length [1..] then [] else myDrop (n-1) (tail [0..]))
  ==> head (if n > 1+1+length [2..] then [] else myDrop (n-1) (tail [0..]))
  ==> head (if n > 1+1+1+length [3..] then [] else myDrop (n-1) (tail [0..]))
  --  never terminates

Pretty much all the list functions in the standard library are written in this form, for example:

head (takeWhile (>=0) [0..]) ==> 0
head (concat (repeat [1,2,3])) ==> 1
head (zip [0..] [2..]) ==> (0,2)
head (filter even [3..]) ==> 4

10.6 Interlude: Adding Strictness

Remember foldr from part 1? Let’s have a look at its cousin foldl. Here’s the definition of foldl for lists (it’s actually part of the Foldable typeclass and so works for various other types too). While foldr processes a list right-to-left, foldl processes a list left-to-right. To be a bit more exact, foldr associates to the right while foldl associates to the left. Note the difference in the next example:

foldr (+) 0 [1,2,3]  ==>  1+(2+(3+0))
foldl (+) 0 [1,2,3]  ==>  ((0+1)+2)+3

Here are the definitions of foldl and foldr:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f y []     = y
foldr f y (x:xs) = f x (foldr f y xs)

As foldr f y (x:xs) ==> f x (foldr f y xs), it enables lazy evaluation to focus on f on the second step. Hence, foldr works nicely with lazy or short-circuiting operations:

    foldr (&&) True [False,False,False]
==> False && (foldr (&&) True [False,False])
==> False

    head (foldr (++) [] ["Hello","World","lorem","ipsum"])
==> head ("Hello" ++ (foldr (++) [] ["World","lorem","ipsum"]))
==> head ('H':("ello" ++ (foldr (++) [] ["World","lorem","ipsum"])))
==> 'H'

However foldl needs to process the whole list in order to produce a (WHNF) value. The reason is that foldl remains in the leftmost-outermost position for as long as its list argument remains non-empty. This makes foldl the priority for lazy evaluation. Only after the list becomes empty does the evaluation proceed into simplifying the folded values.

    foldl (&&) True [False,False,False]
==> foldl (&&) (True&&False) [False,False]
==> foldl (&&) ((True&&False)&&False) [False]
==> foldl (&&) (((True&&False)&&False)&&False) []
==> ((True&&False)&&False)&&False
==> (    False    &&False)&&False
==>              False    &&False
==>                      False

    head (foldl (++) [] ["Hello","World","lorem","ipsum"])
==> head (foldl (++) ([]++"Hello") ["World","lorem","ipsum"])
==> head (foldl (++) (([]++"Hello")++"World") ["lorem","ipsum"])
==> head (foldl (++) ((([]++"Hello")++"World")++"lorem") ["ipsum"])
==> head (foldl (++) (((([]++"Hello")++"World")++"lorem")++"ipsum") [])
==> head (((([]++"Hello")++"World")++"lorem")++"ipsum")
-- head forces the last ++, which forces the next-to-last ++, and so on
==> head ((("Hello"++"World")++"lorem")++"ipsum")
-- same happens again
==> head ((('H':("ello"++"World"))++"lorem")++"ipsum")
-- for clarity, let's drop the "ello"++"World" expression which isn't needed
==> head ((('H':__)++"lorem")++"ipsum")
-- now the next-to-last ++ can operate
==> head (('H':(__++"lorem"))++"ipsum")
-- let's drop the __++"lorem" expression
==> head (('H':__)++"ipsum")
-- now the last ++ can operate
==> head ('H':(__++"ipsum"))
==> 'H'

So why use foldl at all? Let’s return to our first fold example again. Now, since + is a strict operation, both types of fold need to build up an expression with lots of +s. The Haskell implementation needs to track this expression in memory, which is why a problem like this is called a space leak.

    foldr (+) 0 [1,2,3]
==> 1 + foldr (+) 0 [2,3]
==> 1 + (2 + foldr (+) 0 [3])
==> 1 + (2 + (3 + foldr (+) 0 []))
==> 1 + (2 + (3 + 0))
==> 1 + (2 + 3)
==> 1 + 5
==> 6

    foldl (+) 0 [1,2,3]
==> foldl (+) (0+1) [2,3]
==> foldl (+) ((0+1)+2) [3]
==> foldl (+) (((0+1)+2)+3) []
==> ((0+1)+2)+3
==> (  1  +2)+3
==>       3  +3
==>          6

Now let’s instead look at what happens when we use foldl', a version of foldl that forces its second argument!

    foldl' (+) 0 [1,2,3]
==> foldl' (+) (0+1) [2,3]
-- force second argument
==> foldl' (+) 1 [2,3]
==> foldl' (+) (1+2) [3]
-- force second argument
==> foldl' (+) 3 [3]
==> foldl' (+) (3+3) []
-- force second argument
==> foldl' (+) 6 []
==> 6

Now the work is performed incrementally while scanning the list. No space leak! Sometimes too much laziness can cause space leaks, and a bit of strictness can fix them.

You can find foldl' in the Data.List module, and it works just like this. But how could one implement foldl'? We certainly know by now how to do it for a specific type, say Int. We just add a pattern match on the second argument that doesn’t change the semantics of the function.

foldl'Int :: (Int -> Int -> Int) -> Int -> [Int] -> Int
foldl'Int f z [] = z
foldl'Int f 0 (x:xs) = foldl'Int f (f 0 x) xs
foldl'Int f z (x:xs) = foldl'Int f (f z x) xs

    foldl'Int (+) 0 [1,2,3]
==> foldl'Int (+) (0+1) [2,3]
-- to be able to pick between the second and third equations, (0+1) is forced
==> foldl'Int (+) 1 [2,3]
-- the third equation applies
==> foldl'Int (+) (1+2) [3]
-- again, we need to pick between the second and third equations
==> foldl'Int (+) 3 [3]
==> foldl'Int (+) (3+3) []
==> 3+3
==> 6

To write a generic implementation of foldl' we need to introduce a new built-in function, seq. The call seq a b evaluates to b but forces a into WHNF. Here are some examples of using seq in GHCi. To demonstrate what gets evaluated, we use the special value undefined, which causes an error if something tries to evaluate it into WHNF.

Prelude> seq (not True) 3
3
Prelude> seq undefined 3
*** Exception: Prelude.undefined
Prelude> (seq (not True) 3) + 7
10
Prelude> (seq undefined 3) + 7
*** Exception: Prelude.undefined
Prelude> let f x = f x in seq (f 3) 3
-- ...infinite recursion

As an example of using seq in a function, here’s a version of head that doesn’t work for infinite lists (since it evaluates the last element of the list):

strictHead :: [a] -> a
strictHead xs = seq (last xs) (head xs)

Let’s play around with it in GHCi:

Prelude> head [1,2,3]
1
Prelude> strictHead [1,2,3]
1
Prelude> head (1:2:undefined)
1
Prelude> strictHead (1:2:undefined)
*** Exception: Prelude.undefined
Prelude> head [1..]
1
Prelude> strictHead [1..]
-- ...infinite recursion

Finally, here’s a definition for foldl'. Note how we need to introduce sharing of a new variable, z', to be able to make seq evaluate the new value and then use it in a recursive call. The new definition is also used in a more detailed evaluation of foldl' (+) 0 [1,2,3] below.

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f z [] = z
foldl' f z (x:xs) = let z' = f z x
                    in seq z' (foldl' f z' xs)

    foldl' (+) 0 [1,2,3]
==> seq (0+1) (foldl' (+) (0+1) [2,3])  -- seq forces first argument
          |                 |
          +-----sharing-----'
          |                 |
==> seq   1   (foldl' (+)   1   [2,3])  -- first argument to seq in WHNF, seq disappears
==> foldl' (+) 1 [2,3]
==> seq (1+2) (foldl' (+) (1+2) [3])
==> seq   3   (foldl' (+)   3   [3])
==> foldl' (+)   3   [3]
==> seq (3+3) (foldl' (+) (3+3) [])
==> seq   6   (foldl' (+)   6   [])
==> foldl' (+)   6   []
==> 6

We won’t dive deeper into this subject on this course, but it’s important that you’re aware that seq exists. You can find more about seq on the Haskell Wiki and learn more about when it is necessary to add strictness in Real World Haskell. Often it’s nicer to use bang patterns instead of seq, as discussed by FPComplete and Real World Haskell.

10.7 Newtype Declarations

Recall lecture 7. Sometimes we need boxed types. There’s a special keyword newtype that can be used instead of data when a boxed type is needed. newtype expects exactly one constructor, with exactly one field. For instance,

newtype Money = Cents Int

However, the following won’t work, you need data:

-- the compiler won't accept these!
newtype Currency = Dollars Int | Euros Int
newtype Money = Money Int Int

So what’s the difference? In terms of writing code, nothing. You work with a newtype exactly as you would with a data. However, the memory layout is different. Using data introduces an indirection layer (the constructor), but using newtype doesn’t. The indirection for data is necessary to support multiple constructors and multiple fields. An illustration:

code:                                 memory:

data Money = Cents Int                x --> Cents --> 100
x = Cents 100


newtype Money = Cents Int             x --> 100
x = Cents 100

This difference has many repercussions. First of all, newtype is more efficient: the type can be said to “disappear” when compiling. The type is still checked though, so you get type safety without any performance impact. Secondly, newtypes are strict. Concretely, this means that Money x is in weak head normal form only if x is in WHNF. This can be witnessed in GHCi:

-- if we use data, Cents undefined is in WHNF
Prelude> data Money = Cents Int
Prelude> seq (Cents undefined) True
True
-- if we use newtype, Cents undefined isn't in WHNF, and trying
-- to make it so trips up in undefined
Prelude> newtype Money = Cents Int
Prelude> seq (Cents undefined) True
*** Exception: Prelude.undefined

So when should you use newtype? In general it’s best to use newtype whenever you have a single-field single-constructor datatype. However nothing will go catastrophically wrong if you always use data. The newtype pattern is also often used when you need to define a different type class instance for a type. Here’s an example that defines a number type with an inverted ordering

newtype Inverted = Inverted Int
  deriving (Show, Eq)

instance Ord Inverted where
  compare (Inverted i) (Inverted j) = compare j i

Prelude Data.List> sort [1,2,3]
[1,2,3]
Prelude Data.List> sort [Inverted 1,Inverted 2,Inverted 3]
[Inverted 3,Inverted 2,Inverted 1]

10.8 Something Fun: Tying the Knot

Now that we know about sharing and path copying, we can make our own cyclic datastructures. Remember the cycle examples from the list lecture?

Prelude> take 21 $ cycle "asdf"
"asdfasdfasdfasdfasdfa"

This is what it looks like in memory:

Earlier it was said that Haskell data forms directed graphs in memory. This is an example of a directed graph with a cycle.

How can we define structures like this? We just give a value a name, and refer to that name in the value itself. That is, the value is recursive or self-referential. This trick is known as tying the knot. A simple example:

  code                     memory

let xs = 1:2:xs      xs -> (1:) -> (2:) -+
 in xs                      ^            |
                            +------------+

Note how we use the name xs inside the definition of xs. When we make a recursive definition like this, sharing causes it to turn into a cyclic structure in memory.

A more fun example: a simple adventure game where the world is a self-referential structure. Note how the cyclic structure is built with local definitions that refer to each other.

data Room = Room String [(String,Room)]

describe :: Room -> String
describe (Room s _) = s

move :: Room -> String -> Maybe Room
move (Room _ directions) direction = lookup direction directions

world :: Room
world = meadow
  where
    meadow = Room "It's a flowery meadow next to a cliff." [("Stay",meadow),("Enter cave",cave)]
    cave = Room "You are in a cave" [("Exit",meadow),("Go deeper",tunnel)]
    tunnel = Room "This is a very dark tunnel. It seems you can either go left or right."
                  [("Go back",cave),("Go left",pit),("Go right",treasure)]
    pit = Room "You fall into a pit. There is no way out." []
    treasure = Room "A green light from a terminal fills the room. The terminal says <<loop>>."
                    [("Go back",tunnel)]

play :: Room -> [String] -> [String]
play room [] = [describe room]
play room (d:ds) = case move room d of Nothing -> [describe room]
                                       Just r -> describe room : play r ds

Prelude> play world ["Stay","Enter cave","Go deeper","Go back","Go deeper","Go right"]
["It's a flowery meadow next to a cliff.",
 "It's a flowery meadow next to a cliff.",
 "You are in a cave",
 "This is a very dark tunnel. It seems you can either go left or right.",
 "You are in a cave",
 "This is a very dark tunnel. It seems you can either go left or right.",
 "A green light from a computer terminal floods the room. The terminal says <<loop>>."]

Here’s what the world of the game looks like in memory:

               ,-----------------,
               v                 |
         +-----------------------|-----------------+
meadow-->|Room "It's..." ["Stay" o, "Enter cave" o]|
         +---------------------------------------|-+
                                    ^            v
         +--------------------------|----------------+
cave---->|Room "You are..." ["Exit" o, "Go deeper" o]|
         +-----------------------------------------|-+
                                       ^           v
         +-----------------------------|----------------------------+
tunnel-->|Room "This is..." ["Go back" o, "Go left" o, "Go right" o]|<--------,
         +------------------------------------------|-------------|-+         |
                                                    |             |           |
                     ,------------------------------'             |           |
                     v                                            v           |
         +---------------------+                +-----------------------------|-+
pit----->|Room "You fall..." []|    treasure--->|Room "A green..." ["Go back" o]|
         +---------------------+                +-------------------------------+

We’ve now seen three types of recursion. Recursive functions call themselves. Recursive types allow us to express arbitarily large structures. Recursive values are one way to implement infinite structures.

10.9 Something Fun: Debug.Trace

Even though Haskell is a pure programming language, we can sometimes gain insights by sprinkling in a bit of impurity.

We can use the function trace :: String -> a -> a from the module Debug.Trace to peek into Haskell evaluation. The expression trace "message" x is the same as x, but prints message when it is evaluated (forced). We can use trace to witness the laziness of the || operator:

Prelude> import Debug.Trace
Prelude Debug.Trace> trace "a" True
a
True
Prelude Debug.Trace> trace "a" False || trace "b" True
a
b
True
Prelude Debug.Trace> trace "a" True || trace "b" True
a
True

We can also have a look at when list elements are evaluated. Note how length doesn’t need to evaluate the elements of the list, and sum needs to evaluate all of them. (To be precise, head xs doesn’t actually evaluate the first element of xs, but returns it to GHCi, which evaluates it in order to show it.)

Prelude Debug.Trace> head [trace "first" 1, trace "second" 2, trace "third" 3]
first
1
Prelude Debug.Trace> last [trace "first" 1, trace "second" 2, trace "third" 3]
third
3
Prelude Debug.Trace> length [trace "first" 1, trace "second" 2, trace "third" 3]
3
Prelude Debug.Trace> sum [trace "first" 1, trace "second" 2, trace "third" 3]
third
second
first
6

Debug.Trace also offers useful variants of trace. A notable one is traceShowId x which prints show x and evaluates to x. Let’s verify the evaluation of our previous head-filter-map example using traceShowId. Note how even though we map traceShowId over the infinite list [0..], only 6 values are actually evaluated. The last 243 is the returned value, not a trace print.

Prelude Debug.Trace> head (filter (>100) (map (\x -> traceShowId (3^x)) [0..]))
1
3
9
27
81
243
243

Debug.Trace is especially useful when you have an infinite recursion bug. Here’s an example:

-- computes sums like 7+5+3+1
sumEverySecond :: Int -> Int
sumEverySecond 0 = 0
sumEverySecond n = n + sumEverySecond (n-2)

sumEverySecond 6 ==> 12
sumEverySecond 7 ==> doesn't terminate

We can debug this by adding a trace to wrap the whole recursive case.

sumEverySecond :: Int -> Int
sumEverySecond 0 = 0
sumEverySecond n = trace ("sumEverySecond "++show n) (n + sumEverySecond (n-2))

Prelude Debug.Trace> sumEverySecond 6
sumEverySecond 6
sumEverySecond 4
sumEverySecond 2
12
Prelude Debug.Trace> sumEverySecond 7
sumEverySecond 7
sumEverySecond 5
sumEverySecond 3
sumEverySecond 1
sumEverySecond -1
sumEverySecond -3
sumEverySecond -5
-- and so on

A ha! The problem is that our recursion base case of sumEverySecond 0 is not enough to stop the recursion.

Finally, a word of caution. Using trace, and especially traceShowId, can cause things that would not otherwise get evaluated to get evaluated. For example:

Prelude Debug.Trace> traceHead xs = head (traceShowId xs)
Prelude Debug.Trace> traceHead [0..]
-- never terminates since it's trying to show an infinite list

So feel free to use Debug.Trace when working on the exercises, but try to leave trace calls out of your final answers. Some exercise sets check your imports and disallow Debug.Trace.

We’ll see a more principled way of dealing with side effects in the next lecture!

10.10 Quiz

Which of these statements is true?

1. reverse . reverse . reverse === reverse
2. reverse . reverse === reverse
3. reverse . id === id

Which of these is an infinite list that starts with [0,1,2,1,2,1,2...]?

1. cycle [0,1,2]
2. 0:repeat [1,2]
3. 0:cycle [1,2]
4. 0:[1,2..]

What’s the next step when evaluating this expression?

head (map not (True:False:[]))

1. head (False : True : [])
2. head (not True)
3. head (False : map not (False:[]))
4. head (not True : map not (False:[]))

Which of these values is not in weak head normal form?

1. map
2. f 1 : map f (2 : [])
3. Just (not False)
4. (\x -> x) True

Which of these statements about the following function is true?

f 0 x = 1+x
f _ x = 2+x

1. f is strict in its left argument
2. f is strict in its right argument
3. f forces both of its arguments
4. None of the above

Does this function work with infinite lists as input? Why?

f [] = []
f (x:xs) = x : map not xs

1. No, because it includes a [] case, which is never reached.
2. No, because it uses map, which evaluates the whole list.
3. Yes, because it only looks at the first element of the list before producing a WHNF value.
4. Yes, because it calls map, which works with infinite lists.

What about this one?

f xs = map (+(sum xs)) xs

1. No, because it uses map, which evaluates the whole list.
2. No, because computing the head of the result needs the whole input list.
3. Yes, because it doesn’t includes a [] case
4. Yes, because it calls map, which works with infinite lists.

10.11 Exercises

• Set10a
• Set10b

11.1 Contents

• IO

11.2 You’ve Been Fooled!

Forget what we talked about functional programming and purity. Actually, Haskell is the world’s best imperative programming language! Let’s start:

questionnaire = do
  putStrLn "Write something!"
  s <- getLine
  putStrLn ("You wrote: "++s)

Prelude> questionnaire
Write something!
Haskell!
You wrote: Haskell!

Reading input and writing output was easy enough. We can also read stuff over the network. Here’s a complete Haskell program that fetches a some words from a URL using HTTP and prints them.

import Network.HTTP
import Control.Monad

main = do
  rsp <- simpleHTTP (getRequest "http://httpbin.org/base64/aGFza2VsbCBmb3IgZXZlcgo=")
  body <- getResponseBody rsp
  forM_ (words body) $ \w -> do
     putStr "word: "
     putStrLn w

You can find this program in the course repository as exercises/Examples/FetchWords.hs, and you can run it like this:

$ cd exercises/Examples
$ stack runhaskell FetchWords.hs
word: haskell
word: for
word: ever

What’s going on here? Let’s look at the types:

Prelude> :t putStrLn
putStrLn :: String -> IO ()
Prelude> :t getLine
getLine :: IO String

A value of type IO a is an operation that produces a value of type a. So getLine is an IO operation that produces a string. The () type is the so called unit type, its only value is (). It’s mostly used when an IO operation doesn’t return anything (but rather just has side effects).

A comparison with Java (method) types might help:

IO operations can be combined into bigger operations using do-notation.

do operation
   operation arg
   variable <- operationThatReturnsStuff
   let var2 = expression
   operationThatProducesTheResult var2

query :: IO ()
query = do
  putStrLn "Write something!"                    -- run an operation, ignore produced value
  s <- getLine                                   -- run an operation, capture produced value
  let n = length s                               -- run a pure function
  putStrLn ("You wrote "++show n++" characters") -- run an operation, passing on the produced value

Prelude> query
Write something!
lorem ipsum
You wrote 11 characters

askForALine :: IO String
askForALine = do
  putStrLn "Please give me a line"
  getLine

Prelude> askForALine
Please give me a line
this is a line
"this is a line"
Prelude> line <- askForALine
Please give me a line
this is a line
Prelude> :t line
line :: String
Prelude> line
"this is a line"

ask :: String -> IO String
ask question = do
  putStrLn question
  getLine

Prelude> ask "What is love?"
What is love?
Baby don't hurt me!
"Baby don't hurt me!"
Prelude> response <- ask "Who are you?"
Who are you?
The programmer.
Prelude> response
"The programmer."
Prelude> :t response
response :: String
Prelude> :t ask
ask :: String -> IO String
Prelude> :t ask "Who are you?"
ask "Who are you?" :: IO String

11.3 The Subtle return

The Haskell function return is named a bit misleadingly. In other languages return is a built-in keyword, but in Haskell it’s just a function. The return :: a -> IO a function takes a value and turns it into an operation, that produces the value.

produceThree :: IO Int
produceThree = return 3

printThree :: IO ()
printThree = do
  three <- produceThree
  putStrLn (show three)

That doesn’t sound very useful does it? Combined with do-notation it is. Here we return a boolean according to whether the user answered Y or N:

yesNoQuestion :: String -> IO Bool
yesNoQuestion question = do
  putStrLn question
  s <- getLine
  return (s == "Y")

Prelude> yesNoQuestion "Fire the missiles?"
Fire the missiles?
Y
True
Prelude> answer <- yesNoQuestion "Are you sure?"
Are you sure?
N
Prelude> :t answer
answer :: Bool
Prelude> answer
False

Note! This means that return does not stop execution of an operation (unlike return in Java or C). Remember that in do-blocks, the last line decides which value to produce. This means that this operation produces 2:

produceTwo :: IO Int
produceTwo = do return 1
                return 2

Prelude> produceTwo
2

Let’s look at this another way. The do notation allows us to cause a sequence of side-effects, and finally to produce a value.

produceThree = do putStrLn "1"   -- side effect, produces (), which is ignored
                  return    2    -- no side effect, produces 2, which is ignored
                  getLine        -- side effect, produces a String, which is ignored
                  return    3    -- no side effect, produces 3, which is passed on

Prelude> final <- produceThree
1
this line is ignored
Prelude> final
3

Also note that these are the same operation:

do ...
   x <- op
   return x

do ...
   op

Since return is a function, you should remember to parenthesize any complex expressions:

return (f x : xs)
-- alternatively:
return $ f x : xs

11.4 do and Types

Let’s look at the typing of do-notation in more detail. A do-block builds a value of type IO <something>. For example in

foo = do
  ...
  lastOp

The lastOp must be of type IO X (for some X). The type of foo will also be IO X. Let’s look at an example with parameters next:

bar x y = do
  ...
  lastOp arg

The lastOp must be of type Y -> IO X (so that lastOp arg has type IO X). The type of bar will be A -> B -> IO X (and inside bar we’ll have x :: A and y :: B).

If we use return:

quux x = do
  ...
  return value

The function quux will have type A -> IO B, where x :: A and value :: B.

Let’s look at the typing of <- next. If op :: IO X and you have var <- op, var will have type X. We’ve seen this in many GHCi examples.

The last line of a do cannot be foo <- bar. It can’t be let foo = bar either. The last line determines what the whole operation produces, so it must be an operation (for example, return something).

Here’s a worked example:

alwaysFine :: IO Bool
alwaysFine = do
  putStrLn "What?" -- :: IO ()
  return 2         -- :: IO Int, produced value is discarded
  s <- getLine     -- getLine :: IO String, thus s :: String
  putStrLn s       -- putStrLn :: String -> IO (), thus putStrLn s :: IO ()
  let b = True     -- b :: Bool
  return b         -- :: IO Bool
                   -- Thus, alwaysFine :: IO Bool

The typing rules guarantee that you can not “escape” IO. Even though <- gives you an X from an IO X, you can only use <- inside do. However a do always means a value of type IO Y. In other words: you can temporarily open the IO box, but you must return into it. “What happens in IO, stays in IO.”

We’ll talk more about what this means later. For now, it’s enough to know that if you have a function with a non-IO type, like for example myFunction :: Int -> [String] -> String, the function can not have IO happening inside it. It is a pure function.

11.5 Control Structures

For the following examples, we’ll need two new operations.

print :: Show a => a -> IO ()   -- print a value using the show function
readLn :: Read a => IO a        -- get a line and convert it to a value using the read function

The usual tools of recursion, guards and if-then-else also work in the IO world. Here’s an IO operation that’s defined using a guard:

printDescription :: Int -> IO ()
printDescription n
  | even n    = putStrLn "even"
  | n==3      = putStrLn "three"
  | otherwise = print n

Prelude> printDescription 2
even
Prelude> printDescription 3
three
Prelude> printDescription 5
5

Here’s an operation that prints all numbers in a list using recursion and pattern matching:

printList :: [Int] -> IO ()
printList [] = return () -- do nothing
printList (x:xs) = do print x
                      printList xs -- recursion

Prelude> printList [1,2,3]
1
2
3

Here are two slightly more complicated examples of recursive IO operations. They use the value produced by the recursive call. The operation readAndSum n reads n numbers from the user and prints their sum. The operation ask questions shows each string in questions to the user, reads a response, and returns a list of all the responses.

readAndSum :: Int -> IO Int
readAndSum 0 = return 0
readAndSum n = do
  i <- readLn            -- read one number
  s <- readAndSum (n-1)  -- recursion: read and sum rest of numbers
  return (i+s)           -- produce result

Prelude> s <- readAndSum 3
2
4
5
Prelude> s
11

ask :: [String] -> IO [String]
ask [] = return []
ask (question:questions) = do
  putStr question
  putStrLn "?"
  answer <- getLine         -- get one answer
  answers <- ask questions  -- recursion: get rest of answers
  return (answer:answers)   -- produce result

Prelude> replies <- ask ["What is your name","How old are you"]
What is your name?
Yog-Sothoth
How old are you?
The question is meaningless
Prelude> replies
["Yog-Sothoth","The question is meaningless"]

Additionally, we have some IO-specific control structures, or rather, functions. These come from the module Control.Monad.

-- when b op performs op if b is true
when :: Bool -> IO () -> IO ()
-- unless b op performs op if b is false
unless :: Bool -> IO () -> IO ()
-- do something many times, collect results
replicateM :: Int -> IO a -> IO [a]
-- do something many times, throw away the results
replicateM_ :: Int -> IO a -> IO ()
-- do something for every list element
mapM :: (a -> IO b) -> [a] -> IO [b]
-- do something for every list element, throw away the results
mapM_ :: (a -> IO b) -> [a] -> IO ()
-- the same, but arguments flipped
forM  :: [a] -> (a -> IO b) -> IO [b]
forM_ :: [a] -> (a -> IO b) -> IO ()

Using these, we can rewrite our earlier examples:

printList :: [Int] -> IO ()
printList xs = mapM_ print xs

readAndSum n = do
  numbers <- replicateM n readLn
  return (sum numbers)

ask :: [String] -> IO [String]
ask questions = do
  forM questions askOne

askOne :: String -> IO String
askOne question = do
  putStr question
  putStrLn "?"
  getLine

11.6 A Word About do and Indentation

It’s easy to run into weird indentation problems when using do-notation. Here are some rules of thumb to help you get it right.

The most important rule of do and indentation is all operations in a do-block must start in the same column.

Some examples of this rule:

-- This is not OK, putStrLn is way too left
foo = do y <- getLine
   putStrLn y

-- This is not OK either
foo = do y <- getLine
           putStrLn y

-- This is OK
foo = do y <- getLine
         putStrLn y

-- This is also OK: putting a line break after do
foo = do
  y <- getLine
  putStrLn y

A related rule is when an operation goes over multiple lines, indent the follow-up lines. If you don’t indent, it’ll look like a new operation!

-- This is not OK, the string starts a new operation
quux = do putStrLn
          "this long string"
          print 1

-- This is OK
quux = do putStrLn
            "this long string"
          print 1

Here’s one more example, with nested do-blocks, and two different valid indentations.

-- This is OK
foo x = do quux
           y <- blorg
           when y (do thing
                      otherThing)
           return 3

-- This is also OK: starting putting a line break after do, using $
foo x = do
  quux
  y <- blorg
  when y $ do
    thing
    otherThing
  return 3

11.7 Let’s Write a Program

After all these short one-off examples, let’s turn to something a bit longer. Let’s write a program to fetch all type annotations from all .hs files. We use IO operations like readFile and listDirectory to read and find files, but also pure code like map and filter to do the actual processing. First off, here’s a recap of the library operations we’re using:

-- split string into lines
lines :: String -> [String]
-- `isSuffixOf suf list` is true if list ends in suf
Data.List.isSuffixOf :: Eq a => [a] -> [a] -> Bool
-- `isInfixOf inf list` is true if inf occurs inside list
Data.List.isInfixOf :: Eq a => [a] -> [a] -> Bool
-- FilePath is just an alias for String
type FilePath = String
-- get entire contents of file
readFile :: FilePath -> IO String
-- list files in directory
System.Directory.listDirectory :: FilePath -> IO [FilePath]
-- is the given file a directory?
System.Directory.doesDirectoryExist :: FilePath -> IO Bool

And here’s the program itself. You can also find it in the course repository as exercises/Examples/ReadTypes.hs.

module Examples.ReadTypes where

import Control.Monad (forM)
import Data.List (isInfixOf, isSuffixOf)
import System.Directory (listDirectory, doesDirectoryExist)

-- a line is a type signature if it contains :: but does not contain =
isTypeSignature :: String -> Bool
isTypeSignature s = not (isInfixOf "=" s) && isInfixOf "::" s

-- return list of types for a .hs file
readTypesFile :: FilePath -> IO [String]
readTypesFile file
  | isSuffixOf ".hs" file = do content <- readFile file
                               let ls = lines content
                               return (filter isTypeSignature ls)
  | otherwise             = return []

-- list children of directory, prepend directory name
qualifiedChildren :: String -> IO [String]
qualifiedChildren path = do childs <- listDirectory path
                            return (map (\name -> path++"/"++name) childs)

-- get type signatures for all entries in given directory
-- note mutual recursion with readTypes
readTypesDir :: String -> IO [String]
readTypesDir path = do childs <- qualifiedChildren path
                       typess <- forM childs readTypes
                       return (concat typess)

-- recursively read types contained in a file or directory
-- note mutual recursion with readTypesDir
readTypes :: String -> IO [String]
readTypes path = do isDir <- doesDirectoryExist path
                    if isDir then readTypesDir path else readTypesFile path

-- main is the IO action that gets run when you run the program
main :: IO ()
main = do ts <- readTypes "."
          mapM_ putStrLn ts

We can run this program by going to the directory exercises/Examples and running:

$ stack runhaskell ReadTypes.hs
deposit :: String -> Int -> Bank -> Bank
withdraw :: String -> Int -> Bank -> (Int,Bank)
runBankOp :: BankOp a -> Bank -> (a,Bank)
... and so on

The exact output will vary according to the contents of the directory, of course.

11.8 What Does It All Mean?

Let’s return to the functional world. How can we reconcile IO operations with Haskell being a pure and lazy language? Something like putStrLn :: String -> IO () is a pure function that returns an operation. How is it pure? putStrLn x is the same when x is the same. In other words: an operation is a pure description of a chain of side effects. Only executing the operation causes those side effects. When a Haskell program is run, only one operation is executed - it’s called main :: IO (). Other operations can be run only by linking them up to main.

When in GHCi, if an expression you type in evaluates to an operation, GHCi runs that operation for you. Here’s a demonstration of the purity of print:

Prelude> x = print 1   -- creates operation, doesn't run it
Prelude> x             -- runs the operation
1
Prelude> x             -- runs it again!
1

Operations are values just like numbers, lists and functions. We can write code that operates on operations. This function takes two operations, a and b, and returns an operation that asks the user which one he’d like to run.

choice :: IO x -> IO x -> IO x
choice a b =
  do putStr "a or b? "
     x <- getLine
     case x of "a" -> a
               "b" -> b
               _ -> do putStrLn "Wrong!"
                       choice a b

Prelude> choice (putStrLn "A!!!!") (putStrLn "B!!!!")
a or b? z
Wrong!
a or b? a
A!!!!

Using operations specified as parameters lets us write functions like mapM_, which we met earlier. The implementation is a recursive IO operation that takes another IO operation as a parameter. Conceptually complicated, but simple when you read the code:

mapM_ :: (a -> IO b) -> [a] -> IO ()
mapM_ op     [] = return ()       -- do nothing for an empty list
mapM_ op (x:xs) = do op x         -- run operation on first element
                     mapM_ op xs  -- run operation on rest of list, recursively

Prelude> mapM_ print [1,2,3]
1
2
3

11.9 One More Thing: IORef

So far the only side-effects we’ve been able to produce in IO have been terminal (getLine, print) and file (readFile, listDirectory) IO. Imperative programs written in Java, Python or C have other types of side effects too that we can’t express in pure Haskell. One of these is mutable (i.e. changeable) state. A pure function can not read mutable state, because otherwise two invocations of the same function might not return the same value.

The Haskell type IORef a from the module Data.IORef is a mutable reference to a value of type a

newIORef :: a -> IO (IORef a)                -- create a new IORef containing a value
readIORef :: IORef a -> IO a                 -- produce value contained in IORef
writeIORef :: IORef a -> a -> IO ()          -- set value in IORef
modifyIORef :: IORef a -> (a -> a) -> IO ()  -- modify value contained in IORef with a pure function

Here are some examples of using an IORef in GHCi:

Prelude> :m +Data.IORef
Prelude Data.IORef> myRef <- newIORef "banana"
Prelude Data.IORef> readIORef myRef
"banana"
Prelude Data.IORef> writeIORef myRef "apple"
Prelude Data.IORef> readIORef myRef
"apple"
Prelude Data.IORef> modifyIORef myRef reverse
Prelude Data.IORef> readIORef myRef
"elppa"