# Learning Haskell

*
15 Jun, 2016
*

Haskell is a *functional programming* language, very different to the
programming languages I'm used to (C++, Python, JavaScript...). I've been
hearing about Haskell for a while; people emphasize its elegance, its
mathematical inspiration and foundation, and the fact that being based on such a
different paradigm with respect to imperative programming it helps thinking
about programming from a very different
perspective.
Python, Java, C++... are all languages that are incorporating concepts from
functional programming to their latest versions. Therefore I was willing to
learn some Haskell.

*Haskell logo*

## Material

I began to look for books, tutorials, presentations, etc. For me, the best book for beginners is Learn You a Haskell for Great Good!. This presentation (in Spanish) by UJI professor Andrés Marzal is also very interesting and entertaining (in two hours and a half he starts presenting Haskell and ends up explaining some pretty advanced features), it also includes some great pdf notes. I also checked the book Real World Haskell, which I don't think is the best book to start with, but it surely has very interesting information if you want to develop larger projects.

## Practice with... the Judge!

Once I was convinced of the benefits of Haskell, I wanted to start writing some
code, but did not have any project in mind. That's when I thought of learning
Haskell the same way I had learned to program in C++ many years ago: with **the
Judge**.

*The Judge with the classic traffic light:
green or red depending on whether your program is correct or not.*

The Judge is a platform to learn how to
program, developed by professors Jordi Petit and Salvador Roura at UPC. This
platform contains problems to be solved by programs that are sent to the same
Judge, which automatically checks whether their execution is correct. The Judge
is used in many UPC programming and algorithms courses and **its use is open to
the public**, even more... **it contains 33 problems of a Haskell programming
course**!

Thus, in recent weeks I have done these 33 problems :-). It has been a very fun experience and a great excercise to get familiar with the language and the development environment.

## Haskell examples

Next I'll show some Haskell features to give an idea of its potential. These concepts are explained in more depth in Learn You a Haskell for Great Good!, here I will present them together with some code examples.

Working in Ubuntu, you can install `haskell-platform`

(```
sudo apt-get install
haskell-platform
```

) and use the `ghci`

interpreter. You can save the programs in
files (e.g. `prog.hs`

), defining in them the funtions you want. Then, these
functions can be loaded (and reloaded) with `ghci>: l to prog`

, which makes
them available to be used and tested.

Let's see which are these interesting Haskell functionalities...

### Recursion

Haskell, as a functional programming language, doesn't have loops: no `while`

,
no `for`

. One way to implement what could be done using loops is through
recursion. An example with the factorial function:

$$factorial(n) = n! = n\cdot (n-1)\cdots2\cdot 1$$

Recursively, we could define it as:

$$\begin{cases} factorial(0) = 1 \\ factorial(n) = n\cdot factorial(n-1) \end{cases}$$

And in Haskell, it could be implemented as follows:

```
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n-1)
```

The first line is the *signature* of function, which specifies the type of the
parameter and result. In our case, we use `Integer`

, which are integer numbers
of arbitrary length.

### Lists

Many programs need to work with lists of values, and Haskell offers us many ways to do it comfortably. For example, let's see some ways to get even numbers between 0 and 20:

```
Prelude> [2,4..20]
[2,4,6,8,10,12,14,16,18,20]
Prelude> filter even [1..20]
[2,4,6,8,10,12,14,16,18,20]
Prelude> [x | x <- [1..20], even x]
[2,4,6,8,10,12,14,16,18,20]
```

Note the last expression, which is a *list comprehension*, very similar to the
mathematical notation $\left\{x \; \vert \; \forall\, x \in {1,\ldots,20},\;
iseven(x)\right\}$.

Using recursion and list comprehensions we can implement the **quicksort**
sorting algorithm. Given a list, quicksort orders the items as follows:

- Choose the first element as a
*pivot*. - Build two lists: the first with elements smaller than the pivot, and the second with elements bigger than the pivot.
- Sort these two lists using the same quicksort algorithm.
- The result is a list containing the sorted smaller values, followed by the pivot, followed by the sorted list of bigger values.

The Haskell implementation of this algorithm can be very neat:

```
qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) =
qsort [y | y <- xs, y <= x] ++ [x] ++ qsort [y | y <- xs, y > x]
```

### Lazy evaluation

Haskell is based entirely on the *lazy evaluation*, ie, making the calculations
as late as possible, and that's when they are needed by someone else. This
enables the language to use endless lists, because values of the list are
only calculated when another task needs them. For example:

```
Prelude> take 5 [1 ..]
[1,2,3,4,5]
Prelude> take 10 [1 ..]
[1,2,3,4,5,6,7,8,9,10]
```

Using this feature, we can implement the sieve of Eratosthenes algorithm, which generates the list of prime numbers.

The sieve of Eratosthenes begins with number 2 (which is prime) and marks all its multiples. It repeatedly takes the smallest number not marked, which is prime because it is no a multiple of any other smaller number, and again marks all of its multiples.

This process returns all primes smaller than a given number:
obviously we can not mark *all* even numbers, because they never end.
Moreover, what we can do is to discard all even numbers lower than 1000, for
example. Haskell, however, by using lazy evaluation, is able to work
with never ending lists and therefore allows a very simple implementation:

```
primes :: [Int]
primes = sieve [2..]
where
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]
```

We save it in the file `primes.hs`

and we can run:

```
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Prelude> :l primes
[1 of 1] Compiling Main ( primes.hs, interpreted )
Ok, modules loaded: Main.
*Main> take 5 primes
[2,3,5,7,11]
*Main> takeWhile (<50) primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
```

### Higher order functions

Higher order functions are functions that take other functions as parameters.
An example is the `map`

