ZSdoH

Introduction to Functional Programming

University course in functional programming with Haskell for computer science and engineering.

Aug 31, 2021
Downloads ‐ HTML, Markdown, PDF
All Files ‐ Post Files

What is software

You can think of software as the following.

\[ \text{software = programs + data} \]

Where programs is some sort of a program written in any programming language and data being some sort of data stored in several ways, some examples are listed below.

  • numbers, letters, email messages
  • maps, video clips
  • mouse clicks, other programs

In the most basic sense, programs compute new data from old data, think of programs as things that take some sort of input and give out some kind of output. For example.

  • A computer game computes a sequence of screen imags from a sequence of mouse clicks
  • vasttrafik.se computes an optimal route given a source and destination bus stop

Programming languages

The most basic way to write a computer program is to write the binary machine instructions by hand. Alternatively the first abstraction layer above that would be to write assembler. Although this can be very tedious because they are so low-level. Therefore we use higher level programming languages which are easier to write and in many cases can optimize certain operations better than a programmer might do.

  • Programs are written in programming languages
  • There are hundreds of different programming languages, each with their strengths and weaknesses
  • A large system will often contain components in many different languages, each fit for its task.

Two major paradigms

Imperative programming

  • Instructions are used to change the computers state
    • \(x := x + 1\)
    • delete_file(“slides.pdf”)
  • Run the program by following the instructions top-down

Functional programming

  • Functions are used to declare dependencies between data values
    • \(y = f(x)\)
    • \(x = 32\)
  • Dependencies drive evaluation

Functional programming

As said before, Functions are used to delcare dependencies between data values such as \(y = f(x)\). The basic building block of a functional program is the function. The functions are used to compose functions into even larger functions for more complex tasks. In a pure function, the result only depends on the argument given to it, there is not other data it reads or gets.

Purpose

Hopefully this and the later posts in this series will.

  • Make it easy to learn more programming languages.
  • Make it easy to adapt to new programming languages.
  • Appreiciate differences between languags.
  • Become a better programmer.

Last but very importantly, the rest of this will use the Haskell functional programming language as the main programming language, see haskell.org.

Why Haskell?

  • Haskell is a very high-level programming language
    • Lets you focus on the important aspects of programming
  • Haskell is expressive and concise
    • Can achieve a lot fiwth little effort
  • Haskell is good at handling complex data and combining components
  • Haskell is defining the state of the art in programming language development
  • Haskell is not particularly high-performance language (see C/C++ or Assembly instead)
    • Prioritizes programmer-time over computer-time

Jumping into Code

First you will need a text-editor of some sort, for example vim, emacs, vs code, sublime ect. Second you will need to install haskell on your computer. Search up on how to do this. On ubuntu linux distros however it should just be

sudo apt install haskell-platform

in the terminal. Which should install all the appropriate tools required to develop haskell programs.

You can start using the haskell interpreter in the command line (terminal) by just typing ghci (to exit press control-d or type “:q” in the interpreter).

fullnitrous@fullnitrous:/haskell$ ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude>

We can begin by writing a very simple function.

Prelude> f x = x + 1

What we have done now is declared the function x and also defined it with x + 1. Therefore if we run it with the value of 2 we can the following output.

Prelude> f 2
3

The interpreter is a great way to explore the language and see what works ect. But do not forget that what you write in the interpreter session will not be saved so do not write full programs which are supposed to be run several times. In that case you will want to write the program in a text file and then run it from that text file, this is also called persistent data storage (more spesifically source code).

We can therefore create a very small haskell program by creating a file called “lecture_1a.hs” (.hs being the haskell source code file extension). Then write the following in the file.

We can load this file into the interpreter by doing the following command in the terminal.

fullnitrous@fullnitrous:/haskell$ ghci lecture_1a.hs
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( lecture_1a.hs, interpreted )
Ok, modules loaded: Main.

We can also write :browse to see everything that has been declared and is available to run from the source file we loaded.

*Main> :browse
main :: IO ()

We can of course also call the function main for which we have defined without any arguments. Which will yield the following.

*Main> main
"testing"

