How does list generation with Fractionals work?

Question

If i want to generate a list with the input:

[3.1,5.1..8.1]

GHC 8.6.3 returns:

[3.1,5.1,7.1,9.099999999999998]

My problem here isn't the approximation of 9.1, but why the list made by GHC has one element more than the following solution. In the documentation I found in GHC.Enum, that enumFromThenTo translates this to something similar to the following:

    -- | Used in Haskell's translation of @[n,n'..m]@ with
    --   @[n,n'..m] = enumFromThenTo n n' m@, a possible implementation
    --   being @enumFromThenTo n n' m = worker (f x) (c x) n m@,
    --   @x = fromEnum n' - fromEnum n@, @c x = bool (>=) (<=) (x > 0)@
    --   @f n y
    --      | n > 0 = f (n - 1) (succ y)
    --      | n < 0 = f (n + 1) (pred y)
    --      | otherwise = y@ and
    --   @worker s c v m
    --      | c v m = v : worker s c (s v) m
    --      | otherwise = []@

So the following code:

import Data.Bool
eftt n s m = worker (f x) (c x) n m
     where x = (fromEnum s) - (fromEnum n)
c x = bool (>=) (<=) (x > 0)
f n y 
    | n > 0 = f (n-1) (succ y)
    | n < 0 = f (n+1) (pred y)
    | otherwise = y
worker s c v m
    | c v m = v: worker s c (s v) m
    | otherwise = []

On the same input as before, this however returns this list:

[3.1,5.1,7.1]

The real implementation defined in GHC.Enum is the following:

enumFromThenTo x1 x2 y = map toEnum [fromEnum x1, fromEnum x2 .. fromEnum y]

But there is no instantiation of Enum Double or Enum Float in GHC.Enum

So when I tried to reproduce this with the following code:

import Prelude(putStrLn,show)
import GHC.Enum(toEnum,fromEnum,Enum,enumFromThenTo)
import GHC.Base(map)

main = putStrLn (show (_enumFromThenTo 3.1 5.1 8.1))

_enumFromThenTo :: (Enum a) => a -> a -> a -> [a]
_enumFromThenTo x1 x2 y = map toEnum [fromEnum x1, fromEnum x2 .. fromEnum y]

I compiled with:

$ ghc -package ghc -package base <file.hs>

The result was again:

[3.0,5.0,7.0]

What is happening here, such that the output becomes:

[3.1,5.1,7.1,9.099999999999998]

?

score 2 · Accepted Answer · answered Dec 15 '18 at 16:44

Well, this is instance Enum Double

instance Enum Double where
  enumFromThenTo = numericEnumThenFromTo

The implementation is here

numericEnumFromThenTo   :: (Ord a, Fractional a) => a -> a -> a -> [a]
numericEnumFromThenTo e1 e2 e3
    = takeWhile predicate (numericEnumFromThen e1 e2)
                                where
                                 mid = (e2 - e1) / 2
                                 predicate | e2 >= e1  = (<= e3 + mid)
                                           | otherwise = (>= e3 + mid)

More important than the implementation is the note above it:

-- These 'numeric' enumerations come straight from the Report

Which refers to this passage in the (2010) Report:

For Float and Double, the semantics of the enumFrom family is given by the rules for Int above, except that the list terminates when the elements become greater than e₃ + i∕2 for positive increment i, or when they become less than e₃ + i∕2 for negative i.

(Where e₃ refers to the upper bound, and i the increment.)

The comment you found on Enum and the implementation in class Enum are both irrelevant. The comment is just example code detailing how an instance might be implemented, and the implementation given is inside a class, and thus may be overridden with anything.

How does list generation with Fractionals work?

1 Answers1