Odd values when enumerating a list

As part of a larger function definition, I needed to allow the domain (i, n) of a function to increment from i to n at varying rates. So I wrote:

f (i, n) k = [i, (i+k)..n]

into GHC. This returned odd results:

*Main> 开发者_运维技巧f (0.0, 1.0) 0.1
[0.0,0.1,0.2,0.30000000000000004,0.4000000000000001,0.5000000000000001,0.6000000000000001,0.7000000000000001,0.8,0.9,1.0]

Why does GHC return, e.g., 0.30000000000000004 instead of 0.3?

---

Because IEEE floating point arithmetic can't express decimal numbers precisely, in general. There is always a rounding error in the binary representation, which sometimes seeps to the surface when displaying the number.

Depending on how GHC converts floating-point numbers to a decimal representation, you might find that on Windows it displays the result as the expected 0.3. This is because Microsoft's runtime libraries are smarter than Linux and Mac about how they present floats.

EDIT: This may not be the case. The number 0.3 will encode as the integer 3fd3333333333333 when using IEEE floats, whereas 0.1 + 0.1 + 0.1 will produce a number that encodes as 3fd3333333333334, and I don't know whether Microsoft's runtime libraries are tolerant enough to round back to 0.3 when displaying this.

In any event, a good example of the different handling is to type 0.3 into a Python interactive shell. If it's Python 2.6, you'll get back 0.29999999999999999, and if it's 2.7, it will display 0.3.

---

If i, n, and k are rational, you could go the infinite-precision route:

f :: (Rational, Rational) -> Rational -> [Rational]
f (i, n) k = [i, (i+k) .. n]

The notation may require a bit of getting used to:

ghci> f (0%1, 1%1) (1%10)
[0 % 1,1 % 10,1 % 5,3 % 10,2 % 5,1 % 2,3 % 5,7 % 10,4 % 5,9 % 10,1 % 1]

Think of the % as a funny looking fraction bar.

You could view approximations with

import Control.Monad (mapM_)
import Data.Ratio (Rational, (%), denominator, numerator)
import Text.Printf (printf)

printApprox :: [Rational] -> IO ()
printApprox rs = do
  mapM_ putRationalToOnePlaceLn rs
  where putRationalToOnePlaceLn :: Rational -> IO ()
        putRationalToOnePlaceLn r = do
          let toOnePlace :: String
              toOnePlace = printf "%.1f" (numFrac / denomFrac)
              numFrac, denomFrac :: Double
              numFrac    = fromIntegral $ numerator   r
              denomFrac  = fromIntegral $ denominator r
          putStrLn toOnePlace

The code above is written in an imperative style with full type annotations. Read its type as transforming a list of rational numbers into some I/O action. The mapM_ combinator from Control.Monad evaluates an action (putRationalToOnePlaceLn in this case) for each value in a list (the rationals we want to approximate). You can think of it as sort of a for loop, and there is even a forM_ combinator that's identical to mapM_ except the order of the arguments is reversed. The underscore at the end is a Haskell convention showing that it discards the results of running the actions, and note that there are mapM and forM that do collect those results.

To arrange for the output of the approximations via putStrLn, we have to generate a string. If you were writing this in C, you'd have code along the lines of

int numerator = 1, denominator = 10;
printf("%.1f\n", (double) numerator / (double) denominator);

The Haskell code above is similar in structure. The type of Haskell's / operator is

(/) :: (Fractional a) => a -> a -> a

This says for some instance a of the typeclass Fractional, when given two values of the same type a, you'll get back another value of that type.

We can ask ghci to tell us about Fractional:

ghci> :info Fractional
class (Num a) => Fractional a where
  (/) :: a -> a -> a
  recip :: a -> a
  fromRational :: Rational -> a
    -- Defined in GHC.Real
instance Fractional Float -- Defined in GHC.Float
instance Fractional Double -- Defined in GHC.Float

Notice the instance lines at the bottom. This means we can

ghci> (22::Float) / (7::Float)
3.142857

or

ghci> (22::Double) / (7::Double)
3.142857142857143

but not

ghci> (22::Double) / (7::Float)

