---
# System prepended metadata

title: 'Haskell: Recursion in Functional Programming'
tags: [programming languages, ' haskell']

---

---
tags: programming languages, haskell
---
# Haskell: Recursion in Functional Programming

(Part of the course *Programming Languages*)

## Introduction

We have learned the basics of Haskell and how to execute recursive programs pen-and-paper. 

The next step is to let the Haskell interpreter do the computations.

In order to make this note more self-contained, I repeat quite some material we have seen already. So feel free to pick the new bits and pieces.


## List as a Recursive Data Type

Lists are the simplest recursive data type.

Lists in Haskell can be **constructed** in several ways. The basic ones are the following
```haskell
     []
```
is the empty list and if `x` is some data and `xs` is a list then
```haskell
    x:xs
```  
is the list that has `x` as its first element and continues with `xs`. We can also write
```haskell
    [3,6,2,1]
```  
as an abbreviation of 
```haskell
    3:(6:(2:(1:[])))
```
where we are allowed to drop the parentheses    
```haskell
    3:6:2:1:[]
```
    
If we want to **deconstruct** a list into its elements we can use built-in functions head and tail which are defined by the equations
```haskell
    head(x:xs) = x
    tail(x:xs) = xs
```
**Warning:**  Haskell has no assignment. `=` reads more like a mathematical equality.     

## Programming by Recursion on Lists

**Example:** Save the following program
```haskell
    len [] = 0
    len (x:xs) = 1 + len xs
```    
in a file called `lists.hs` and run it in a console.[^length] 

[^length]: Haskell has a built in function `length` with the same functionality. But here we want to see how to write it from scratch.

On my machine, I have the following dialogue


    ghci
    Prelude> :load lists.hs
    
and test it with various lists such as in

    *Main> len [1,2,3]
    3


**Exercise:** Implement the factorial function in Haskell. (A solution can be found in [Haskell in 5 steps](https://wiki.haskell.org/Haskell_in_5_steps).)

## Types 

One reason why Haskell will be a powerful tool to implement interpreters is that Haskell is *strongly typed*. We will learn later more about what that means and why this is so powerful. At the moment, this section on types is just needed for general background. 

If your aim is to get started quickly, types can be largely ignored. The reason for this, as we will learn later, is that Haskell has automated *type inference*. This means that even if you do do not specify the types of your Haskell programs, Haskell can (often) infer the types. This is why we choose to ignore types in the remainder of this lecture. 

But types may become visible to you anyway, for example in error messages or because your editor is configured to automatically display types. So it is good to have some rough acquaintance with types. 

I keep this section to a minimum, more information is available in many places, for example at [learnyouahaskell](http://learnyouahaskell.com/types-and-typeclasses). 

In `ghci`, we can use `:t` to ask for the type of a program.

```haskell
Prelude> :t 'a'
'a' :: Char
Prelude> :t "a"
"a" :: [Char]
```

This tells us that `'a'` is a `Char` and that `"a"` is list of `Char`.

Btw, we should be able to write a list containing `'a'` also using the  `[...]`. A good way to learn Haskell is whenever you have a question like to ask the console. So let us try

```haskell
Prelude> "a"==[a]
<interactive> error: Variable not in scope: a :: Char
```

Oops ... sth went wrong. 

**Exercise:** Can you explain the error message? Can you fix the error? (So that we get the expected answer `True`.)

<!--
```haskell
"a"==['a']
True
```
-->

One more experiment about lists:

```haskell
Prelude> list = 'a':'b':'c':[]
```

What is the type of `list` we expect now? 

(Btw, one of the important principles of the scientific method is to **always be explicit about what outcome you expect before performing an experiment.**)

```haskell
Prelude> :t list
list :: [Char]
```

Ok, next we should learn about function types. Let us try a few functions, we have seen before. What is the type of `head`? It is a function that takes a list and returns the first element. Let us see how this is expressed in Haskell:

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

Makes sense, doesn't it? `->` separates input from output. Input is a list of `a`s and output is an `a`. But what does `a` stand for? `a` is a so-called *type variable* and `head` is a *polymorphic function*.

Again, type variables and polymorphism is sth we will hear more about later. For now, let us just say that the use of the type variable `a` allows us to type a function like `head` that works the same whatever the type of the elements of the list is. (This makes sense: All `head` does is to take the first element ... the same algorithm, whether you have a list of integers or a list of characters.)

What types have numbers. There is a potential problem here, for example, the number `2` can be an integer or a fraction or a real number and maybe more. As we said before, Haskell has type inference which allows the programmer to ignore types in many situations. But what if the programmer does not specify the type of, say, `2`?

The answer is *type classes*. A type class is an interface that can be instantiated in various ways. For example there is a type class `Num`. 

```haskell
Prelude> :t 2
2 :: Num p => p
```

`Num p => p` tells us that if `p` is an instance of `Num` then the type of `2` is `p`. The "if-then" in the previous sentence is rendered by Haskell as `=>`. As you can see, it has a different meaning than the `->` in, say, `head :: [a] -> a`.

#### Further Reading

- [Chapter 3: Types and Typeclasses](http://learnyouahaskell.com/types-and-typeclasses) of Learn You a Haskell.


## Exercises

As we said before, you can ignore types for now. The aim for now is to learn how to write recursive functions. We have seen examples `fib` and `len` above. Now try your own. If you need more background I recommend Chapters 2, 3 and 5 of [Learn You a Haskell](http://learnyouahaskell.com/chapters).

**Task 1:** Implement in Haskell the following functions

	select_evens
	select_odds
	member
	append
	revert
	less_equal
    
Examples:

	*Main> select_evens ["a","b","c","d","e"]
	["b","d"]    
	*Main> select_odds ["a","b","c","d","e"]
    ["a",c","e"]
    *Main> member 2 [5,2,6]
    True
    *Main> member 3 [5,2,6]
    False
    *Main> append [1,2] [3,4,5]
    [1,2,3,4,5]
    *Main> revert [1,2,3]
    [3,2,1]
    *Main> less_equal [1,2,3] [2,3,4]
    True
    *Main> less_equal [1,2,3] [2,3,2]
    False
    *Main> 

Remember that Haskell does not have assignment or for-loops. All these exercises can be solved with pattern matching and recursion, just as we did for `fib` and `len`.

(Btw, you can put all functions in the same file.)[^lists.hs]

**Task 2:** Similar to Homework 1 and our example `fib 6`, show the computations taken in one selected example.

## More Haskell exercises (Optional)

**Zipping two lists** 

The function `zipp` should merge two lists taking elements from the lists in turn, very much like a zipper. Example:

    *Main> zipp [1,2,3] [4,5,6,7,8]
    [1,4,2,5,3,6,7,8]
    
Remark: The following should always be true

    zipp (select_odds xs) (select_evens xs) = xs

    
**Merging two lists of integers**

    merge
    merge_sort
    
For `merge_sort` implement an algorithm that does, for example, the following computation:

    [6,5,4,3,2,1,7,8] 
    = [[6],[5],[4],[3],[2],[1],[7],[8]] 
    = [[5,6],[3,4],[1,2],[7,8]] 
    
and then keeps on merging neighbouring lists as follows

    = [[3,4,5,6],[1,2,7,8]] 
    = [[1,2,3,4,5,6,7,8]] 
    
until only one list remains. Explain why this list is always sorted. Benchmark your algorithm. What time complexity does it have?
    
**Summing a list of integers**

    *Main> summ [1,2,3,4]
    10
    *Main> mean [1,2,1]
    1.3333333333333333
    *Main> prod [1,2,3,4]
    24
    *Main> summs [0,1,2] [4,5,6]
    [4,6,8]
    *Main> prods [0,1,2] [4,5,6]
    [0,5,12]

#### Recursion over numbers

The idea is not to use a closed formula (even if there is one), but to practice recursive programming. So defining a function `func` would typically follow the pattern

    func 0 = ...
    func n = ...
    
see also the example of `fib` in the first lecture.

    *Main> triangle_number 4
    10
    *Main> sums_of_squares 3
    14

The examples above can be found at the [Online Encyclopedia of Integer Sequences](https://oeis.org/) under [A000217](https://oeis.org/A000217) and [A000330](https://oeis.org/A000330). 

Why don't you explore and implement some more sequences such as [the number of different RNA structures for sequences of length n.](https://oeis.org/A170941)

## Further Resources

[Haskell in 5 steps](https://wiki.haskell.org/Haskell_in_5_steps)

[Comparing Haskell and Python Lists](https://hackmd.io/@alexhkurz/BkCGLGkXv) ... btw, there is a data structure for efficient indexing in Haskell, see [Haskell Vectors](https://hackage.haskell.org/package/vector), but we will not need this in this course.

The tutorials referenced at [Haskell in 5 steps](https://wiki.haskell.org/Haskell_in_5_steps).

The first two videos of the tutorial [Haskell for Imperative Programmers](https://www.youtube.com/watch?v=Vgu82wiiZ90) cover the material in greater depth ... well worth watching, even if it contains stuff we didn't do (yet).

Wikibooks/Haskell:
- [Truth values](https://en.wikibooks.org/wiki/Haskell/Truth_values)
- [Lists and tuples](https://en.wikibooks.org/wiki/Haskell/Lists_and_tuples)

Gayle Laakmann McDowell explains in [Algorithms: Recursion](https://www.youtube.com/watch?v=KEEKn7Me-ms) recursion as a problem solving technique.

[Recursive image rotation](https://www.youtube.com/watch?v=OXo-uzzD4Js&feature=emb_logo) is a great visual example of recursion. [^leetcode48]  

[^leetcode48]: This is problem [LeetCode 48](https://leetcode.com/problems/rotate-image/) and [Fisher Coder](https://www.youtube.com/channel/UCPL5uAbYQ40HwAdOe4ikI0w) has a good [explanation](https://www.youtube.com/watch?v=gCciKhaK2v8).

## tl;dr

[Fast Sorting with Haskell](https://www.reddit.com/r/haskell/comments/5wkyv4/delazification_of_algorithms/)

[^lists.hs]: [Solution](https://github.com/alexhkurz/programming-languages-2020/blob/master/Answers/lists.hs).