Free Thinking Functionally with Haskell by Richard Bird Page A

list, which is built from (:) alone; for example, [1..] is the infinite list of the nonnegative integers.
    All three kinds of list arise in everyday programming. Chapter 9 is devoted to exploring the world of infinite lists and their uses. For example, the prelude function iterate returns an infinite list:
    iterate :: (a -> a) -> a -> [a]
    iterate f x = x:iterate f (f x)
    In particular, iterate (+1) 1 is an infinite list of the positive integers, a value we can also write as [1..] (see the following section).
    As another example,
    head (filter perfect [1..])
    where perfect n = (n == sum (divisors n))
    returns the first perfect number, namely 6, even though nobody currently knows whether filter perfect [1..] is an infinite or partial list.
    Finally, we can define
    until p f = head . filter p . iterate f
    The function until was used to compute floors in the previous chapter. As this example demonstrates, functions that seem basic in programming are often composed of even simpler functions. A bit like protons and quarks.
4.2 Enumerations
    Haskell provides useful notation for enumerating lists of integers. When m and n are integers we can write
[m..n]
for the list [ m , m +1, . . . , n ]
[m..]
for the infinite list [ m , m +1, m +2, . . .]
[m,n..p]
for the list [ m , m +( n − m ), m +2( n − m ), . . . , p ]
[m,n..]
for the infinite list [ m , m +( n − m ), m +2( n − m ), . . .]
    The first two notations crop up frequently in practice, the second two less so. As examples, ghci> [0,2..11]
    [0,2,4,6,8,10]
    ghci> [1,3..]
    [1,3,5,7,9,11 {Interrupted}
    In the first example the enumeration stops at 10 because 11 isn’t even. In the second example we quickly interrupted the evaluation of an infinite list.
    As a matter of fact, enumerations are not restricted to integers, but to members of yet another type class Enum . We won’t elaborate more on this class, except to say that Char is also a member: ghci> ['a'..'z']
    "abcdefghijklmnopqrstuvwxyz"
4.3 List comprehensions
    Haskell provides another useful and very attractive piece of notation, called list comprehensions , for constructing lists out of other lists. We illustrate with a few examples: ghci> [x*x | x <- [1..5]]
    [1,4,9,16,25]
    ghci> [x*x | x <- [1..5], isPrime x]
    [4,9,25]
    ghci> [(i,j) | i <- [1..5], even i, j <- [i..5]]
    [(2,2),(2,3),(2,4),(2,5),(4,4),(4,5)]
    ghci> [x | xs <- [[(3,4)],[(5,4),(3,2)]], (3,x) <- xs]
    [4,2]
    Here is another example. Suppose we wanted to generate all Pythagorean triads in a given range. These are triples of numbers ( x , y , z ) such that x 2 + y 2 = z 2 and 1 ≤ x , y , z ≤ n for some given n . We can define
    triads :: Int -> [(Int,Int,Int)]
    triads n = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n], x*x+y*y==z*z]
    Hence
    ghci> triads 15
    [(3,4,5),(4,3,5),(5,12,13),(6,8,10), (8,6,10),(9,12,15),(12,5,13),(12,9,15)]
    That’s probably not what we want: each essentially distinct triad is generated in two different ways. Moreover, the list contains redundant triads consisting of multiples of basic triads. To improve the definition of triad we can restrict x and y so that x < y and x and y are coprime, meaning they have no divisors in common. As mathematicians we know that 2 x 2 cannot be the square of an integer, so the first restriction is valid. The divisors of a number can be computed by divisors x = [d | d <- [2..x-1], x `mod` d == 0]
    Hence
    coprime x y = disjoint (divisors x) (divisors y)
    We will leave the definition of disjoint as an exercise.
    That means we can define
    triads n = [(x,y,z) | x <- [1..n], y <- [x+1..n],
    coprime x y,
    z <- [y+1..n], x*x+y*y==z*z]
    This definition is better than before, but let us try to make it a little faster, mainly to illustrate an important point. Since 2 x 2 < x 2 + y 2 = z 2 ≤ n 2 we see thatSoThat suggests we can write triads n = [(x,y,z) | x <- [1..m], y <- [x+1..n],
    coprime x y,
    z <- [y+1..n], x*x+y*y==z*z]
    where m = floor (n / sqrt 2)
    But the expression for m is incorrect: n is an