Introduction to Functional Programming – Frequently Asked Questions TDA555 / DIT440, LP1 2016 Home | Schedule | Labs | Lectures | Exercises | Exam | About | FAQ Fire | Forum | TimeEdit | YouTube | Links
 Introduction to Functional Programming – Frequently Asked Questions TDA555 / DIT440, LP1 2016 Home | Schedule | Labs | Lectures | Exercises | Exam | About | FAQ Fire | Forum | TimeEdit | YouTube | Links

### How do Haskell’s built-in lists work?

In this course, we’re trying to explain Haskell’s built-in lists in terms of user-defined data types, in order to show that they are just like ordinary data types but with special syntactic support. So let’s look at user-defined lists first.

In the lectures, we define two different list-like types:

data Hand
= Empty
data List a
= Nil
| Cons a (List a)

(In the lecture, the List type uses the constructors Add and Empty just like Hand, but here we’re using different names for clarity.)

Those two types have the exact same structure: Empty/Nil is used to construct an empty hand/list and Add/Cons is used to add an element to a smaller hand/list. The only difference is that the Hand type hard-codes the elements to have type Card (i.e. Hand is a list of cards) while List a can have elements of any type a.

Since the two types have the same structure, functions on them will look very similar; e.g:

-- throw away the last card in a hand
initHand :: Hand -> Hand
initHand (Add c Empty) = Empty

-- throw away the last element in a list
initList :: List a -> List a
initList (Cons a Nil) = Nil
initList (Cons a as)  = Cons a (initList as)

By just renaming Cons to Add and Nil to Empty, we see that the two definitions are really the same.

Haskell’s ordinary lists (of type [a]) are not defined by a data declaration (which is why we call them built-in). However, it is important to know that they still work just like ordinary data types. The constructors of the [a] type are

[]  :: [a]              -- Empty list
(:) :: a -> [a] -> [a]  -- Add element to a smaller list

Compare these to the constructors of the above List type:

Nil  :: List a
Cons :: a -> List a -> List a

We see that by just changing List a to [a] they get the same types.

This shows that [a] in fact has the same structure as List and Hand. So we should be able to give a very similar definition of the above init function for built-in lists:

initList' :: [a] -> [a]
initList' ((:) a []) = []
initList' ((:) a as) = (:) a (initList' as)

By just renaming (:) to Cons and [] to Nil, we see that initList' is identical to initList.

Now comes the special part: since (:) is a symbolic (i.e. non-alpha-numeric) constructor, it can be written between its arguments (read about that here). So it is more common to write the init function for built-in lists as follows:

initList'' :: [a] -> [a]
initList'' (a:[]) = []
initList'' (a:as) = a : initList' as

Now the similarity to initList and initHand is a bit more obscure. However, the structure of the definition is still the same, only written in slightly different style.

### What is pattern matching?

Before reading these notes, make sure that you have understood these slides that explain data type definitions and constructors.

Pattern matching is used to deconstruct values in functions (and other places). Deconstruct means two things:

1. Look at a value to distinguish between different cases (e.g. whether a list is empty or non-empty)
2. Take a value apart and give names to the components (e.g. call the first element of a non-empty list a and the rest as)

Remember the following data types from the lectures:

data Suit = Spades | Hearts | Diamonds | Clubs           deriving (Eq,Show)
data Rank = Numeric Integer | Jack | Queen | King | Ace  deriving (Eq,Show)
data Card = Card Rank Suit                               deriving (Eq,Show)
data Hand = Empty | Add Card Hand                        deriving (Eq,Show)

Here are some function definitions that use pattern matching on the above data types:

isHearts :: Suit -> Bool
isHearts Hearts = True
isHearts s      = False

isHeartsCard :: Card -> Bool
isHeartsCard (Card r s) = isHearts s

size :: Hand -> Integer
size Empty     = 0
size (Add c h) = 1 + size h

topIsJackOfHearts :: Hand -> Bool
topIsJackOfHearts (Add (Card Jack s) rest) = isHearts s
topIsJackOfHearts h                        = False

In isHearts, we use pattern matching to distinguish between whether the argument is Hearts or something else.

In isHeartsCard, we use pattern matching in a different way: to take a card apart and give names to its two components (here the rank is called r and the suit s). Since we now have a name for the suit, we can use it on the right-hand side of the equation. Here we pass s on to the isHearts function.

In size, we use pattern matching in two ways: (1) to distinguish between empty and non-empty lists, and (2) to take a non-empty list apart and give names to its components (here c is the first card and h is the rest).

