In mathematics, the comprehension notation can be used to construct new sets from old sets.
$ \{x^2 | X \in \{1...5\}\} $
The set {1,4,9,16,25} of all numbers $x^2$ such that x is an element of the set {1...5}.
In Haskell, a similar comprehension notation can be used to construct new lists from old lists
$ [X^2 | x \leftarrow [1..5]] $
The list [1,4,9,16,25] of all numbers x^2 such that x is an element of the list [1..5].
[(x,y) | x <- [1,2,3], y <- [4,5]]
[(x,y) | y <- [4,5], x <- [1,2,3]]
Multiple generators are like nested loops, with later generators as more deeply nested loops whose variables change value more frequently
For example:
[(x, y) | y <- [4,5], x <- [1,2,3]]
x $\leftarrow$ [1,2,3] is the last generator, so the value of the x component of each pair changes most frequently
Later generators can depend on the variables that are introduced by earlier generators.
[(x, y) | x <- [1..3], y <- [x..3]]
The list [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)] of all pairs of number (x,y) such that x,y are elements of the list [1..3] and $y \geq x$
Using a dependant generator we can define the library function that concatenates a list of lists:
concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]
concat [[1,2,3], [4,5], [6]]
List comprehensions can use guards to restrict the values produced by earlier generators
[x | x <- [1..10], even x]
The list [2,4,6,8,10] of all numbers x such that x is an element of the list [1..10] and x is even
Using a guard we can define a function that maps a positive integer to its list of factors:
factors :: Int -> [Int]
factors n =
[x | x <- [1..n], n `mod` x == 0]
factors 15
A postive integer is prime if its only factors are 1 and itself. Hence, using factors we can define a function that decides if a number is prime:
prime :: Int -> Bool
prime n = factors n == [1,n]
prime 7
prime 15
Using a guard we can now define a function that returns the list of all primes up to a given limit:
primes :: Int -> [Int]
primes n = [x | x <- [1..n], prime x]
-- notice how you can get the same results
-- even if you do primes n = [x | x <- [2..n], prime x]
-- because we know 1 is not a prime and we do not have to always check for that
primes 40
A useful library function is zip, which maps two lists to a list of pairs of their corresponding elements.
zip :: [a] -> [b] -> [(a,b)]
zip ['a', 'b', 'c'] [1,2,3,4]
Using zip we can define a function returns the list of all pairs of adjacent elements from a list:
pairs :: [a] -> [(a,a)]
pairs xs = zip xs (tail xs)
pairs [1,2,3,4,5]
Using pairs we can define a function that decides if the elements in a list are sorted:
sorted :: Ord a => [a] -> Bool
sorted xs = and [x <= y | (x,y) <- pairs xs]
sorted [1,2,3,4]
sorted [1,2,45,3,7]
Using zip we can define a function that returns the list of all position of a value in a list:
positions :: Eq a => a -> [a] -> [Int]
positions x xs =
[i | (x', i) <- zip xs [0..], x == x']
positions 0 [1,0,0,1,0,1,1,0]
A string is a sequence of characters enclosed in double quotes. Internally, however, strings are represented as lists of characters.
"abc" :: String
Means ['a','b','c'] :: Char
Because strings are just special kinds of lists, any polymorphic function that operates on lists can also be applied to strings. For example:
length "abcde"
take 3 "abcde"
zip "abc" [1,2,3,4]
Similarly, list comprehensions can also be used to define functions on strings, such as counting how many times a character occurs in a string:
count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x' == x]
count 's' "Mississippi"
pyths :: Int -> [(Int, Int, Int)]
That maps an integer n to all such triples with components in [1..n].
pyths :: Int -> [(Int, Int, Int)]
pyths x = [(x',y,z) | x' <- [1..x], y <- [1..x], z <- [1..x], x'^2 + y^2 == z^2]
pyths 5
perfects :: Int -> [Int]
perfects :: Int -> [Int]
perfects x = [x' | x' <- [1..x], sum (factors x') - x' == x']
perfects 500
$ \sum ^{n-1}_{i=0} (xs_i * ys_i) $
Using a list comprehension, define a function that returns the scalar product of two lists.
scalarproduct :: [Int] -> [Int] -> Int
scalarproduct xs ys = sum [fst xys * snd xys | xys <- zip xs ys]
scalarproduct [1,2,3] [1,2,3]