Read Online Thinking Functionally with Haskell by Richard Bird - Free Book Online

).
    Secondly, why have we used `leq` when the alternative (<=) seems perfectly adequate? The answer is that (<=) has the type (<=) :: Num a => a -> a -> Bool
    In particular the two arguments of (<=) have to have the same type. But we want leq :: Integer -> Float -> Bool
    and the two arguments have different numeric types. We therefore need to convert integers to floats using fromInteger . Appreciation of the need for conversion functions in some situations is one of the key points to understand about Haskell arithmetic.
    Finally, note that (`leq` x) is not the same as (leq x) :
    (leq x) y = leq x y
    (`leq` x) y = y `leq` x = leq y x
    It is easy to make this mistake.
    If you don’t like the subsidiary definition, you can always write
    floor x = until ((<=x) . fromInteger) (subtract 1) (-1) In this version we have inlined the definition of (`leq` x) .
    We still have to deal with the case x ≥ 0. In this case we have to look for the first integer n such that x < n +1. We can do this by finding the first integer n such that x < n and subtracting 1 from the answer. That leads to
    floor x = until (x `lt` ) (+1) 1 - 1
    where x `lt` n = x < fromInteger n
    Putting the two pieces together, we obtain
    floor x = if x < 0
    then until (`leq` x) (subtract 1) (-1)
    else until (x `lt`) (+1) 1 - 1
    (Question: why do we not have to write x < fromInteger 0 in the first line?) The real problem with this definition, apart from the general ugliness of a case distinction and the asymmetry of the two cases, is that it is very slow: it takes about | x | steps (| x | is the mathematician’s way of writing abs x ) to deliver the result.
    Binary search
    A better method for computing floor is to first find integers m and n such that m ≤ x < n and then shrink the interval ( m , n ) to a unit interval (one with m +1 = n ) that contains x . Then the left-hand bound of the interval can be returned as the result. That leads to
    floor :: Float -> Integer
    floor x = fst (until unit (shrink x) (bound x))
    where unit (m,n) = (m+1 == n)
    The value bound x is some pair ( m , n ) of integers such that m ≤ x < n . If ( m , n ) is not a unit interval, then shrink x (m,n) returns a new interval of strictly smaller size that still bounds x .
    Let us first consider how to shrink a non-unit interval ( m , n ) containing x , so m ≤ x < n . Suppose p is any integer that satisfies m < p < n . Such a p exists since ( m , n ) is not a unit interval. Then we can define
    type Interval = (Integer,Integer)
     
    shrink :: Float -> Interval -> Interval
     
    shrink x (m,n) = if p `leq` x then (p,n) else (m,p) where p = choose (m,n)
    How should we define choose ?
    Two possible choices are choose (m,n) = m+1 or choose (m,n) = n-1 for both reduce the size of an interval. But a better choice is
    choose :: Interval -> Integer
    choose (m,n) = (m+n) `div` 2
    With this choice the size of the interval is halved at each step rather than reduced by 1.
    However, we need to check that m < ( m + n ) div 2 < n in the case m + 1 ≠ n . The reasoning is: m < ( m + n ) div 2 < n
    ≡ {ordering on integers}
    m + 1 ≤ ( m + n ) div 2 < n
    ≡ {since ( m + n ) div 2 = ⌊( m + n )/2⌋}
    m + 1 ≤ ( m + n )/2 < n
    ≡ {arithmetic}
    m + 2 ≤ n ∧ m < n
    ≡ {arithmetic}
    m + 1 < n
    Finally, how should we define bound ? We can start off by defining
    bound :: Float -> Interval
    bound x = (lower x, upper x)
    The value lower x is some integer less than or equal to x , and upper x some integer greater than x . Instead of using linear search to discover these values, it is better to use
    lower :: Float -> Integer
    lower x = until (`leq` x) (*2) (-1)
     
    upper :: Float -> Integer
    upper x = until (x `lt`) (*2) 1
    For a fast version of bound it is better to double at each step rather than increase or decrease by 1. For example, with x = 17.3 it takes only seven comparisons to compute the surrounding interval (−1, 32), which is then reduced to (17, 18) in a further five steps. In fact, evaluating