<interactive>:1:16:
    Couldn't match expected type `Double' against inferred type `Float'
    In the second argument of `(/)', namely `(7 :: Float)'
    In the expression: (22 :: Double) / (7 :: Float)
    In the definition of `it': it = (22 :: Double) / (7 :: Float)

and certainly not

ghci> (22::Integer) / (7::Integer)

<interactive>:1:0:
    No instance for (Fractional Integer)
      arising from a use of `/' at :1:0-27
    Possible fix: add an instance declaration for (Fractional Integer)
    In the expression: (22 :: Integer) / (7 :: Integer)
    In the definition of `it': it = (22 :: Integer) / (7 :: Integer)

Remember that Haskell's Rational type is defined as a ratio of Integers, so you can think of fromIntegral as sort of like a typecast in C.

Even after reading A Gentle Introduction to Haskell: Numbers, you'll still likely find Haskell to be frustratingly picky about mixing numeric types. It's too easy for us, who perform infinite-precision arithmetic in our heads or on paper, to forget that computers have only finite precision and must deal in approximations. Type safety is a helpful reality check.

Sample output:

*Main> printApprox $ f (0%1, 1%1) (1%10)
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

The definition of printApprox probably seemed comforting with all the helpful signposts such as names of functions and parameters or type annotations. As you grow more experienced and comfortable with Haskell, such imperative-looking definitions will begin to look cluttered and messy.

Haskell is a functional language: its strength is specifying the what, not the how, by assembling simple functions into more complex ones. Someone once suggested that Haskell manipulates functions as powerfully as Perl manipulates strings.

In point-free style, the arguments disappear leaving the structure of the computation. Learning to read and this style does take practice, but you'll find that it helps write cleaner code.

With tweaks to the imports, we can define a point-free equivalent such as

import Control.Arrow ((***), (&&&))
import Control.Monad (join, mapM_)
import Data.Ratio (Rational, (%), denominator, numerator)
import Text.Printf (printf)

printApproxPointFree :: [Rational] -> IO ()
printApproxPointFree =
  mapM_       $
  putStrLn    .
  toOnePlace  .
  uncurry (/) .
  join (***) fromIntegral .
  (numerator &&& denominator)
  where toOnePlace = printf "%.1f" :: Double -> String

We see a few familiar bits: our new friend mapM_, putStrLn, printf, numerator, and denominator.

There's also some weird stuff. Haskell's $ operator is another way to write function application. Its definition is

f $ x = f x

It may not seem terribly useful until you try

Prelude> show 1.0 / 2.0

<interactive>:1:0:
    No instance for (Fractional String)
      arising from a use of `/' at :1:0-13
    Possible fix: add an instance declaration for (Fractional String)
    In the expression: show 1.0 / 2.0
    In the definition of `it': it = show 1.0 / 2.0

You could write that line as

show (1.0 / 2.0)

or

show $ 1.0 / 2.0

So you can think of $ as another way to write parentheses.

Then there's . that means function composition. Its definition is

(f . g) x = f (g x)

which we could also write as

(f . g) x = f $ g x

As you can see, we apply the right-hand function and then feed the result to the left-hand function. You may remember definitions from mathematics textbooks such as

The name . was chosen for its similarity in appearance to the raised dot.

So with a chain of function compositions, it's often easiest to understand it by reading back-to-front.

The (numerator &&& denominator) bit uses a fan-out combinator from Control.Arrow. For example:

ghci> (numerator &&& denominator) $ 1%3
(1,3)

So it applies two functions to the same value and gives you back a tuple with the results. Remember we need to apply fromIntegral to both the numerator and denominator, and that's what join (***) fromIntegral does. Note that *** also comes from the Control.Arrow module.

Finally, the / operator takes separate arguments, not a tuple. Thinking imperatively, you might want to write something like

(fst tuple) / (snd tuple)

where

fst (a,_) = a
snd (_,b) = b

but think functionally! What if we could somehow transform / into a function that takes a tuple and uses its components as arguments for the division? That's exactly what uncurry (/) does!

You've taken a great first step with Haskell. Enjoy the journey!

---

A better way of doing this is more along the lines of

map (/10) [0 .. 10]

This takes whole numbers, thereby avoiding the float problem, and divides each one by 10.