Free Thinking Functionally with Haskell by Richard Bird

2
     
    bound :: Float -> Interval
    bound x = (0,until above (*2) 1)
    where above n = x `lt` (n*n)
    The functions `leq` and `lt` were defined in Section 3.3 . Note the parentheses in the expressions (p*p) `leq` x and x `lt` (n*n) . We didn’t state an order of association for `leq` and `lt` , so without parentheses these two expressionswould have been interpreted as the ill-formed expressions p * (p `leq` x) and (x `lt` n) * n . (I made just this mistake when first typing in the solution.) Answer to Exercise F
    A better approximation tothan either y or x / y is ( y + x / y )/2. The relative-error test is the more sensible one, and the program is
    sqrt :: Float -> Float
    sqrt x = until goodenough improve x
    where goodenough y = abs (y*y-x) < eps*x
    improve y = (y+x/y)/2
    eps = 0.000001
    Answer to Exercise G
    It is sufficient to define (<) :
    instance Ord Nat where
    Zero < Zero = False Zero < Succ n = True Succ m < Zero = False Succ m < Succ n = (m < n)
    Now we can define
    divMod :: Nat -> Nat -> (Nat,Nat)
    divMod x y = if x < y then (Zero,x)
    else (Succ q,r)
    where (q,r) = divMod (x-y) y
3.7 Chapter notes
    The primary source book for computer arithmetic is The Art of Computer Programming, Volume 2: Semi-numerical Algorithms (Addison-Wesley, 1998) by Don Knuth. The arithmetic of floors and other simple numerical functions is studied in depth in Concrete Mathematics (Addison-Wesley, 1989) by Don Knuth, Ronald Graham and Oren Patashnik.

Chapter 4
Lists
    Lists are the workhorses of functional programming. They can be used to fetch and carry data from one function to another; they can be taken apart, rearranged and combined with other lists to make new lists. Lists of numbers can be summed and multiplied; lists of characters can be read and printed; and so on. The list of useful operations on lists is a long one. This chapter describes some of the operations that occur most frequently, though one particularly important class will be introduced only in Chapter 6 .
4.1 List notation
    As we have seen, the type [a] denotes lists of elements of type a . The empty list is denoted by [] . We can have lists over any type but we cannot mix different types in the same list. As examples,
[undefined,undefined]
::
[a]
[sin,cos,tan]
::
Floating a => [a -> a]
[[1,2,3],[4,5]]
::
Num a => [[a]]
["tea","for",2]

not valid
    List notation, such as [1,2,3] , is in fact an abbreviation for a more basic form 1:2:3:[]
    The operator (:) :: a -> [a] -> [a] , pronounced ‘cons’, is a constructor for lists. It associates to the right so there is no need for parentheses in the above expression. It has no associated definition, which is why it is a constructor. In other words, there are no rules for simplifying an expression such as 1:2:[] . Theoperator (:) is non-strict in both arguments – more precisely, it is non-strict and returns a non-strict function. The expression undefined : undefined
    may not be very interesting, but we do know it is not the empty list. In fact, that is the only thing we do know about it. Note that the two occurrences of undefined have different types in this expression.
    The empty list [] is also a constructor. Lists can be introduced as a Haskell data type with the declaration data List a = Nil | Cons a (List a)
    The only difference is that List a is written [a] , Nil is written [] and Cons is written (:) .
    According to this declaration, every list of type [a] takes one of three forms:
The undefined list undefined :: [a] ;
The empty list [] :: [a] ;
A list of the form x:xs where x :: a and xs :: [a] .
    As a result there are three kinds of list:
A finite list, which is built from (:) and [] ; for example, 1:2:3:[]
A partial list, which is built from (:) and undefined ; for example, the list filter (<4) [1..] is the partial list 1:2:3:undefined . We know there is no integer after 3 that is less than 4, but Haskell is an evaluator, not a theorem prover, so it ploughs away without success looking for more answers.
An infinite