# Haskell: Lists (incomplete)

(under construction)

In this session we repeat what we have done in Python in a functional programming language. We have seen a bit of Haskell before [](). We have also seen that recursive programming was easier and more elegant in Haskell than in Python.

As we will see later, this is due to the fact that Haskell as a functional programming language is based on a different model of computation than the imperative language Python. But before I can explain this, we need to get some first-hand experience.

I put some notes together on [installing Haskell](https://hackmd.io/@alexhkurz/Hk86XnCzD).

Lists in Haskell look superficially like lists in Python, for example the following are lists.

[]
[1]
[1,2]
[5,3,6,2]

## Recursion over Lists

But they are implemented in a very different way. In Python, elements of a list can be accessed by knowing their index. In Haskell, lists are what is sometimes called *linked lists*, that is, you can access elements only by successively going from the first to the last element. If the list is long, accessing the first element is fast and accessing the last element is slow.

To see how to access the elements of a list in Haskell, look at the following dialogue.

*Main> l = [4,3,2,1]
*Main> head l
4
*Main> tail l
[3,2,1]
*Main> head (tail l)
3
*Main> tail (tail l)
[2,1]
*Main> head (tail (tail l))
2
*Main>

**Exercise:** Write an expression that extracts `1` from `l`.

To compute the length of a list we can define

*Main> len l = if l == [] then 0 else (len (tail l)) + 1

**Exercise:** Test the above program.

We notice that the Haskell is defined recursively, not iteratively.

**Activity:** Explain the above program.

Before we continue, we should rewrite the program above in a more Haskellian way, using pattern matching and case distinction instead of `==` and `if-then-else`. Since multi-line programs are a bit awkward to type in the console, we save the following in a file [`length.hs`]() and then load it in the console with `:load length.hs`.

len [] = 0
len (x:xs) = (len xs) + 1

The notation `x:xs` denotes a list `xs` to which `x` was appended at the front. We will learn more about this in the next subsection.

**Exercise:** Test the above program.

**Activity:** Explain the above program

## Constructing Lists

In Haskell, we typically construct lists from the empty list

[]

by adding elements in front using the `:` notation as in

x:xs

which is the list that has `x` as its first element and continues with `xs`. In a sense this is the only way to construct lists. For example,

[3,6,2,1]

is as an abbreviation of

3:(6:(2:(1:[])))

where we are allowed to drop the parentheses

3:6:2:1:[]

## Comparing Haskell and Python Lists

I put [Comparing Haskell and Python Lists](https://hackmd.io/@alexhkurz/BkCGLGkXv) at a separate location. Can be skipped for now.

## Examples

... tbc ...