Finally, topIsJackOfSpades shows that patterns can be arbitrarily deep. Instead of using the pattern Add c h, we use a deeper pattern Add (Card Jack s) h. This pattern matches any hand whose top card is a Jack. The pattern also introduces the two variables s (the suit of the first card) and h (the rest of the hand) which we can use on the right-hand side of the equation.

#### Wildcards

In the definitions above, there are some cases where we give a name to a value but never use it in the result; for example, the card c in size. In such cases, it is often preferred to replace the variable with a wildcard written as an underscore _. A wildcard matches any value. Using a wildcard, we could rewrite size as follows:

size' :: Hand -> Integer
size' Empty     = 0
size' (Add _ h) = 1 + size' h

#### Built-in types

Some types that are “built-in” to Haskell have special syntactic support. Here are some examples of such values:

10          :: Int
10          :: Double
()          :: ()           -- The "unit" type
(True, 10)  :: (Bool, Int)  -- A pair
'e'         :: Char

For these types, pattern matching uses the same syntax as for construction; for example:

isNumber10 :: Int -> Bool
isNumber10 10 = True
isNumber10 _  = False

addPair (a,b) = a + b

isX :: Char -> Bool
isX 'X' = True
isX _   = False

Built-in lists are a bit special because there are different ways to construct the same list (see the entry about built-in lists and about infix data constructors):

[1,2,3]                   :: [Int]
1 : 2 : 3 : []            :: [Int]   -- Use : as an infix operator
(:) 1 ((:) 2 ((:) 3 []))  :: [Int]   -- Use : as a prefix operator

['C','a','t']             :: String  -- String = [Char]
"Cat"                     :: String
'C' : 'a' : 't' : []      :: String

However, one only has to remember that all of these forms can be used in patterns as well. For example, these three functions are equivalent:

isCat1 :: String -> Bool
isCat1 ['C','a','t']          = True
isCat1 _                      = False

isCat2 :: String -> Bool
isCat2 "Cat"                  = True
isCat2 _                      = False

isCat3 :: String -> Bool
isCat3 ('C' : 'a' : 't' : []) = True
isCat3 _                      = False

Note however, that in the first two versions, the empty list [] is hidden in the pattern, so it is not possible to give a deeper pattern for the rest of the list. This means that if one e.g. wants to match on a string that starts with “Cat” and can have any length, one has to use the third form:

startsWithCat :: String -> Bool
startsWithCat ('C' : 'a' : 't' : _) = True
startsWithCat s                     = False

#### Caveat 1: It is not always a good idea to use pattern matching!

For example, a function that checks whether a hand has 10 cards could be defined as follows:

In the last equation, we use pattern matching to take the hand apart, but then, on the right-hand side, we immediately reconstruct the same hand. In that case, it is better to just replace Add c rest by a variable h on both sides. This has the advantage that the first equation (the Empty case) is not needed, since it is covered by the general equation:

has10 :: Hand -> Bool
has10 h = size h == 10

#### Caveat 2: Guards are not the same as pattern matching!

For example, one could write a function that returns the color of a card as follows:

| s == Hearts   = "Red"
| s == Diamonds = "Red"
| otherwise     = "Black"

However, it is usually considered bad style to use the == operator to distinguish between cases like this. The main problem is that == can not replace pattern matching in general. We said that pattern matching has two purposes: (1) to distinguish between cases, and (2) to take values apart. But the == operator can only be used for the first purpose.

As a concrete example, it is not possible to define topIsJackOfHearts using == and guards:

topIsJackOfHearts_wrong :: Hand -> Bool
topIsJackOfHearts_wrong h
| h == Add (Card Jack s) rest = isHearts s
| otherwise                   = False

Guards can not be used to introduce new variables, so this definition is rejected by GHC because there are no variables called s and rest available. In other words, we can only use == to check if a hand is equal to another specific hand, but we cannot use it check if a hand has a certain “form”.

### What does a dollar sign ($) mean in an expression?$ can be used to avoid parentheses in deeply nested expressions. As an example, say we want to take the 10 last characters in a sentence, excluding the final dot:

ex1 :: String -> String
ex1 s = reverse (take 10 (drop 1 (reverse s)))

The nested parentheses make this expression a bit hard to read. A more readable variant can be obtained using $: ex1' :: String -> String ex1' s = reverse$ take 10 $drop 1$ reverse s

Informally, we can think of each $as meaning “a parenthesis from here to the end of the expression”. In fact, there is nothing special about$ – it is just a simple binary operator defined as follows:

($) :: (a -> b) -> a -> b f$ a = f a

Its first argument is a function from a to b. Its second argument is a value of type a and the result is a value of type b, obtained by passing the a-value to the function.

