Roger, I have only the first edition at hand so I don't have the big picture of what's going on. My guess is that based on the year of publication (1998) of the 2nd edition, Bird was writing at a time when the Num typeclass hierarchy was still in flux and simply wasn't what it is today. Some comments:

The type of 0 is ambiguous, it could be an Integer or it could be a Double. This ambiguity can be seen by checking its type using WinGHCi:

:type 0 0 :: Num a => a"

Rather than ambiguous, it's better to say that 0 is polymorphic. Or that it's a Num-constrained expression. The definitive meaning of ambiguous is whatever the type checker reports as such. ;)

The datatype Double falls within the class Fractional.

Better to say: there is an instance of Double for the class Fractional. The idea of "falling" suggests it's all forced upon the language by the Powers That Be. It's not. There's a declaration for the instance in the prelude. And the prelude can be suppressed.

Fundamental rule of Haskell: you cannot compare an Integer against a Double, you can only compare a Double against a Double.

You didn't quite ask it this way, but let me treat it as a question: Is it possible to create a typeclass with a method compare that takes 2 independently varying types? You're correct: No, it can't be done if you restrict yourself to Haskell98. However, multi-parameter typeclasses are extremely well-supported and widely used both depth- (historically) and breadth-wise (non-GHC).

Here is the signature for floor: floor :: (Fractional a, Ord a, Real c) => a -> c Read as: Invoke function floor with a Fractional (Double) value and it will return a Real (Integer) value.

Better to read as "floor takes a Fractional and Ord-constrained input and produces a Real-constrained output." Why does this help Haskell learners? Because writing the following is plenty common: floor :: Fractional a -> Real c or sequence :: [Monad a] -> Monad [a] Must. Keep. Types. And. Type classes. Distinct. That said, awareness of the importance of speaking out code is a strong sign of success in learning the language. In due course those combinator-laden expressions won't seem such a dense fog of arcane symbols. Really impressed at your making notes and publishing them. I look forward to more of your tutorials! -- Kim-Ee On Sun, Nov 4, 2012 at 4:40 PM, Costello, Roger L. wrote:

Hi Folks,

On page 82 of the book "Introduction to Functional Programming using Haskell" the author Richard Bird provides this sample implementation of the floor function:

floor x = searchFrom 0 where searchFrom = decrease . upper . lower lower = until (<=x) decrease upper = until (>x) increase decrease n = n - 1 increase n = n + 1

The problem with that implementation is that it does not return an Integer value; rather, it returns a decimal (Double) value. Here's an example:

floor (-3.4) -- returns (-4.0)

That is wrong. The specification for floor says that it "maps a value of type Float to a value of type Integer." Clearly it is not producing an Integer result.

I will now explain how to revise floor so that it returns an Integer value. In the process we will see an excellent illustration of the Haskell types.

The heart of the problem is with the until function.

Here is how Richard Bird implements it:

until :: (a -> Bool) -> (a -> a) -> a -> a until p f y = if p y then y else until p f (f y)

It takes three arguments, p, f, and y. Look at the signature of that function. The type of the third argument, y, dictates the type of the other arguments and the type of the result--whatever type y is, the other arguments must be the same type and the result must be the same type.

Function until is first invoked by function lower:

lower = until (<=x) decrease 0

Here are the three arguments provided to function until:

(1) p is the partial function (<=x), where x is the input to the floor function. Suppose x is this value: x = (-3.4)

(2) f is the function decrease

(3) y is 0

Now you may argue, "Hey, the third argument, y, is 0 and that's an Integer, so clearly the result of function until will be an Integer." However, that is not correct. The type of 0 is ambiguous, it could be an Integer or it could be a Double. This ambiguity can be seen by checking its type using WinGHCi:

:type 0 0 :: Num a => a

The class Num is high up in Haskell's type hierarchy and it represents any number (Integer, Double, etc.). Thus, we cannot determine the type of function until's result just by examining its third argument. The other arguments will determine whether the 0 is an Integer or a Double. Let's examine the first argument:

p is the partial function (<=x), where x = (-3.4)

p compares "some value" against (-3.4). Let's check the type of (-3.4) using WinGHCi:

:type (-3.4) (-3.4) :: Fractional a => a

The datatype Double falls within the class Fractional. So p compares "some value" against a Double.

