Yosuf

Notes on Haskell

Yosuf Ali -

These are notes from my lectures at university augmented with some online and textbook reading. They’re unfinished but they’ve been sitting in my drafts so I thought I’d publish them in case others find them useful.

Surely there must be a less primitive way of making big changes in the store than by pushing vast numbers of words back and forth through the von Neumann bottleneck. Not only is this tube a literal bottleneck for the data traffic of a problem, but, more importantly, it is an intellectual bottleneck that has kept us tied to word-at-a-time thinking instead of encouraging us to think in terms of the larger conceptual units of the task at hand. Thus programming is basically planning and detailing the enormous traffic of words through the von Neumann bottleneck, and much of that traffic concerns not significant data itself, but where to find it. — John Backus

Contents

  • Thinking functionally
  • GHCi
  • Basics
  • Lists
  • Expressions and Types
  • Functions
  • Constrained Polymorphism
  • Language Details

Thinking Functionally

Procedural programming closely mirrors the underlying architecture and focuses on how something is done. Declarative programming (including functional) focuses on what the answer is and provides powerful abstraction (generalisation) mechanisms, as well as being concise and expressive.

Functional programming is programming with functions (lol). The most basic component is a function. They determine a unique output for each combination of inputs.

Instead of asking “How do I change the value of a variable?” or “How do I write a loop?”, ask “What value do I want to produce?”, “How can I make it from the input?” “What are the intermediate values?”.

Expressions are just their values and should be interchangeable.

GHCi

GHC is the compiler for Haskell. GHCi is the interactive environment in which Haskell expressions can be interactively evaluated and programs can be interpreted. It’s what you use on the command line to write Haskell. If you want to follow along, you can either download GHCi or use repl.it for a browser-based environment.

Prelude is just what you get for the command prompt when inside GHCi:

Prelude>

GHCi Commands

:load filename … (or :l as a shortcut) — loads modules from specified 
files:reload (or :r) - repeats the last load command
:type exp (or :t) - prints the type of the expression
:quit (or :q) - exits the interpreter

Basics

Examples of basic math operations as well as using built-in functions:

Prelude> 2+3
5

Prelude> 2+3*5
17

Prelude> (2+3)*5
25

Prelude> 2^3
8

Prelude> sqrt 2
1.4142135623730951

Prelude> sqrt 2 + 3
4.414213562373095

Prelude> sqrt (sqrt 2)
1.189207115002721

Prelude> max 4 8
8

Prelude> div 13 5
2

Prelude> mod 13 5
3

Prelude> 13 `div` 5
2

Prelude> 13 `mod` 5
3

The last two are examples of infix functions (take note of the weird quotes).

Lists

Prelude> [1, 1+3, 1+3+5]
[1,4,9]

The value of [a..b] is a list of integers starting at a and ending at b.

Prelude> [1..6]
[1,2,3,4,5,6]

Prelude> [2..2]
[2]

Prelude> [6..1]
[]

Prelude> [6,5..1]
[6,5,4,3,2,1]

Prelude> 1:2:[]
[1,2]

Some list related functions:

Prelude> product [3,4,5]
60

Prelude> product [1..7]
5040

Prelude> product []
1

Prelude> length [1,3,5]
3

Prelude> reverse [1,3,5]
[5,3,1]

If you’re wondering why product [] = 1, its because of the identity in the category of multiplication. A practical explanation:

product [1,2,3]
	== product [1] * product 2:3:[]
	== product [1] * product [2] * product 3:[]
	== product [1] * product [2] * product [3] * product []

which allows us to implement it with simple recursion:

product [] = 1
product (x:xs) = x * product xs

In Haskell, strings are just lists of characters:

Prelude> ['H', 'e', 'l', 'l', 'o']
"Hello"

Prelude> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"

Prelude> length "Hello"
5

Prelude> reverse "Hello"
"olleH"

[char] is synonymous with String.

Expressions and Types

Basic Types in Haskell

Types

Every expression in Haskell has a type.

Unlike some languages like Java and Pascal, Haskell has type inference. If we write a number we don’t have to tell Haskell it’s a number. It can infer that on its own, so we don’t have to explicitly write out the types of our functions and expressions to get things done.

Types are sets of values, and Typeclasses are sets of Types.

For example, the type Integer includes values like 3 and 8, and the Typeclass Num includes the Types Integer and Double.

This is somewhat analogous to Java, where Classes are sets of Objects, and Interfaces are sets of Classes:

Checking the type of 3 gives us a weird answer:

