Free Thinking Functionally with Haskell by Richard Bird Page B

Int and we cannot divide integers. We need an explicit conversion function, and the one to use is fromIntegral (not fromInteger because n is an Int not an Integer ). We need to replace the definition of m by m = floor (fromIntegral n / sqrt 2) . Once again we have to be careful about what kinds of number we are dealing with and aware of the available conversion functions between them.
    List comprehensions can be used to define some common functions on lists. For example,
    map f xs = [f x | x <- xs]
    filter p xs = [x | x <- xs, p x]
    concat xss = [x | xs <- xss, x <- xs]
    Actually, in Haskell it is the other way around: list comprehensions are translated into equivalent definitions in terms of map , and concat . The translation rules are:
    [e |True] = [e]
    [e | q] = [e | q, True]
    [e | b, Q] = if b then [e | Q] else []
    [e | p <- xs, Q] = let ok p = [e | Q]
    ok _ = []
    in concat (map ok xs)
    The definition of ok in the fourth rule uses a don’t care pattern, also called a wild card . The p in the fourth rule is a pattern, and the definition of ok says that the empty list is returned on any argument that doesn’t match the pattern p .
    Another useful rule is
    [e | Q1, Q2] = concat [[e | Q2] | Q1]
4.4 Some basic operations
    We can define functions over lists by pattern matching. For example,
    null :: [a] -> Bool
    null [] = True
    null (x:xs) = False
    The patterns [] and x:xs are disjoint and exhaustive, so we can write the two equations for null in either order. The function null is strict because Haskell has to know which equation to apply and that requires evaluation of the argument, at least to the extent of discovering whether it is the empty list or not. (A question: why not simply define null = (==[]) ?) We could also have written
    null [] = True
    null _ = False
    This definition uses a don’t care pattern.
    Here are two other definitions using pattern matching:
    head :: [a] -> a
    head (x:xs) = x
     
    tail :: [a] -> [a]
    tail (x:xs) = xs
    There is no equation for the pattern [] , so Haskell reports an error if we try to evaluate head [] or tail [] .
    We can use [x] as shorthand for x:[] in a pattern:
    last :: [a] -> a
    last [x] = x
    last (x:y:ys) = last (y:ys)
    The first equation has a pattern that matches a singleton list; the second has a pattern that matches a list that contains at least two elements. The standard prelude definition of last is slightly different:
    last [x] = x
    last (_:xs) = last xs
    This definition uses a don’t care pattern. The two equations have to be written in this order because x:[] matches both patterns.
4.5 Concatenation
    Here is the definition of (++) , the concatenation operation:
    (++) :: [a] -> [a] -> [a]
    [] ++ ys = ys
    (x:xs) ++ ys = x:(xs ++ ys)
    The definition uses pattern matching on the first argument but not on the second. The second equation for (++) is very succinct and requires some thought, but once you have got it, you have understood a lot about how lists work in functional programming. Here is a simple evaluation sequence:
    [1,2] ++ [3,4,5]
    = {notation}
    (1:(2:[])) ++ (3:(4:(5:[])))
    = {second equation for ++ }
    1:((2:[]) ++ (3:(4:(5:[]))))
    = {and again}
    1:(2:([] ++ (3:(4:(5:[])))))
    = {first equation for ++ }
    1:(2:(3:(4:(5:[]))))
    = {notation}
    [1,2,3,4,5]
    As this example suggests, the cost of evaluating xs++ys is proportional to the length of xs , where
    length :: [a] -> Int
    length [] = 0
    length (x:xs) = 1 + length xs
    Note also that
    undefined ++ [1,2] = undefined
    [1,2] ++ undefined = 1:2:undefined
    We know nothing about the first list, but we do know that the second list begins with 1 followed by 2 .
    Concatenation is an associative operation. Thus
    (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
    for all lists xs , ys and zs . We will see how to prove assertions like these in Chapter 6 .
4.6 concat , map and filter
    Three very useful list operations that we have met already are concat , map and filter . Here are their definitions using pattern matching:
    concat :: [[a]] ->