Fundamental rule of Haskell: you cannot compare an Integer against a Double, you can only compare a Double against a Double.

Recall that p compares "some value" against (-3.4). What is that "some value"? If we examine the body of function until we see that it is the third argument, y, and we know that y = 0. Ah, now we know how Haskell will treat 0: since the 0 is being compared against a Double value Haskell will treat the 0 as a Double. Okay, now that we know the type of y we can plug it into the type signature for function until:

until :: (a -> Bool) -> (a -> a) -> Double -> a

All a's must be of the same type, so the other a's must also be Double:

until :: (Double -> Bool) -> (Double -> Double) -> Double -> Double

Therefore function until will return a Double value. For example:

until (<=x) decrease 0 -- returns (0.0)

The output of function until is assigned to function lower:

lower = until (<=x) decrease

So the result of function lower is a Double value.

The output of lower is then input to upper and the Double datatype propagates through the entire chain of composed functions:

decrease . upper . lower

The result of function floor is therefore a Double value.

Okay, so how do we get floor to return an Integer value? The key is to prevent p in function until from casting the type of y to a Double. Recall function lower:

lower = until (<=x) decrease 0

Notice that p is this partial function:

(<=x)

We must modify p to express, "Hey, compare x against an Integer value that has been cast to a Double value." That is implemented using a Lambda (anonymous) function:

(\a -> (realToFrac a) <= x)

Read that as: For whatever value, a, is provided convert it to a Fractional (Double) value and then compare it to x.

Wow!

So we are telling Haskell that the 0 is not to be treated as a Fractional (Double) value, it is to be treated as a Real (Integer) value.

At last, we can implement function floor and it will return the desired Integer result:

floor x = searchFrom 0 where searchFrom = decrease . upper . lower lower = until (\a -> (realToFrac a) <= x) decrease upper = until (\a -> (realToFrac a) > x) increase decrease n = n - 1 increase n = n + 1

Notice that wherever function until is called (in lower and upper), the first argument, p, is a Lambda (anonymous) function that takes its argument, a, and casts it from a Real (Integer) value to a Fractional (Double) value. Here are a couple examples of using this revised floor function:

floor (-3.4) -- returns (-4) floor 3.4 -- returns 3

Notice that floor now returns an Integer value, which is what we want.

Here is the signature for floor:

floor :: (Fractional a, Ord a, Real c) => a -> c

Read as: Invoke function floor with a Fractional (Double) value and it will return a Real (Integer) value.

On page 83 Richard Bird shows a second version of function floor that uses a binary search:

floor x = searchFrom (-1, 1) where searchFrom = fst . middle . cross(lower, upper) lower = until (<= x) double upper = until (> x) double middle = until done improve done (m, n) = (m + 1 == n) improve (m, n) = if p <= x then (p, n) else (m, p) where p = (m + n) div 2

That has multiple problems. First, it is syntactically not a well-formed Haskell program because the div operator (on the last line) must have back ticks ( ` ) surrounding it:

where p = (m + n) `div` 2

Second, the functions lower and upper invoke function until. The first argument to until must be a Lambda function as described above:

lower = until (\m -> (realToFrac m) <= x) double upper = until (\n -> (realToFrac n) > x) double

Third, the function improve compares p (an Integer) against x (a Double), so p must be cast to a Fractional (Double) value:

improve (m, n) = if (realToFrac p) <= x then (p, n) else (m, p) where p = (m + n) div 2

With those three changes the function works as desired:

floor x = searchFrom (-1, 1) where searchFrom = fst . middle . cross(lower, upper) lower = until (\m -> (realToFrac m) <= x) double upper = until (\n -> (realToFrac n) > x) double middle = until done improve done (m, n) = (m + 1 == n) improve (m, n) = if (realToFrac p) <= x then (p, n) else (m, p) where p = (m + n) `div` 2

Here are a couple examples of using the revised floor function:

floor (-3.4) -- returns (-4) floor 3.4 -- returns 3

Notice that floor now returns an Integer value, which is what we want.

Here is the signature for floor:

floor :: (Fractional a, Ord a, Real c) => a -> c

Read as: Invoke function floor with a Fractional (Double) value and it will return a Real (Integer) value.

/Roger

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners