# Comparing Haskell and Python Lists

This comparison applies more generally to functional vs imperative programming languages.

The computational model of functional programming is based on rewriting expressions, just like equational reasoning in high-school algebra.

The computational model of imperative programming is based on modifying memory.

## Lists in functional programming

A list in functional programming is a data type defined by saying that

- the empty list is a list
- if $x$ is some data (of type `a`) and $l$ is some list (of elements of type `a`),
then the pair $(x,l)$ is a list (of elements of type `a`)
- nothing else is a list (of elements of type `a`).

This abstract definition can be actually implemented in Haskell as follows.[^Mylist]

data Mylist a =
Nil |
Cons a (Mylist a)

The first line gives the name `Mylist` to the type we define. The second line corresponds to the first bullet point and makes the empty list known to Haskell under the name `Nil`. The third line implements the second bullet point.

To see that this works we add to the three lines above a suitable definition of the length function

len Nil = 0
len (Cons x l) = (len l) + 1

and save all of it in a file called [`mylists.hs`](). We can then have the following dialogue with Haskell

*Main> :load mylists.hs
*Main> len (Cons 1 (Cons 2 Nil))
2
*Main> len (Cons 1 (Cons 'a' Nil))
<interactive>:7:11: error:

- We see that `len` computes the length of the list `Cons 1 (Cons 'a' Nil)` as expected.
- The error message reflects that all elements of a `Mylist` need to have the same type (denoted by the type variable `a` in the definition).
- Can `len` compute the the length of a list of strings?

Now let us see how Haskell actually evaluates the length of a list. To this end, we do not need to know anything about how Haskell is implemented, we can just do some equational reasoning as in high-school algebra:

len (Cons 'a' (Cons 'b' (Cons 'c' (Cons 'd' Nil)))) =
(len (Cons 'b' (Cons 'c' (Cons 'd' Nil)))) + 1 =
(len (Cons 'b' (Cons 'c' (Cons 'd' Nil)))) + 1 =
...
((((0+1)+1)+1)+1) =
4

- Can you fill in the dots? Make sure that each `=` is justified by one of the equations defining `len`.

## Lists in imperative programming

The idea of lists as contiguous elements in memory that can be addressed by their position (or index) is important. This idea comes in many variations and under various names such as array, vector, arrayList, etc, depending on the particular programming languages.

**Activity:** Explain the advantages of arrays in terms of the memory model of imperative programming languages. On the other hand, what are the advantages of recursively defined lists?

[^Mylist]: In [GHC.Types](https://hackage.haskell.org/package/ghc-prim-0.6.1/docs/src/GHC.Types.html) lists are defined via

data [] a = [] | a : [a]

which is, up to notation, equivalent to

data Mylist a = Nil | Cons a (Mylist a)

The main differences are the name of the type (`Mylist` instead of `[]`), the names of the constructors (`Nil` for `[]` and `Cons` for `:`), as well as `:` being an "infix" operator (inbetween its arguments) and `[]` being an "mixfix" operator (with its argument in the middle).