Introduction to Functional Programming – Frequently Asked Questions | TDA555 / DIT440, LP1 2014 |
Home | Schedule | Labs | Exercises | Exam | About | FAQ | Fire | Forum | TimeEdit | Links |
Introduction to Functional Programming – Frequently Asked Questions | TDA555 / DIT440, LP1 2014 |
Home | Schedule | Labs | Exercises | Exam | About | FAQ | Fire | Forum | TimeEdit | Links |
This page answers some frequently asked questions regarding Haskell.
($)
mean in an expression?let
and where
do, and how are they different?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:
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.
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
.stdArgs {maxSuccess = 1000}
is used to override the maxSuccess
parameter in stdArgs
with the value 1000, telling QuickCheck to test each property 1000 times.