Lists
Tags: functional, haskell
Published: 2019-05-14 20:53:19

---
title: Lists
description: #100DaysOfFP Day 16: Review of Haskell book's 9th chapter
cover_image: https://images.pexels.com/photos/793088/pexels-photo-793088.jpeg?auto=compress&cs=tinysrgb&dpr=2&h=750&w=1260
series: 100 Days Of FP
tags: fp,haskell
published: true
---

> The explicit teaching of thinking is no trivial task, but who said that the teaching of programming is? In our terminology, the more explicitly thinking is taught, the more of a scientist the programmer will become.
> _Edsger Dijkstra_

More catch up :tm:, this time with a previous week's session, [Delft Haskell Study Group #6](https://www.meetup.com/Delft-Haskell-Study-Group/events/260075544/). As always, I quote [the book](http://haskellbook.com/) as a way of recap :book:

## About thinking :thinking:

I'm always adding the quotes the book adds at the cover of each chapter but never mention anything about them. I really liked this one in particular. Programming is all about thinking. The more we learn to think the better programmers we'll be.

## Lists

The list datatype in Haskell is defined like this:

```haskell
data [] a = [] | a : [a]
```

There are a few things to point out there. `[]` Is both the type constructor as well as the data constructor for the empty list. The other constructor (`:`), the infix operator called [_cons_](https://en.wikipedia.org/wiki/Cons), takes a value of type `a` and a list of type `[a]` and evaluates to `[a]`. The data type as a whole is a sum (`|`) but the second constructor (`:`) is a product. What `a : [a]` does is adding `a` to the front of the list.

### Pattern matching :tada:

As I already mentioned pattern matching is one of my favorite features of Haskell. And we can do quite some interesting things by pattern matching on lists.

```haskell
head' :: [a] -> Maybe a
head' []       = Nothing
head' (x : _ ) = Just x

tail' :: [a] -> Maybe [a]
tail' []       = Nothing
tail' (_ : xs) = Just xs
```

I wrote these versions that return the value wrapped in a maybe because `[a]` doesn't guarantee that the list will have values. If we try the [Prelude](http://hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html) version of these functions on empty lists we get and error.

```
λ> head []
*** Exception: Prelude.head: empty list
λ> tail []
*** Exception: Prelude.tail: empty list
```

One thing to mention about our `tail'`. In case of calling it with a list that has one value, it will return `Just []`. I think it's fine, since it reflects what the tail of a list with one element is (`a : []`). But if we'd want to only return lists with elements we could extend it like so.

```haskell
tail' :: [a] -> Maybe [a]
tail' []       = Nothing
tail' (_ : []) = Nothing
tail' (_ : xs) = Just xs
```

### Sweet sweet syntactic sugar :lollipop:

To write a list of four elements using the constructor we'd have to do use the cons operator 4 times.

```haskell
(1 : 2 : 3 : 4 : [])
```

Luckily Haskell provides some syntactic sugar to make it easier, which resembles the one in many other languages.

```haskell
[1, 2, 3, 4]
```

### Ranges

Another nice thing to work with lists that Haskell provides is the ranges syntax.

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

λ> [2, 4..10]
[2,4,6,8,10]

λ> [1..]
[1,2,3,4,5,6,7,8,9,10,11,12 ...] -- continues infinitely


λ> [1, 5..]
[1,5,9,13,17,21,25,29,33,37,41,45 ...] -- continues infinitely
```

Which are equivalent to.

```
λ> enumFromTo 1 10
[1,2,3,4,5,6,7,8,9,10]

λ> enumFromThenTo 2 4 10
[2,4,6,8,10]

λ> enumFrom 1
[1,2,3,4,5,6,7,8,9,10,11,12 ...] -- continues infinitely


λ> enumFromThen 1 5
[1,5,9,13,17,21,25,29,33,37,41,45 ...] -- continues infinitely
```

All of these functions require the type being ranged, in other words an `Enum` type class.

```haskell
enumFromTo :: Enum a => a -> a -> [a]
enumFromThenTo :: Enum a => a -> a -> a -> [a]

enumFrom :: Enum a => a -> [a]
enumFromThen :: Enum a => a -> a -> [a]
```

## List comprehensions


> List comprehensions are a means of generating a new list from a list or lists. They come directly from the concept of set comprehensions in mathematics, including similar syntax. They must have at least one list, called the generator, that gives the input for the comprehension, that is, provides the set of items from which the new list will be constructed. They may have conditions to determine which elements are drawn from the list and/or functions applied to those elements.

Coming from a non-mathematical background (JS, PHP, C++, Go, .etc) this was one of the really new things for me.

```haskell
[ x^2 | x <- [1..10]]
```

Give the definition we can guess that we are building a list of all the square numbers from the list of `[1..10]`. Or at least I'd guess that because I already read the chapter :joy:


```
λ> [ x^2 | x <- [1..10]]
[1,4,9,16,25,36,49,64,81,100]
```

We can add predicates to ignore certain items. The ones the predicate returns `False` for, naturally. For example, we can decide to keep only the numbers divisible by 3.

```
λ> [x^2 | x <- [1..10], rem x 3 == 0]
[9,36,81]
```

List comprehensions can have multiple generators.

```
λ> [x^y | x <- [1..5], y <- [2, 3]]
[1,1,4,8,9,27,16,64,25,125]

λ> [(x, y) | x <- [1..5], y <- [2, 3]]
[(1,2),(1,3),(2,2),(2,3),(3,2),(3,3),(4,2),(4,3),(5,2),(5,3)]
```

Notice that the rightmost generator is exhausted first, then the second one and so on.

### Spines and nonstrict evaluation

Lists are a recursive series of cons cells `a : [a]` terminated by the empty list `[]`. Now, it'd be great to find a way to visualize that.

In Haskell we say that some data structures (lists, sequences and trees) have a _spine_, the connective structure that ties the collection of values together. In lists it's the recursive cons (`:`) operators.

```
1 : 2 : 3 : []

or

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

There's a problem with this `1 : 2 : 3 : []` representation, it makes it look like `1` exists before the _cons cell_ but actually it contains the two values. Looking more like the following.

```
  :
 / \
1   :
   / \
  2   :
     / \
    3  []
```

> Because of this and the way nonstrict evaluation works, you can evaluate cons cells independently of what they contain. It is possible to evaluate only the spine of the list without evaluating individual values. It is also possible to evaluate only part of the spine of a list and not the rest of it.

Evaluation of a list goes down the spine, while construction goes up. But nothing is evaluated until it is needed to be.

As we said, the spine is the recursive series of cons operators (`:`). And in here the `_` would be the non evaluated values.

```
 : <------|
/ \       |
_  : <----| This is the "spine"
  / \     |
 _   : <--|
    / \
   _  []
```

Using `:sprint` in GHCi we can see what is evaluated and what isn't.

```
λ> ls = [1..5] :: [Int]
λ> :sprint ls
ls = _

```

So, `ls` hasn't been evaluated yet (as `_` indicates).

```
λ> take 1 ls
[1]
λ> :sprint ls
ls = 1 : _
```

Now we evaluated the first cons cell and it's first value. Let's take 2 values.

```
λ> take 2 ls
[1, 2]
λ> :sprint ls
ls = 1 : 2 : _
```

We can continue like that until the end. We can also evaluate the whole spine with `length`.

```
λ> length ls
5
λ> :sprint ls
ls = [1,2,3,4,5]
```

Wait but I said the spine only :thinking: This is some quirk of GHCi. But we can prove it's only the spine by checking a list of bottom ⊥ (i.e. `undefined`).

```
λ> undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err
  undefined, called at <interactive>:1:1 in interactive:Ghci1
```

As we can see it throws an exception when evaluated. But ...

```
λ> ls = [undefined, undefined]
λ> :sprint ls
ls = _
λ> length ls
2
λ> :sprint ls
ls = [_,_]
```

As we can see Haskell only evaluates what it needs and nothing else. The book extends on this a bit more and explains the concepts of _normal form_ and _weak head normal form_. But I'll get back to those in more depth in the chapter of nonstrictness.

### Transforming lists of values

We can use `map` or `fmap` to transform a list of values, by applying a function to each element and then returning the new list.

```haskell
map  ::              (a -> b) -> [a] -> [b]
fmap :: Functor f => (a -> b) -> f a -> f b
```

`fmap` is the generalized version of `map` that works for Functors. List is one of them. More on Functors in a following chapter.

```
λ> fmap (+1) [1, 2, 3, 4]
[2,3,4,5]
```

This is how it's defined in `base`.


```haskell
map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (a:as) = f a : map f as
```

By adding some parens to the type definition we can make it more explicit what map really allows us to do. Basically lifting our function `a -> b` to work in lists.

```
(a -> b) -> ([a] -> [b])

( a  ->  b )
([a] -> [b])
```

### Filtering lists of values

`map` is not the only function we can use on lists. We can also filter certain values out of a list when they don't fulfill a predicate.

```
λ> even 10
True
λ> even 9
False
λ> filter even [1..10]
[2,4,6,8,10]
```

Here's how `filter` is defined.

```haskell
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter pred (x:xs)
  | pred x    = x : filter pred xs
  | otherwise = filter pred xs
```

### Zipping lists


> Zipping lists together is a means of combining values from multiple lists into a single list.

```
λ> :t zip
zip :: [a] -> [b] -> [(a, b)]
λ> zip "abc" "cde"
[('a','c'),('b','d'),('c','e')]
λ> zip "abc" "cdefghi"
[('a','c'),('b','d'),('c','e')]
λ> zip "abcdefghi" "jkl"
[('a','j'),('b','k'),('c','l')]
```

Note that `zip` returns the length of the shortests list.

We can also `unzip` lists.

```
λ> :t unzip
unzip :: [(a, b)] -> ([a], [b])
λ> unzip [(1,'a'), (2, 'b'), (3, 'c')]
([1,2,3],"abc")
```

There's also `zipWith` to combine two lists.

```
λ> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
λ> zipWith (+) [1,2,3] [1,2,3]
[2,4,6]
λ> zipWith (+) [1,2,3] [1,2,3]
[2,4,6]
λ> zipWith (,) [1,2,3] [1,2,3]
[(1,1),(2,2),(3,3)]
```

## Conclusion

With lists we start to see the declarative patterns of functional programming. And how the same functions we can use for plain values can be used for lists as well with higher order functions like `map`, `filter` and `zip`.

Thanks to Haskell's laziness (nonstrict evaluation) it will only evaluate what it needs and no more.

```
λ> ls = [1,2,3,4,5,6,7,undefined]
λ> filter even ls
[2,4,6*** Exception: Prelude.undefined
λ> take 2 $ zip "abcdefg" $ map (*2) $ filter even ls
[('a',4),('b',8)]
```

Although it's clear in this example, it has many more implications that I'm yet to understand or even discover and I look forward to learn about that.