function, which takes a function as the first parameter
and a list as the second parameter, and it applies the function to each item in
the list. For example:

```
Prelude> map (* 2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
Prelude> map (^ 2) [1..10]
[1,4,9,16,25,36,49,64,81,100]
```

Given a list of integers, and a list of exponents, we can raise each number to the given power:

```
Prelude> zipWith (^) [1..5] [1..5]
[1,4,27,256,3125]
```

Here You can find more examples of higher order functions and their use.

### Pattern matching

Another interesting feature of Haskell is *pattern matching*. We can check the
pattern `(x:y:xs)`

over a list, so `x`

and `y`

represent the first and second
value of the list and `xs`

the remaining elements.

Let us see how we can use pattern matching to implement binary tree traversal in different orders. Let's remember first preorder, inorder and postorder traversals:

* Ways to traverse a binary tree: preorder (left: F, B, A, D, C, E, G, I, H) inorder (center: A, B, C, D, E, F, G, H, I) and postorder (right: A, C, E, D, B, H, I, G, F). The black dots indicate at what time of the route each node is chosen*

And that we can implement it like this:

```
data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Show)
preOrder :: Tree a -> [a]
preOrder Empty = []
preOrder (Node n t1 t2) = [n] ++ preOrder t1 ++ preOrder t2
postOrder :: Tree a -> [a]
postOrder Empty = []
postOrder (Node n t1 t2) = postOrder t1 ++ postOrder t2 ++ [n]
inOrder :: Tree a -> [a]
inOrder Empty = []
inOrder (Node n t1 t2) = inOrder t1 ++ [n] ++ inOrder t2
```

The expressions `(Node n t1 t2)`

is where pattern matching takes place.

### Input / output

Consider also a small example of input/output: a program that reads the name
a person says `Hello maca`

if the name ends in `a`

and `Hello maco`

otherwise (maco and maca mean pretty in Catalan :P):

```
main :: IO()
main = do
name <- getLine
putStrLn $
"Hola mac" ++
(if elem (last name) "aA" then "a" else "o") ++ "!"
```

### Product of polynomials with Fast Fourier Transform

Finally, let's see the implementation of polynomial multiplication using the Fast Fourier Transform. The product of polynomials of degree $n$ has a cost of $\mathcal{O}(n^2)$ if we use the trivial algorithm: we multiply each coefficient of the first polynomial by each coefficient of the second polynomial, and then add them as needed, which leads to a quadratic performance. There is a much faster algorithm with a performance of $\mathcal{O}(n\log n)$, which uses the Fast Fourier Transform.

A very good explanation of how this algorithm works and how to implement it can be found here.

Next I show a working implementation, where the FFT is implemented in only 12 lines of code and 10 more lines are used to implement polynomial multiplication.

```
import Data.Complex
fft :: [Complex Double] -> Complex Double -> [Complex Double]
fft [a] _ = [a]
fft a w = zipWith (+) f_even (zipWith (*) ws1 f_odd) ++
zipWith (+) f_even (zipWith (*) ws2 f_odd)
where
-- Take even and odd coefficients of a(x)
a_even = map fst $ filter (even . snd) (zip a [0..])
a_odd = map fst $ filter (odd . snd) (zip a [0..])
-- Compute FFT of a_even(x) and a_odd(x) recursively
f_even = fft a_even (w^2)
f_odd = fft a_odd (w^2)
-- Compute 1st and 2nd half of unity roots (ws2 = - ws1)
ws1 = take (length a `div` 2) (iterate (*w) 1)
ws2 = map negate ws1
-- Multiplication of polynomials: c(x) = a(x) · b(x)
-- * a(x) and b(x) have degree n (power of 2), c(x) has degree 2n
-- Algorithm:
-- 1. Compute f_a = fft(a), f_b = fft(b) .. O(n·logn)
-- 2. Compute product: f_c = f_a · f_c .. O(n)
-- 3. Interpolate c: c = fft^{-1}(f_c) .. O(n·logn)
mult :: [Double] -> [Double] -> [Double]
mult [] _ = []
mult a b = map realPart c
where
n = length a
w = exp (pi * (0 :+ 1) / fromIntegral n)
f_a = fft (map (:+ 0) $ a ++ replicate n 0.0) w
f_b = fft (map (:+ 0) $ b ++ replicate n 0.0) w
f_c = zipWith (*) f_a f_b
c = map (/ (fromIntegral $ 2*n)) $ fft f_c (1/w)
```

To test this program, save it in the file `fft.hs`

, open a Haskell interpreter
`ghci`

and load the program: `:l fft.hs`

. We can multiply polynomials with
`mult [2,1] [3,-2]`

. Because we are working with floating point numbers, we can
see small inaccuracies (eg. instead of `2.0`

, the system can save
`1.9999999999999996`

). That's why we define `round2`

, a function which rounds
numbers to two decimal places. Here are some examples:

```
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Prelude> :l fft.hs
[1 of 1] Compiling Main ( fft.hs, interpreted )
Ok, modules loaded: Main.
*Main> let round2 f = (fromInteger $ round $ f * 100) / 100
*Main> map round2 $ mult [2,1] [3,-2]
[6.0,-1.0,-2.0,0.0]
*Main> map round2 $ mult [2,1,0,0] [3,-2,0,0]
[6.0,-1.0,-2.0,0.0,0.0,0.0,0.0,0.0]
*Main> map round2 $ mult [3.5,-2,6,1] [3.5,-2,6,1]
[12.25,-14.0,46.0,-17.0,32.0,12.0,1.0,0.0]
*Main> map round2 $ mult [1,2,3,4,5,6,7,8] [0,0,0,0,1,0,0,0]
[0.0,0.0,0.0,0.0,1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,0.0,0.0,0.0,0.0]
```