Saturday, Dec 12, 2020

List comprehensions are a powerful idiom to generate new lists from old ones.

## Syntax

[e | gnr1,.., grd1,..]


So we wrap inside square brackets an expression that will generate new list followed by | and then one or more generators and optionally one or more guards. Generators generate the elements of the older list. For example, x <- [1..10] generates a list of integers 1 through 10 and assign these to x one by one. x then can be used in e. Guards help to filter out elements that we don't want in the new list. As a concrete example, the expression:

[x | x <- [1..10], even x]


will generate the list

[2, 4, 6, 8, 10]


and can be read as get me a list of all even numbers drawn from list [1..10]

## More examples

### Length of a list

length :: [a] -> Int
length xs = sum [1 | _ <- xs]


So we can do pattern matching on generators.

### Return number of upper case letters in a string

uppers :: String -> Int
uppers xs = length [x | x <- xs, Data.Char.isUpper x]


### Pairwise sum of two lists of numbers

pairSum :: Num a => [a] -> [a] -> [a]
pairSum xs ys = [x+y | (x,y) <- zip xs ys]


Here the library function zip is used to create list of pairs that are pattern-matched in the generator. Components of pairs are then added to create the final list.

### Scalar product of two lists of integers

Scalar product is defined as: $$\sum_{i=0}^{n-1} (xs_i * ys_i)$$

scalarproduct :: [Int] -> [Int] -> Int
scalarproduct xs ys = sum [a*b | (a,b) <- zip xs ys]


Notice how the formula nicely translates to code.

### Concat

concat is a library function that flattens a list of list. We can write that using list comprehension as

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


Here we are using two generators. For multiple generators, we have to think each subsequent generator nested a level deeper than the previous one, like nested for loops in imperative programming. So here, xs is drawn from the input list, and thus each xs is a list. For each xs, second generator (x <- xs) draws an element to build a new list.

### Pythagorean triples

A triple $(x,y,z)$ of positive integers is Pythagorean if it satisfies the equation $x^2+y^2 = z^2$.

pyths :: Int -> [(Int, Int, Int)]
pyths n = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n],
x^2 + y^2 == z^2]

*Main> pyths 10
[(3,4,5),(4,3,5),(6,8,10),(8,6,10)]