We can see that it did what the function was defined to do (to print out what we put between qoutation marks).

We can also, if we want to run the program in a non interactive way do the following.

fullnitrous@fullnitrous:/haskell$ runghc lecture_1a.hs
"testing"

Important to note that when running the program this way it will search for a function called main as its entry point which will be the function it will run. As we can see it gives the same output.

Lastly we can actually also compile the program we created into an executable/binary file on our disk which we can run later.

fullnitrous@fullnitrous:~/haskell$ ghc --make lecture_1a.hs 
[1 of 1] Compiling Main             ( lecture_1a.hs, lecture_1a.o )
Linking lecture_1a ...

We can then list all the files in our currently directory to see that a couple of files have been created. Most importantly lecture_1a which is the executable file.

fullnitrous@fullnitrous:~/haskell$ ls
lecture_1a  lecture_1a.hi  lecture_1a.hs  lecture_1a.o

We can now run the file in the following way and also see that we get the same output.

fullnitrous@fullnitrous:~/haskell$ ./lecture_1a
"testing"

But for the majority of code here we will pass the file into the interpreter just to run it instantly, although in productio code you may want to compile it into a runnable file for several reasons.

Inside the haskell interpreter you can also load a file the following way instead of needing to pass it to the interpreter on startup, this may come in handy as well.

fullnitrous@fullnitrous:~/haskell$ ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude> :l lecture_1a
[1 of 1] Compiling Main             ( lecture_1a.hs, interpreted )

Then we can just run our main function as before.

*Main> main 
"testing"
*Main>

Everything we write in the haskell source code must follow the appropriate grammitical and syntactical rules per the language we are using, that is haskell. Therefore if we have the following source code.

Then in the interpreter we can just reload (by doing “:r”) the previous file we loaded.

*Main> :r
[1 of 1] Compiling Main             ( lecture_1a.hs, interpreted )

lecture_1a.hs:2:1: error:
    Parse error: naked expression at top level
    Perhaps you intended to use TemplateHaskell
Failed, modules loaded: none.

And as we can see we got an error which we expected. Also notice that it tells you which file the error occured on and also the line and column number. So you can very quickly and easily find where the error occured in the file.

Comments

A comment is basically a bit of text that does not get run and that the compiler and or the interpreter just ignores, they can be used to comment and describe what certain parts of your code do for clarity. You can also use them for other puposes. Again, in the simplest terms, they are text intended to be read by humans, not the computer.

If you wish to write a comment only spanning a single line, you can do the following.

If you wish to write a multi line comment in haskell you can do the following.

Standard Library

There exists a thing in many programming languages called the standard library, this is basically a set of functions and definitions ect which are defined by default by the language itself, they exist because the functionality they provide is used so much that they are just given to you directly so you don’t have to make the functions yourself.

By typing “:browse Prelude” in the interpreter we get a very long list containing everything that is pre-defined for you already.

Prelude> :browse Prelude
(!!) :: [a] -> Int -> a
($) ::
  forall (r :: GHC.Types.RuntimeRep) a (b :: TYPE r).
  (a -> b) -> a -> b
