class: center, middle # Haskell: A Crash Course in Functional Programming *Matthew Alger* .sidenote[Presented at NCSS 2016] --- # A brief introduction Me: - Matthew (hello!) - Studying CS/Physics at the ANU - Software Engineering Intern at Google - NCSS '12/'13, Tutor '15 Haskell: - Functional .sidenote[(a program is just function evaluation)] - Lazily evaluated .sidenote[(evaluates only when necessary)] - Strongly typed .sidenote[(we know the type of all data at all times)] - Made by people who really like mathematics --- # What we're going to do We're going to: - Learn how to do basic things in Haskell - Talk about interesting computer science concepts - Get a feel for functional programming - Think about things differently! --- # Outline - Data and types - Functions - Defining types - Pattern matching --- layout: true # Data and types --- ## A crash-course in types What is a type? - Types tell you what properties some data have - Types tell you what you can do to that data - All data have a type - All data with a particular type behave the same way --- ## A crash-course in types Common examples: - `3` is an `Integer` - `1.21` is a `Float` - `3.0` is also a `Float` - `True` is a `Bool` - `'h'` is a `Char` If we need to write down what type some data is, we use `::` . - `3 :: Integer` means "`3` is an `Integer`" - `1.21 :: Float` means "`1.21` is a `Float`" - `True :: Bool` means "`True` is a `Bool`" - `'h' :: Char` means "`'h'` is a `Char`" --- ## Numeric types **`Integer`**. Whole numbers. You can add them, multiply them, and subtract them: ```haskell 1 + 2 2 * 5 7 - 4 ``` **`Float`**. Decimal numbers. You can add them, multiply them, subtract them, and divide them: ```haskell 1.134 + 2.4 2.3 * 5.0 7.1 - 4.34567 8.5 / 4.0 ``` --- ## .aside[Aside: ] Syntax Comments: ```haskell -- haskell will ignore this line ``` Order of operations: ```haskell 4 * (2 + 3) -- use parentheses to change evaluation order ``` --- ## Booleans **`Boolean`**. Either `True` or `False`. Used for logic. ```haskell coolResult = if x < 4 then 100000 * 34 else 15 ``` You can make booleans by doing comparisons like `<`, `>`, `==`, and `/=`, and you can also just write `True` and `False`. --- ## Lists Lists are ordered collections of data. We write a list with square brackets, and separate the data in the list with commas. ```haskell [1, 2, 3, 7, 9, 11] ``` All data in the list must be the same type! Lists are data, too, so they have a type. The type of a list is the type of whatever is in the list, surrounded by square brackets. ```haskell [1, 2, 3] :: [Integer] -- a list of Integers [True, False, False, True, False] :: [Bool] -- a list of Bools [[1, 3, 5], [1], [2, 3]] :: [[Integer]] -- a list of lists of Integers! ``` --- layout: true # Functions --- ## Functions in Haskell In other languages, you *call* a function, and the function *does stuff*. In Haskell, you *apply* functions to data, and they *transform* that data in some way. Your whole program becomes one big function evaluation. - No loops, just functions - No variables, just input and output - Sadness, tears, and pain --- ## Like in mathematics! Here's a mathematical function definition: $$parabola(x) = x^2$$ Here's how you'd use that: $$parabola(2) \rightarrow 2^2 \rightarrow 4$$ Here's the same function definition in Haskell: ```haskell parabola x = x^2 ``` Here's how you'd use that: ```haskell parabola 2 -- same as 2^2 from the definition -- 4 ``` --- ## Applying functions to data Say I have a function `addOne` that takes one number and adds `1` to it. To use that function, I just write: ```haskell addOne 4 addOne 8 addOne 100 ``` and these would become `5`, `9`, and `101` respectively. Say I have a function `add` that takes two numbers and adds them together. To use that function, I just write: ```haskell add 1 3 add 5 2 add 8 6 ``` and these would become `4`, `7`, and `14` respectively. --- ## Some basic, standard functions On numbers: - `mod`, integer remainder of two numbers - `div`, integer division of two numbers - `negate`, negates one number - `even`, checks if a number is even - `odd`, checks if a number is odd - `pi` is a function that takes *no* arguments and gives a number back - `sqrt` is a function that takes a `Float` and gives its square root back **Try using them!** The syntax is: ```haskell function arg1 arg2 arg3 ... odd 5 -- for example ``` --- ## Some basic, standard functions On lists: - `head` takes a list and gives you the first thing in it - `last` takes a list and gives you the last thing in it - `tail` takes a list and gives you a list of everything but the first thing in it - `init` takes a list and gives you a list of everything but the last thing in it - `reverse` takes a list and reverses it - `take` takes a number `\(n\)` and a list, and gives you back the first `\(n\)` things from that list (Lists are much more interesting than numbers!) **Try these too!** Remember, list syntax is ```haskell ['h', 'e', 'l', 'l', 'o'] ``` --- ## Writing functions Writing functions is pretty much just like you would write them in mathematics. ```haskell addOne n = n + 1 add x y = x + y ``` Now we're getting somewhere. **Try defining your own** — a classic example is to implement the quadratic formula: $$x(a, b, c) = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$ -- ```haskell x a b c = (-b + sqrt (b^2 - 4*a*c))/(2*a) x 1 3 1 -- -0.3819660112501051 ``` --- ## Function types If you want to refer to a function, you just use its name: `sqrt`, `addOne`, `even`, `head`, `tail`... In Haskell, functions are data! Since they're data, they also have types. The type of a function `f` that takes one `Integer` and returns a `Char` looks like this: ```haskell f :: Integer -> Char ``` Reasonably intuitive! The type of a function `f` that takes *any* type and then returns something of the same type looks like this: ```haskell f :: a -> a ``` (Note that `a` is lowercase — it's just a placeholder. We could also have used `b`, `any`, `sometype`...) --- ## Function types Here are some types for functions we've already seen: ```haskell even :: Integer -> Bool odd :: Integer -> Bool head :: [a] -> a tail :: [a] -> [a] sqrt :: Float -> Float ``` --- ## Function types What if we have multiple arguments? The `div` function takes two `Integer`s divides them, and returns the integer part of the result. Its type looks like this: ```haskell div :: Integer -> Integer -> Integer ``` `take` takes an `Integer` and a list of any type, and gives back a list of the same type. Its type looks like this: ```haskell take :: Integer -> [a] -> [a] ``` <!-- The astute readers amongst you, presumably the ones reading this source code, will note that the type of `take` isn't actually `Integer -> [a] -> [a]`, it's `Int -> [a] -> [a]`. However, the distinction between Integer and Int is beyond the scope of this talk. --> The basic format, then, is to just chain together the types of all your arguments with `->` separating them, then put another `->`, then put the return type. .sidenote[(There's a fantastic reason for this weird syntax; I'll explain it if we get time.)] --- ## Function types When you write a function, Haskell can guess its types. But it's good practice to put the types above each function, like so: ```haskell addOne :: Integer -> Integer addOne x = x + 1 ``` --- layout: false # Branching Branching is when you do different things based on a condition. There are three main ways this is done in Haskell. ```haskell x = if y == 2 then 2 else (y + 1000) ``` The `if` here is an *expression* — it itself has a value, unlike in Python or C where an `if` is a *statement* controlling program flow. ```haskell x | y == 2 = 2 | y >= 10 = y - 10 | otherwise = y + 1000 ``` This is called a "guard"; you can use any `Bool` on the left of the `=` sign and the expression on the right is returned for the first `True` left-hand side. --- # Branching The third way is called *pattern matching*. We need to know more about types to cover it properly, but the basic idea is that you replace one of your function arguments with a *pattern*. At the simplest level, this might just be a value. Then, that particular function definition only runs if the pattern is matched by the input values. If your data contains other data (like a list), then you can also match using placeholders, and Haskell will store the corresponding data in those placeholders (check the code below for an example). ```haskell myDivision :: Float -> Float -> Float myDivision a 0.0 = 10000000.0 -- basically infinity, right? myDivision a b = a/b -- usage examples myDivision 1.0 0.0 -- 10000000.0 myDivision 1.0 2.0 -- 0.5 ``` ```haskell contrivedList :: [Integer] -> Integer contrivedList [] = 0 contrivedList [x, y] = x + y contrivedList list = head list -- usage example contrivedList [1, 2] -- 3 ``` --- # Recursion In Haskell, there are no loops. Instead, you just define functions in terms of themselves. Here is how you might implement factorial: ```haskell factorial :: Integer -> Integer factorial 0 = 1 factorial n = n * factorial (n-1) ``` This is called *recursion*. We can also use recursion to do things with lists, but we need to know more pattern matching for that. --- layout: true # List Patterns --- We'll cover list patterns quickly here so you can try them out, then we'll come back after we do some more stuff with types. Haskell has an operator called `:` and it prepends things to lists: ```haskell 1 : [] == [1] 1 : [2, 3] == [1, 2, 3] 1 : 2 : [3] == [1, 2, 3] 1 : 2 : 3 : [] == [1, 2, 3] ``` You can use this in patterns to "unprepend". For example, `1 : rest` matches any list starting with `1`, and then stores the rest of the list in `rest`. ```haskell -- this function cuts off the first 1 from a list contrived :: [Integer] -> [Integer] contrived (1:rest) = rest contrived list = list -- usage examples contrived [1, 2, 3] -- [2, 3] contrived [2, 3, 4] -- [2, 3, 4] ``` --- We can also use placeholders instead of literal values, e.g. `first : rest` — here, Haskell would match any list with at least one thing in it, store the first thing in `first`, and the rest in `rest`. We could use this to implement `head`! **Try this yourself!** Remember, `head` takes a list and returns the first thing in it. ```haskell head :: [a] -> a ``` -- ```haskell head (first:rest) = first ``` --- Now, we have the tools to do really interesting things to lists. Let's try writing a function that returns the last thing in a list. If we have exactly one thing in the list, then our list would be something of the form `[x]` and the last element is `x`, so we can write that down: ```haskell last :: [a] -> a last [x] = x ``` If we have more than one thing in the list, then we really only need to cut off the first thing and get the last thing in the rest of the list. ```haskell last (first:rest) = last rest ``` And that's it! Note that Haskell will try and match these patterns in order, so if you put `(first:rest)` first, it'll match `x:[]` and you'll try calling `last` on an empty list. --- layout: true # Defining types --- Haskell uses *algebraic data types*, meaning you can combine different types to make new types. You could (if you wanted to) define `Bool` like this: ```haskell data Bool = True | False ``` This line defines a new type called `Bool`. `|` can be read as "or" or "union"; this kind of type is called a *union type*. Another example: ```haskell data TemperatureUnit = Celsius | Fahrenheit | Kelvin ``` `Celsius` etcetera are literal values, so you can just use them in your code. ```haskell temperatureSystem :: [Char] -> TemperatureUnit temperatureSystem country = if country == ['U', 'S', 'A'] then Fahrenheit else Celsius ``` --- ## .aside[Aside: ] Deriving `Show` for sanity When you make a type, Haskell assumes that there's no way to print it out, ever. You can tell it to try and guess how to print out your type: ```haskell data TemperatureUnit = Celsius | Fahrenheit | Kelvin deriving (Show) ``` Now you can use your type in Haskell and Haskell won't get confused when you return values of the type. If you get errors like `No instance for (Show Temperature) arising from a use of 'print'`, you probably haven't derived `Show`. --- You can also combine multiple kinds of data into one type: ```haskell data Temperature = Temp Float TemperatureUnit -- example Temp 100.0 Celsius ``` `Temperature` is the name of the type, and `Temp` here is called a *type constructor* — it's how we tell Haskell that we're talking about a `Temperature` rather than just putting random words down. This is called a *product type*. --- You can combine union and product types to make even more types. This one is either an `Integer` or a `Char`: ```haskell data EitherIntOrChar = EitherInteger Integer | EitherChar Char ``` `EitherInteger` and `EitherChar` are type constructors. If we didn't have those, then Haskell couldn't tell that we're using `EitherIntOrChar` types instead of `Integer`s or `Char`s. To use this type, you'd just have to put one of the constructors in front of the associated value: ```haskell EitherInteger 1 :: EitherIntOrChar EitherChar 'h' :: EitherIntOrChar [EitherChar 'h', EitherChar 'e', EitherInteger 1, EitherInteger 1, EitherChar 'o'] :: [EitherIntOrChar] ``` --- Maybe we have a function that returns a number sometimes, but might break sometimes — maybe a function that gets the square root of a number, but instead returns some special value if the number we put in is negative. ```haskell maybeSqrt :: Float -> Float maybeSqrt x = if x >= 0 then sqrt x else ??? ``` But what can we return? We shouldn't return a `Float` because then we couldn't distinguish it from an actual answer. Maybe we can make a new type: ```haskell data MaybeFloat = Yes Float | NoFloat ``` So something in our new data type is either a `Yes Float`, or it's `NoFloat`. Example values in this type: ```haskell Yes 10.0 Yes 234.23 Yes pi NoFloat ``` --- Now, we can use our new type. ```haskell maybeSqrt :: Float -> MaybeFloat maybeSqrt x = if x >= 0 then Yes (sqrt x) else NoFloat ``` --- We can generalise this to work with any type, not just `Float`s, by using a *type variable*: ```haskell data Maybe a = Just a | Nothing ``` I've changed the names from `Yes` and `NoFloat` to `Just` and `Nothing`, because Haskell actually includes this type for you. It's called the `Maybe` type. `a` can be whatever type you want, so we can rewrite `maybeSqrt` using this. ```haskell maybeSqrt :: Float -> Maybe Float maybeSqrt x = if x >= 0 then Just (sqrt x) else Nothing ``` This is commonly used to handle errors. --- ## Types and pattern matching Pattern matching can be used to break down a type. For example, say we have a `Maybe Integer` and we want to add one to it if there's a number in it, and return `Nothing` if not. ```haskell maybeAddOne :: Maybe Integer -> Maybe Integer maybeAddOne Nothing = Nothing maybeAddOne (Just something) = Just (something + 1) ``` You can compare this to the definition to see how pattern matching lets you break down types. ```haskell data Maybe Integer = Nothing | Just Integer ``` --- ## Recursive type definitions You can define a type in terms of itself. Such a type is called a *recursive type*. Lists, it turns out, are recursive, and you can define them like this: ```haskell data List a = EmptyList | Prepend a (List a) ``` Or, rewriting this with list syntax: ```haskell data [a] = [] | a : [a] ``` Now you might be able to see why pattern matching can use `:` to break down a list. --- layout: false # Suggested exercises - Find the number of elements in a list - Find the second-last element in a list - Sum a list of integers - Reverse a list - Apply a function to every element in a list # Where to go from here - Lazy evaluation - Higher order functions: `map`, `filter`, `fold`, `zipWith` - More complicated data structures like trees - IO - Currying and partial application - Functors, applicative functors, and monads If we have time, I can go through some of these things.