Functional Programming and Intelligent Algorithms

Overview

Within two days, we have to get to grips with the basics of Haskell. This is the first tutorial, which you should be able to complete before lunch.

• Reading: Simon Thompson, Chapter 1-3

Tutorial

Step 1: Getting started

First of all, we need to get to grips with the Haskell interpreter, that is ghci.

Note Chrome, Chromium, and Opera do not display math-ml correctly. If none of the mathematical expression in Item 3 below show exponentiation, then you need to switch browser. Firefox, Safari, and Iceweasel work well.

Do the following.

1. Open a terminal window
2. Start ghci on the command line
3. Use ghci to calculate the following expressions:
• $7+\mathrm{37}·\mathrm{63}=$
• $3·\left(\mathrm{12}+9\right)=$
• ${\mathrm{11}}^{16}=$
• $\genfrac{}{}{0.1ex}{}{\cos \pi }{2}=$
• $3^{12}mod\mathrm{19}=$
• ${\mathrm{0.4}}^4=$

4. ghci has a number of interpreter commands which are not part of the Haskell language. Such commands start with a :. Have a look at the list of available commands by typing

   :help

   You will see some of the listed commands in use later.

5. Exit ghci. You can use either Ctrl-D or the :quit command to exit.

Step 2: The Pictures Example

A major benefit of functional programming is that we often get a description which closely resembles natural or mathematical language as we would use it in a textbook or report. Functional languages are often used to define domain-specific languages (DSL), which support simple and intuitive definition of problems and solutions within a specific domain. Simon Thompson gives a simple example in the Pictures module, which gives a simple DSL for image operations.

1. Download the source code for the textbook. You can do this on the commandline using: wget https://hackage.haskell.org/package/Craft3e-0.1.0.10/Craft3e-0.1.0.10.tar.gz
2. Unpack the tarball. tar xzf Craft3e-0.1.0.10.tar.gz
3. Unpacking the tarball gives you a new directory with all the source code for the textbook. Change into this directory: cd Craft3e-0.1.0.10
4. Start ghci inside the Craft3e directory
5. Load the Pictures module :load Pictures
6. Print (render) the horse image as ASCII graphics printPicture horse Does it look like a horse?
7. Try the standard print function too: print horse This shows the raw data representing the image. You see a list of strings, each string enclosed in double quotes, and the list enclosed in square brackets with commas to separate the elements.

We will use the Pictures module for several exercises later.

Step 3: Pictures with SVG rendering

The ASCII arts used above isn't too pleasing to the eye. There is a variation rendering SVG graphics as well, namely the PicturesSVG module. It requires a browser on the side for the display. Test it, and see that it works.

1. Make sure that Craft3e-0.1.0.10 is the current directory.
2. Open the file refresh.html in a web browser, e.g. firefox refresh.html & The ampersand (&) makes the program start in the background, so that it does not block the command prompt.
3. Start ghci and load the PicturesSVG module. You can do this in two steps, as with the Pictures module above, or you can do both in a single step giving the module name as an argument to ghci: ghci PicturesSVG
4. Render the horse picture render horse
5. Take each of the images which you printed in ASCII in the previous step, and render them as SVG.

Step 4: Making a script

Although ghci makes a neat calculator out of the box, that's not quite what we want in this module. To solve complex problems we need to write our own programs, that is, define our own functions. This is usually done in a text file to be loaded into ghci later.

1. Make a new directory to keep your notes and files for this first tutorial. E.g. mkdir Tutorial01
2. Change into the new directory. E.g. cd Tutorial01

3. Open an editor to edit a Haskell file. E.g.

   gedit MyFirst.hs

   The name of a Haskell file (script) have to end with .hs and should start with an upper-case letter. E.g.\ MyFirstScript.hs.

4. Start with a comment at the top of your file to claim authorship, e.g. -- John Doe <[email protected]>

   Comments are ignored by the compiler or interpreter, and are purely a help for human readers.

5. Define a new module by adding a module header under the comment module MyFirstScript where Note that the module name must match the filename without the .hs extension.
6. Define your first function inside the greet :: String -> String greet name = "Hello, " ++ name
7. Save the file
8. Start ghci from the command line
9. Load your script, e.g. :l MyFirstScript
10. Test the function greet "John"
11. You can add more functions to your module. Do not close ghci. Use a different window to add a new function to your module. square :: Int -> Int square n = n*n
12. Returning to ghci, reload the module using :reload
13. Test the new function: square 5

Step 5: Working with Integers

One of the fundamental data types is integers. In fact Haskell has two integer types, namely Int and Integer. We shall make a little experiment to see the difference.

1. Open your text editor with a new file, IntTest.hs is a good name.
2. Define a function to do exponentiation of Integer. pow1 :: Integer -> Integer -> Integer pow1 x y = x^y
3. Define another function to do exponentiation of Int. pow2 :: Int -> Int -> Int pow2 x y = x^y
4. Open ghci and load the module you just created.
5. Test the two functions, with small and big arguments. pow1 2 10 pow2 2 10 pow1 2 65 pow2 2 65 pow1 3 39 pow2 3 39

What happens? Why do pow1 and pow2 give different answers?

Step 6: Working with Booleans

Boolean is another fundamental data type, with two possible values, True or False.

1. Open your editor to create a new Haskell module, e.g. BoolTest.hs
2. Add the customary comment to identify yourself as author and the module header.
3. Add a couple of functions: myNot :: Bool -> Bool myNot False = True myNot True = False myAnd :: Bool -> Bool -> Bool myAnd True True = True myAnd _ _ = False Both functions are standard logical operators, the negation (not) and the conjunciton (and).
4. Start ghci, load your module, and test the above functions. Are you happy with the results?
5. Add functions for logical or (myOr) and exclusive or (myXOR) to your module using pattern matching and literals. There is more than one way of doing it, so just think about the mathematical (logical) meaning and do it your way.
6. Reload your module and test the new functions. Do they work as intended?

Step 7: Working with Floating Point Numbers

Many of our algorithms work on real numbers. Unfortunately, the computer does not support real numbers. Instead we have to work with floating point numbers. There are two floating point data types in common use. In Haskell, they are called Float and Double, but they are defined by the CPU architecture and not by the language. Let's explore this

1. Why cannot computers work with real numbers?
2. Start ghci
3. Compare the following expressions 2**500 :: Double 2**500 :: Float 2**(-500) :: Double 2**(-500) :: Float

The floating point types permit a couple of non-numeric values, namely ±Infinity, and NaN (Not a Number).

• What value do you get from the following expressions: 1/0 0/0 isNaN (log (-1)) (log (-1)) == (log (-1)) (1/0)*0 isInfinite (0/0) isInfinite (1/0)

NaN values will usually just propagate through floating point operations, so that NaN in gives NaN out. However, some operations have unpredictable results, so you should check for NaN whenever there is a risk that NaN has occured.

• What value do you get from the following expressions: ceiling (log (-1)) ceiling (0/0) floor (0/0)

Step 8: Playing with Pictures

Do Exercises 2.1-2.4 in Simon Thompson's book.