Note though that (\$) does not always mix well with other infix operators. If there are problems, try inserting parentheses.

### What does let and where do, and how are they different?

The keywords let and where are used to declare local definitions to use in expressions.

As an example, the following function computes the distance between two points in the plane:

dist :: (Float,Float) -> (Float,Float) -> Float
dist (x1,y1) (x2,y2) = sqrt ((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))

Note how the sub-expressions x1-x2 and y1-y2 both appear twice. (We avoid using the built-in power function (^) in order to make a point.)

To reduce the duplication and make the definition more readable, we just introduce two local declarations:

dist_where :: (Float,Float) -> (Float,Float) -> Float
dist_where (x1,y1) (x2,y2) = sqrt (dx*dx + dy*dy)
where
dx = x1-x2
dy = y1-y2

Note that everything local to the definition has to be indented.

The declarations dx and dy are visible in the whole definition of dist_where, but not outside.

An alternative to where is to use let instead. Those two constructs have a similar role, but they are used at different places. As we have seen, where is used to introduce local definitions in a function declaration. On the other hand, let introduces local definitions in an expression.

The syntax of let is

let v = sharedExpression in anotherExpression

This introduces the local definition v = sharedExpression to be used in anotherExpression. Here is how to rewrite dist to use let:

dist_let :: (Float,Float) -> (Float,Float) -> Float
dist_let (x1,y1) (x2,y2) =
let dx = x1-x2 in
let dy = y1-y2 in
sqrt (dx*dx + dy*dy)

Note how let appears inside the expression that gives the result of dist. In dist_where, on the other hand, the local definitions are outside of the expression.

Nested let expressions, as we have above, can be merged into a single one as follows:

dist_let' :: (Float,Float) -> (Float,Float) -> Float
dist_let' (x1,y1) (x2,y2) =
let dx = x1-x2
dy = y1-y2
in  sqrt (dx*dx + dy*dy)

### How do infix operators work?

Any function of at least two arguments can be written infix, i.e. between its arguments, by using back-ticks:

*Main> 3 max 4
4

*Main> 10 mod 3
1

This notation can also be used when defining functions:

dist2 :: (Float,Float) -> (Float,Float) -> Float
(x1,y1) dist2 (x2,y2) = sqrt (dx*dx + dy*dy)
where
dx = x1-x2
dy = y1-y2

Operators, such as +, *, &&, are normal functions (of two arguments). They are written infix by default:

*Main> 1+2
3

*Main> True && False
False

This is also the case for user-defined operators (as long as the name is non-alphanumeric); e.g.

-- Almost equal
(=~) :: Int -> Int -> Bool
a =~ b = abs (a-b) < 2

It is however possible to use operators in prefix style (operator before its arguments) by surrounding it with parentheses:

-- Almost equal
(=~) :: Int -> Int -> Bool
(=~) a b = abs (a-b) < 2

Testing:

*Main> 4 =~ 5
True

*Main> 4 =~ 7
False

*Main> (=~) 4 7
False

#### Infix data constructors

Data constructors are syntactically treated as normal values in Haskell. This means that alpha-numeric constructors are prefix by default and symbolic constructors are infix by default, just like for ordinary functions.

In standard Haskell, one has to use alpha-numeric constructor names when defining new data types. We give many such examples in the course; e.g.

data Hand = Empty | Add Card Hand

The constructor Add is a normal function, and as such, it can be used both prefix and infix. So these two definitions are equivalent:

hand2 = card1 Add (card2 Add Empty)

In standard Haskell there is only a single (I think…) symbolic data constructor: the constructor for non-empty built-in lists (see this entry):

(:) :: a -> [a] -> [a]

This constructor is of course special, since it’s the only example of an infix data constructor. However, there is nothing special about how it is used. Just like for other symbolic function names, it is infix by default, and it can be turned prefix by surrounding it in parentheses. So these three lists are equivalent:

list1 = (:) 1 ((:) 2 ((:) 3 []))

list2 = 1 : (2 : (3 : []))

list3 = 1 : 2 : 3 : []

In list3 we made use of the fact that (:) happens to be right-associative, which makes the parentheses redundant.

Finally, note that we use the same syntax for this infix operator both in patterns and expressions. For example, the following function flips the first two elements of a list:

flipFirstTwo :: [a] -> [a]
flipFirstTwo (a:b:cs) = b:a:cs

On the left-hand side, : is used to split the list in its first and second elements (a and b) and the rest (cs), and on the right-hand side it constructs the result list with a and b flipped.

### How do I debug Haskell programs?

Sometimes there is something wrong with a program, but even after staring at it for a long time, you have no idea what the problem is. Here is a simple guide for what to do in those cases.