Prelude> :t 3
3 :: Num a => a

Here, a is called a type variable. Everything before the => is called the class constraint. The above says “there is some type a in the typeclass Num, 3 is of type a.” The value of 3 belongs to every type in the Num typeclass, including Integer and Double. Haskell is just being lazy and not committing to a specific type.

Functions also have types:

Prelude> :t head
head :: [a] -> a

This says for any type a, the function head takes a list of as and returns an a. (head returns the first element of a list).

We can even ask for the type of a plus operator. We surround it with parentheses since its an infix operator (meaning we usually use it between values: 2 + 2, otherwise GHCi will get confused and think we’re actually using it ):

Prelude> :t (+)
(+) :: Num a => a -> a -> a

This says: “There is some type a in the typeclass Num, “+” takes two as and returns another a.

How about the function zip:

Prelude> :t zip
zip :: [a] -> [b] -> [(a, b)]

Zip takes a list of as and a list of bs and it returns a list of (a,b) pairs.

We’re allowed to specify the type of a function along with its definition, which is generally considered good practice:

add :: Integer -> Integer -> Integer
add x y = x + y

On the first line, we explicitly tell Haskell that the add function we’re about to define takes two Integers and returns an Integer. Then we define the function on the second line.

Being explicit about types provides some documentation for us and anyone who reads our code, but it also helps us find bugs. For example, say we have the following function:

dividesEvenly x y = (y / x) * x == y

This function is meant to tell us if x evenly divides into y. So if x=2, and y=5, we would expect (5/2) to be 2, since 2 goes into 5 twice, then 2*2 would give us 4. 4==5 is not true so we would expect this function to return False given 2 5 as arguments. However, it returns True.

Prelude> dividesEvenly 2 5
True

This is because, in Haskell, 5/2 is not 2, but 2.5. One way to address this is to specify that we expect x and y to be Ints:

Prelude> dividesEvenly :: Int -> Int -> Bool
Prelude> dividesEvenly x y = (y / x) * x == y

However, this gives us an error:

<interactive>:3:1: error:    
	• No instance for (Fractional Int)
	    	arising from a use of ‘dividesEvenly’

It is telling us that Int is not a member of the typeclass Fractional. The / operator only works on Fractionals. Turns out the operator we want is `div`:

Prelude> dividesEvenly :: Int -> Int -> Bool
Prelude> dividesEvenly x y = (y `div` x) * x == y
Prelude> divideEvenly 2 5 False

By specifying the type of our function, we were able to find a bug that we may have otherwise missed.

Functions

Infix Operators

Haskell permits the usual infix notation:

Prelude> 1 + 2*3
11

The infix operators + and * refer to functions that take two arguments. Operators also have precedence and associations. To refer to these kinds of functions by themselves, we wrap them in parentheses, writing (+) and (*). So we can use them like this:

Prelude> (*) 2 5
10
Prelude> (+) 1 ((*) 2 5)
11

If we have ordinary identifiers that refer to binary functions:

div :: Int -> Int -> Int
mod :: Int -> Int -> Int

we can use them as infix functions by wrapping them in backquotes:

Prelude> (1987 `div` 100) `mod` 4

which is the same as:

Prelude> mod (div 1987 100) 4

Functions on Int

(+) :: Int -> Int -> Int
(-) :: Int -> Int -> Int
(*) :: Int -> Int -> Int
(^) :: Int -> Int -> Int
div :: Int -> Int -> Int
mod :: Int -> Int -> Int
abs :: Int -> Int
negate :: Int -> Int

Examples:

Prelude> abs 3
3

Prelude> negate 3
-3

Prelude> abs (negate 3)
3

Prelude> negate (negate 3)
3

Prelude> abs 0
0

Prelude> negate 0
0

Relational Operators

(<) :: Int -> Int -> Bool
(<=) :: Int -> Int -> Bool
(>) :: Int -> Int -> Bool
(>=) :: Int -> Int -> Bool
(==) :: Int -> Int -> Bool
(/=) :: Int -> Int -> Bool

Examples:

Prelude> 2 < 3
True

Prelude> 2 < 3
True

Prelude> 2 < 2
False
Prelude> 2 /= 2
False

Prelude> 2 /= 3
True

Overloading

The (==) function has several types:

(==) :: Int -> Int -> Bool
(==) :: Bool -> Bool -> Bool
(==) :: Char -> Char -> Bool
(==) :: Float -> Float -> Bool
(==) :: Eq a => a -> a -> Bool
(<=) :: Ord a => a -> a -> Bool

