Consider `error`-ing on an infinite decimal expansion, instead of looping forever

[lambda-fairy]

Right now, (1/3) :: Scientific causes an infinite loop. But with a bit of extra code, we can make it throw an error instead.

hasFiniteExpansion :: Rational -> Bool
hasFiniteExpansion = loop . denominator
  where
    loop 1 = True
    loop n
        | n `rem` 2 == 0 = loop (n `quot` 2)
        | n `rem` 5 == 0 = loop (n `quot` 5)
        | otherwise = False

fromRational :: Rational -> Scientific
fromRational x
    | hasFiniteExpansion x = ...  -- as before
    | otherwise = error $ "fromRational: " ++ show x ++ " has an infinite expansion"

I'm not sure how much this check would cost in terms of performance, but since we're going through Rational anyway I suspect it's not that bad.

[basvandijk]

I added the function fromRationalRepetend for doing this.

Like fromRational, this function converts a Rational to a Scientific but instead of diverging (i.e loop and consume all space) on repeating decimals it detects the repeating part, the repetend, and returns where it starts.

To detect the repetition this function consumes space linear in the number of digits in the resulting scientific. In order to bound the space usage an optional limit can be specified. If the number of digits reaches this limit Left (s, r) will be returned. Here s is the Scientific constructed so far and r is the remaining Rational. toRational s + r should yield to original Rational

If the limit is not reached or no limit was specified Right (s, mbRepetendIx) will be returned. Here s is the Scientific without any repetition and mbRepetendIx specifies if and where in the fractional part the repetend begins.

For example:

fromRationalRepetend Nothing (1 % 28) == Right (3.571428e-2, Just 2)

This represents the repeating decimal: 0.03571428571428571428... which is sometimes also unambiguously denoted as 0.03(571428). Here the repetend is enclosed in parantheses and starts at the 3rd digit (index 2) in the fractional part. Specifying a limit results in the following:

fromRationalRepetend (Just 4) (1 % 28) == Left (3.5e-2,1 % 1400)

You can expect the following property to hold.

forall (mbLimit :: Maybe Int) (r :: Rational).
r == (case fromRationalRepetend mbLimit r of
       Left (s, r') -> toRational s + r'
       Right (s, mbRepetendIx) ->
         case mbRepetendIx of
           Nothing         -> toRational s
           Just repetendIx -> toRationalRepetend s repetendIx)

I also added the reverse: toRationalRepetend which converts a Scientific with a repetend, which starts at the given index, into its corresponding Rational.

The algorithm used is described in the paper: turning_repeating_decimals_into_fractions.pdf

For example: toRationalRepetend 0.03571428 2 == 1 % 28

Preconditions for toRationalRepetend s r:

• r >= 0
• r < -(base10Exponent s)

[basvandijk]

Released as scientific-0.3.4.0.