1. Make sure that you have divided your program into simple functions, each focusing on a single sub-task. This makes it easier to understand the code and test each function in isolation. Also, if you provide type signatures for the sub-functions, the type checker will help you catch many errors.
2. Use QuickCheck to test each sub-function, as well as combinations of sub-functions. It is of course also good to QuickCheck the whole program, but if that test fails it can be hard to know where the problem comes from. Checking each sub-function will often very quickly point you to the problematic code.
3. If you find it hard to understand what your code does – e.g. you have a recursion that never reaches the base case – it can be convenient to use trace to follow the execution.

trace takes a message String and a value of type a and returns that value:

trace :: String -> a -> a

Say you have a big expression ... e ... that contains the sub-expression e. To trace the evaluation of e, you just apply trace to it: ... (trace "evaluates e" e) .... This means that whenever sub-expression e is needed, the message “evaluates e” will be printed on the terminal. Note that you need to import the module Debug.Trace to use trace.

Function calls can be traced by adding an extra equation with a false guard:

myFunc :: [Int] -> Int
myFunc as | trace "someone called myFunc" False = undefined
muFunc ...  -- Rest of definition

For example, to trace the execution of the sum function, we write as follows:

mySum :: [Int] -> Int
mySum as | trace (show (length as)) False = undefined
mySum []     = 0
mySum (a:as) = a + mySum as

Here is the tracing in action:

5
4
3
2
1
0
15

This shows how the length decreases from 5 to 0 before the sum of 15 is returned.

### How can I make QuickCheck run more than 100 tests?

Short answer – use quickCheckWith in the following way:

quickCheckWith stdArgs {maxSuccess = 1000} prop_myFunction

Note:

• stdArgs is a QuickCheck data structure that contains configuration parameters.
• quickCheckWith stdArgs is the same as the ordinary quickCheck.
• The syntax stdArgs {maxSuccess = 1000} is used to override the maxSuccess parameter in stdArgs with the value 1000, telling QuickCheck to test each property 1000 times.

### What editor should I use for Haskell code?

The links page suggests a number of editors and IDEs for Haskell.

### How can I compile Haskell code?

Sometimes one wants to make a executable program file from Haskell code. The reason might be to get something that can run without requring GHCi, or to make the code run faster. (Compiled code can be a lot faster than running in GHCi.)

Use the following command (in a terminal, not in GHCi) to compile Haskell code:

ghc --make MyFile.hs -o NameOfExecutable

(The --make flag is needed when your program consists of different modules in different files.)

This produces the executable file NameOfExecutable which you can run as follows (on a Linux system):

./NameOfExecutable

You should also be able to run the file by opening a file browser and double-click on the file.

### What does it mean when type errors talk about Foldable or Traversable?

From version 7.10 of GHC, several functions in the Prelude were generalized from working on lists to working on arbitrary “foldable” or “traversable” data structures.

Maybe you have seen type errors that say something like “Could not deduce (Foldable t0) …”. This means that you have a type error in your program, but the message is not very informative.

Here is a concrete (but strange) example where such an error occurs:

*Main> let getInt = do c <- getChar; return (read [c])
*Main> sum getInt
<interactive>:18:1:
Could not deduce (Foldable IO) arising from a use of ‘sum’
...

To understand where the error message comes from, let’s have a look at the type of sum:

sum :: (Num a, Foldable t) => t a -> a

This type says that the argument of sum is a value of type t a where t is in the Foldable class. Intuitively, this means that t is a data structure whose elements can be combined with each other (e.g. using the + operator, as in the sum case).

For the purpose of this course, it is sufficient to think of t a as meaning [a]. So the type of sum that we are interested in is simply:

sum :: Num a => [a] -> a

Other examples of such functions are:

and     :: Foldable t => t Bool -> Bool
maximum :: (Ord a, Foldable t) => t a -> a
foldr   :: Foldable t => (a -> b -> b) -> b -> t a -> b

The types that we are interested in for those functions are:

and     :: [Bool] -> Bool
maximum :: Ord a => [a] -> a
foldr   :: (a -> b -> b) -> b -> [a] -> b

Another similar class is Traversable. It shows up in the type of these functions (among others):

sequence :: (Monad m, Traversable t) => t (m a) -> m (t a)
mapM     :: (Monad m, Traversable t) => (a -> m b) -> t a -> m (t b)

Again, in this course we simply think of Traversable as meaning lists, so the interesting types for sequence and mapM are:

sequence :: Monad m => [m a] -> m [a]
mapM     :: Monad m => (a -> m b) -> [a] -> m [b]