($!) :: (a -> b) -> a -> b
(&&) :: Bool -> Bool -> Bool
(++) :: [a] -> [a] -> [a]
(.) :: (b -> c) -> (a -> b) -> a -> c
(<$>) :: Functor f => (a -> b) -> f a -> f b
(=<<) :: Monad m => (a -> m b) -> m a -> m b
class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  (*>) :: f a -> f b -> f b
  (<*) :: f a -> f b -> f a
  {-# MINIMAL pure, (<*>) #-}
data Bool = False | True
class Bounded a where
  minBound :: a
  maxBound :: a
  {-# MINIMAL minBound, maxBound #-}
data Char = GHC.Types.C# GHC.Prim.Char#
data Double = GHC.Types.D# GHC.Prim.Double#
data Either a b = Left a | Right b
...

(The output is truncated because of demonstration purposes)

Simple Functions

We can declare and define a function in haskell by first typing the name of the function followed by the parameter(s) then a equal sign followed by the function body which defines what the function will do.

Reloading our interpreter session we can call the function and see that it does what we expect it to do when calling the appropriate name with the appropriate number of parameters.

*Main> inc 2
4

We can also declare and define variables by doing the following.

Which now means that y is an integer with the integer value of 32. The type integer being well-defined in the haskell language.

We can now also write that y = 32 in the interpreter and then call the function with y instead of passing a value directly and it will execute as we expect.

*Main> y = 32
*Main> inc y
34

Lets say for example we would want to have a function to square a number, then we can simply just define a function like this.

Reload and then test.

*Main> sq 8
64

We can of course also have multiple arguments to a function.

where we now define a function add which takes the parameters x and y and returns the sum of them.

Now lets just make a useful function that already exists in the standard library but just for practice. The function in mind is the abs function, which returns the absolute value of the input.

*Main> abs (-3)
3

Since the function abs already exists we are just calling it abs' instead. Note that it takes one argument x and it checks a condition, denoted with | which is that if x > 0 then it returns x. Otherwise if x < 0 it returns the negative of x which would make it positive again. Notice how the function definition can span multiple lines.

We have now made our own version of the abs function called abs' which is functionally the same and can be used in the same way.

But that is not entirely true.

Now it covers for if x is equal to 0, notice x >= 0. Also, if we have several conditions we can actually just write the following instead for cleaner code.

So be aware of small details as such.

Lets also define an xor operation in haskell.

What we have defined now is a function xor which if it gets True False or False True as its parameters it returns True. Otherwise for any other input denoted by _ it returns False. Notice how we can define the functions behaviour in the parameter list in declaring the function.

To be more precise when declaring and defining functions we can add a little line atop the function we are declaring and defining to show what types it takes in and outputs. We can do that in the following way.

Which now means that it takes in two Boolean values and returns a Boolean value. Now this isn’t required because haskell can infer the type itself although it is good to so because we have a more well defined function.

We can also get the type of a value or return value in gchi by typing :t.

Prelude> :t True
True :: Bool

We also get better error messages when we have more well defined types because if we were to input an int to the xor function it would spot the error saying that you were trying to input a integer contra a boolean value.

Looping in Haskell (Recursion)

In other programming languages you have loops of different types which allow the programmer to repeat certain tasks/things. Although in haskell you mainly use recursion for that task.

For example we can define a power function in the following way.

Although this function will cause a stack overflow on the machine you are trying to run it on because haskell does not know when to stop it. Notice that the function power is calling itself in the function body. This can be dangerous if there is no clear exit point, that is to say where it stops calling itself.

We can fix that by doing the following.

Which will now instead just return 1 when k is equal to 0.

Exercises

Consider the following function which defines a way to calculate \(n^k\).

Exercise 1

Define a function which returns the number of recursion steps power will take to calculate the power. The function should be in the following form.

Exercise 2

A different way of computing the power function is to use the standard Haskell function product, which calculates the product (multiplication) of all elements in a list. The general idea is to construct a list with k elements all being n then use product to multiply them together.

Note For how to construct such a list search “list comprehensions in haskell” for more information.

Exercise 3

A different approach to calculating the power function uses fewer computing steps. We use the fact that if k is even, we can calculate \(n^k\) in the following way.

  • if k is even then \(n^k = \left(n^2\right)^{k/2}\), in other terms \(n^k = \left(n \times n\right)^{k/2}\)
  • if k is odd then \(n^k = n \times \left(n^{k - 1}\right)\)

So, instead of recursively using the case for k - 1, we use the smaller case for k/2. If k is not even we simply do k - 1.

In short.

  • if k is even, then \(n^k = \left(n \times n\right)^{k/2}\)
  • if k is odd, then \(n^k = n \times \left(n^{k - 1}\right)\)

Implement this as a Haskell function called power2. This function should still be using recursion.

Note Divide integer numbers by doing div x y. Check for even or odd values by doing even x and odd y.

Exercise 4

Make two functions comparePower1 and comparePower2 which respectively checks that power is in accorande with power1 in the return values and that power is in accordance with power2. Use a list comprehension to put all the comparisions in a list and then check that all are True with the and operator in Haskell.

References