Introduction to Functional Programming – Frequently Asked Questions | TDA555 / DIT440, LP1 2018 |

Home | Schedule | Labs | Lectures | Exercises | Exam | About | FAQ | Fire | WaitList | Slack | TimeEdit | YouTube | Links |

Introduction to Functional Programming – Frequently Asked Questions | TDA555 / DIT440, LP1 2018 |

Home | Schedule | Labs | Lectures | Exercises | Exam | About | FAQ | Fire | WaitList | Slack | TimeEdit | YouTube | Links |

This page answers some frequently asked questions regarding Haskell.

- How do Haskell’s built-in lists work?
- What is
*pattern matching*? - What does a dollar sign
`($)`

mean in an expression? - What does
`let`

and`where`

do, and how are they different? - How do infix operators work?
- How do I debug Haskell programs?
- How can I make QuickCheck run more than 100 tests?
- What editor should I use for Haskell code?
- How can I compile Haskell code?
- What does it mean when type errors talk about
`Foldable`

or`Traversable`

?

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
| Add Card Hand
```

```
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
initHand (Add c h) = Add c (initHand h)
-- 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.

(For more information, see the Wikibooks entry on 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:

- Look at a value to distinguish between different cases (e.g. whether a list is empty or non-empty)
- 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.

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
```

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 :: (Int,Int) -> Int
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
```

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

```
has10_bad :: Hand -> Bool
has10_bad Empty = False
has10_bad (Add c rest) = size (Add c rest) == 10
```

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
```

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

```
color_bad :: Suit -> String
color_bad s
| 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”.

`($)`

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.

For more information, see this section in LYAH.

`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)
```

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
```

TODO Write about fixity declarations.

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:

```
hand1 = Add card1 (Add card2 Empty)
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.

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.

- 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.
- 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.
- 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:

```
*HaskellFAQ> mySum [1..5]
5
4
3
2
1
0
15
```

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

There are also more advanced methods for debugging Haskell; see

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.

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

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.

`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]
```