1.3 sequences (lists)

To represent something as a list of a certain type, we write $[T]$ for some type $T$ . This itself is a type, so one can easily write $[[T ∥ T]]$ , which is useful for problems on 2D graphs and such.

Haskell supports list comprehension, which looks more like set notation. We can look at the base functions for managing lists to understand how exactly this works:

> map :: (a -> b) -> [a] -> [b]
> (map f) xs = [ f x | x <- xs]

Reading this out, map sends a function of type $a \to b$ to its corresponding list function of type $[a] \to [b] .$ To see what it more clearly does on a list, we have $f (x)$ , sending the original value of $x$ to its new one for all $x \leftarrow x s$ , which means $x$ in $x s$ . Everything on the left of the bar is the expression, everything on the right is the condition. Let's go over another example.

filter :: (a -> Bool) -> [a] -> [a]
(filter p) xs = [ f x | x <- xs, p x]

This is almost the exact same, but here $p$ is an indicator function which is being used to check a condition, as the expression $p (x)$ is doing on the right hand side of the bar. For the final example, we'll have multiple variables instantiated in the right hand side.

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <-xs]

Note the order of instantiation. Haskell reads it from left to right, and as such needs $x s$ to be defined before it can draw $x$ from it.

As a nice programming type of thing, elements of type String are just lists of Char types, meaning we can do each of these list comprehension functions on a String.