Building Boolean expressions

(&&) :: Bool -> Bool -> Bool
(||) :: Bool -> Bool -> Bool
not :: Bool -> Bool

Examples:

Prelude> not True
False

Prelude> False || True
True

Prelude> 1 < 2 || 1 > 2
True

A function using relational operators:

small :: Int -> Bool
small n = 0 <= n && n < 10

Functions between types

Haskell has no implicit conversion between types. You must use explicit functions:

To use the ord and chr functions, you must import the Data.Char library module:

Prelude> floor 3.7
3

Prelude> ceiling 3.7
4

Prelude> :m + Data.Char

Prelude> ord 'a'
97

Prelude> chr 98
'b'

Functions of Char

isDigit :: Char -> Bool
isDigit c = ’0’ <= c && c <= ’9’
isUpper, isLower :: Char -> Bool
isUpper c = ’A’ <= c && c <= ’Z’
isLower c = ’a’ <= c && c <= ’z’
isAlpha :: Char -> Bool
isAlpha c = isUpper c || isLower c
ord :: Char -> Int
chr :: Int -> Char

Examples:

Prelude> :m + Data.Char

Prelude> isDigit '2'
True

Prelude> isLower 'B'
False

Prelude> ord '1'
49

Prelude> chr 65
'A'

Prelude> chr 48
'0'

Prelude> chr 32
' '

Prelude> chr (ord 'b')
'b'

Prelude> chr (ord 'b' + 3)
'e'

Functions on Float

(+) :: Float -> Float -> Float
(-) :: Float -> Float -> Float
(*) :: Float -> Float -> Float
(/) :: Float -> Float -> Float
(^) :: Float -> Int -> Float
abs :: Float -> Float
negate :: Float -> Float
sin :: Float -> Float
asin :: Float -> Float
exp :: Float -> Float
log :: Float -> Float
sqrt :: Float -> Float

Guarded Definitions

maxTwo :: Int -> Int -> Int
maxTwo x y
	| x >= y = x
	| otherwise = y

The Boolean expression x >= y is called a guard. Guards are tested in order, so if we had:

maxThree :: Int -> Int -> Int -> Int
maxThree x y z
	| x >= y && x >= z = x
	| y >= x && y >= z = y
	| otherwise = z

it could be simplified to:

maxThree :: Int -> Int -> Int -> Int
maxThree x y z
	| x >= y && x >= z = x
	| y >= z = y
	| otherwise = z

Conditional Expressions

Haskell also has an expression form: if boolexp then exp1 esle exp2 .

So instead of:

maxTwo :: Int -> Int -> Int
maxTwo x y
	| x >= y = x
	| otherwise = y

we could write:

max :: Int -> Int -> Int
max x y = if x >= y then x else y

You can also define functions using existing functions. So you could turn this:

maxThree :: Int -> Int -> Int -> Int
maxThree x y z
	| x >= y && x >= z = x
	| y >= z = y
	| otherwise = z

into this:

maxThree x y z = maxTwo x (maxTwo y z)

Local Definitions

You can have local definitions which are further indented and must line up:

sumSquares :: Int -> Int -> Int
sumSquares n m
	= sqN + sqM
		where
		sqN = n*n
		sqM = m*m

You can use local definitions in all guards, as well as the right-hand expressions:

maxsq :: Int -> Int -> Int
maxsq x y
	| sqx > sqy = sqx
	| otherwise = sqy
	where
	sqx = sq x
	sqy = sq y
    
	sq :: Int -> Int
	sq z = z*z

Constrained polymorphism

For example, the “element” function takes two arguments and asks “does the first argument occur in the second argument (which is a structure of some kind)? And it works for multiple types:

Prelude> elem ‘e’ “Hello”
True

Prelude> elem 3 [1..5]
True

This function is almost polymorphic: the types of things being compared must support equality testing, which is reflected in the constrained type of elem:

Prelude> :t elem
elem :: (Eq a, Foldable t) => a -> t a -> Bool

Here, Eq a is a constraint on the type of a. The type a must belong to the typeclass Eq: those that support equality testing such as Char, Int and Integer.

Language Details

Indentation

In files, Haskell uses indentation to decide where another definition starts, so all definitions must have the same indentation. The following would be seen as two definitions and is legal:

square
	:: Integer -> Integer
square n = n * n

The following are not legal, Haskell sees the first as one definition and the second as two definitions:

square :: Integer -> Integer
	square n = n * n


square
:: Integer -> Integer

Subscribe to my Substack to be notified of future posts.