-- CPP and GeneralizedNewtypeDeriving are needed for IArray UArray instance
-- FFI is for log1p
{-# LANGUAGE CPP, ForeignFunctionInterface, MultiParamTypeClasses #-}
-- We don't put these in LANGUAGE, because it's CPP guarded for GHC only
-- HACK: ScopedTypeVariables and InstanceSigs are for GHC 7.10 only...
{-# OPTIONS_GHC
    -XGeneralizedNewtypeDeriving
    -XScopedTypeVariables
    -XInstanceSigs
    #-}

{-# OPTIONS_GHC -Wall -fwarn-tabs #-}

{-# OPTIONS_GHC -O2 -fexcess-precision -fenable-rewrite-rules #-}

----------------------------------------------------------------
--                                                  ~ 2017.06.18
-- |
-- Module      :  Data.Number.LogFloat
-- Copyright   :  Copyright (c) 2007--2017 wren gayle romano
-- License     :  BSD3
-- Maintainer  :  wren@community.haskell.org
-- Stability   :  stable
-- Portability :  portable (with CPP, FFI)
--
-- This module presents a type for storing numbers in the log-domain.
-- The main reason for doing this is to prevent underflow when
-- multiplying many small probabilities as is done in Hidden Markov
-- Models and other statistical models often used for natural
-- language processing. The log-domain also helps prevent overflow
-- when multiplying many large numbers. In rare cases it can speed
-- up numerical computation (since addition is faster than
-- multiplication, though logarithms are exceptionally slow), but
-- the primary goal is to improve accuracy of results. A secondary
-- goal has been to maximize efficiency since these computations
-- are frequently done within a /O(n^3)/ loop.
--
-- The 'LogFloat' of this module is restricted to non-negative
-- numbers for efficiency's sake, see "Data.Number.LogFloat.Signed"
-- for doing signed log-domain calculations.
----------------------------------------------------------------

module Data.Number.LogFloat
    (
    -- * Exceptional numeric values
      module Data.Number.Transfinite

    -- * @LogFloat@ data type
    , LogFloat()
    -- ** Isomorphism to normal-domain
    , logFloat
    , fromLogFloat
    -- ** Isomorphism to log-domain
    , logToLogFloat
    , logFromLogFloat
    -- ** Additional operations
    , sum, product
    , pow

    -- * Accurate versions of logarithm\/exponentiation
    , log1p, expm1
    ) where

import Prelude hiding (log, sum, product, isInfinite, isNaN)
import Data.List (foldl')

import Data.Number.Transfinite
import Data.Number.PartialOrd


-- GHC can derive (IArray UArray LogFloat), but Hugs needs to coerce
-- TODO: see about nhc98/yhc, jhc/lhc
import Data.Array.Base    (IArray(..))
import Data.Array.Unboxed (UArray)

-- Hugs (Sept 2006) doesn't use the generic wrapper in base:Unsafe.Coerce
-- so we'll just have to go back to the original source.
#ifdef __HUGS__
import Hugs.IOExts        (unsafeCoerce)
#elif __NHC__
import NonStdUnsafeCoerce (unsafeCoerce)
#elif __GLASGOW_HASKELL__ >= 710
-- For when the *heap* representations are the same
--import Data.Coerce        (coerce)
-- For when the *unboxed array* storage representations are the same
import Unsafe.Coerce      (unsafeCoerce)
import Data.Ix            (Ix)
#endif

#ifdef __GLASGOW_HASKELL__
import Foreign.Storable (Storable)
#endif

----------------------------------------------------------------
--
-- | A @LogFloat@ is just a 'Double' with a special interpretation.
-- The 'logFloat' function is presented instead of the constructor,
-- in order to ensure semantic conversion. At present the 'Show'
-- instance will convert back to the normal-domain, and hence will
-- underflow at that point. This behavior may change in the future.
-- At present, the 'Read' instance parses things in the normal-domain
-- and then converts them to the log-domain. Again, this behavior
-- may change in the future.
--
-- Because 'logFloat' performs the semantic conversion, we can use
-- operators which say what we *mean* rather than saying what we're
-- actually doing to the underlying representation. That is,
-- equivalences like the following are true[1] thanks to type-class
-- overloading:
--
-- > logFloat (p + q) == logFloat p + logFloat q
-- > logFloat (p * q) == logFloat p * logFloat q
--
-- (Do note, however, that subtraction can and negation will throw
-- errors: since @LogFloat@ can only represent the positive half of
-- 'Double'. 'Num' is the wrong abstraction to put at the bottom
-- of the numeric type-class hierarchy; but alas, we're stuck with
-- it.)
--
-- Performing operations in the log-domain is cheap, prevents
-- underflow, and is otherwise very nice for dealing with miniscule
-- probabilities. However, crossing into and out of the log-domain
-- is expensive and should be avoided as much as possible. In
-- particular, if you're doing a series of multiplications as in
-- @lp * logFloat q * logFloat r@ it's faster to do @lp * logFloat
-- (q * r)@ if you're reasonably sure the normal-domain multiplication
-- won't underflow; because that way you enter the log-domain only
-- once, instead of twice. Also note that, for precision, if you're
-- doing more than a few multiplications in the log-domain, you
-- should use 'product' rather than using '(*)' repeatedly.
--
-- Even more particularly, you should /avoid addition/ whenever
-- possible. Addition is provided because sometimes we need it, and
-- the proper implementation is not immediately apparent. However,
-- between two @LogFloat@s addition requires crossing the exp\/log
-- boundary twice; with a @LogFloat@ and a 'Double' it's three
-- times, since the regular number needs to enter the log-domain
-- first. This makes addition incredibly slow. Again, if you can
-- parenthesize to do normal-domain operations first, do it!
--
-- [1] That is, true up-to underflow and floating point fuzziness.
-- Which is, of course, the whole point of this module.

newtype LogFloat = LogFloat Double
    deriving
    ( LogFloat -> LogFloat -> Bool
(LogFloat -> LogFloat -> Bool)
-> (LogFloat -> LogFloat -> Bool) -> Eq LogFloat
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: LogFloat -> LogFloat -> Bool
$c/= :: LogFloat -> LogFloat -> Bool
== :: LogFloat -> LogFloat -> Bool
$c== :: LogFloat -> LogFloat -> Bool
Eq
    , Eq LogFloat
Eq LogFloat
-> (LogFloat -> LogFloat -> Ordering)
-> (LogFloat -> LogFloat -> Bool)
-> (LogFloat -> LogFloat -> Bool)
-> (LogFloat -> LogFloat -> Bool)
-> (LogFloat -> LogFloat -> Bool)
-> (LogFloat -> LogFloat -> LogFloat)
-> (LogFloat -> LogFloat -> LogFloat)
-> Ord LogFloat
LogFloat -> LogFloat -> Bool
LogFloat -> LogFloat -> Ordering
LogFloat -> LogFloat -> LogFloat
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: LogFloat -> LogFloat -> LogFloat
$cmin :: LogFloat -> LogFloat -> LogFloat
max :: LogFloat -> LogFloat -> LogFloat
$cmax :: LogFloat -> LogFloat -> LogFloat
>= :: LogFloat -> LogFloat -> Bool
$c>= :: LogFloat -> LogFloat -> Bool
> :: LogFloat -> LogFloat -> Bool
$c> :: LogFloat -> LogFloat -> Bool
<= :: LogFloat -> LogFloat -> Bool
$c<= :: LogFloat -> LogFloat -> Bool
< :: LogFloat -> LogFloat -> Bool
$c< :: LogFloat -> LogFloat -> Bool
compare :: LogFloat -> LogFloat -> Ordering
$ccompare :: LogFloat -> LogFloat -> Ordering
$cp1Ord :: Eq LogFloat
Ord -- Should we really perpetuate the Ord lie?
#ifdef __GLASGOW_HASKELL__
    -- The H98 Report doesn't include these among the options for
    -- automatic derivation. But GHC >= 6.8.2 (at least) can derive
    -- them (even without GeneralizedNewtypeDeriving). However,
    -- GHC >= 7.10 can't derive @IArray UArray@ thanks to the new
    -- type-role stuff! since 'UArray' is declared to be nominal
    -- in both arguments... and that seems to be necessary:
    -- cf., <https://ghc.haskell.org/trac/ghc/ticket/9220>
#if __GLASGOW_HASKELL__ < 710
    , IArray UArray
#endif
    , Ptr b -> Int -> IO LogFloat
Ptr b -> Int -> LogFloat -> IO ()
Ptr LogFloat -> IO LogFloat
Ptr LogFloat -> Int -> IO LogFloat
Ptr LogFloat -> Int -> LogFloat -> IO ()
Ptr LogFloat -> LogFloat -> IO ()
LogFloat -> Int
(LogFloat -> Int)
-> (LogFloat -> Int)
-> (Ptr LogFloat -> Int -> IO LogFloat)
-> (Ptr LogFloat -> Int -> LogFloat -> IO ())
-> (forall b. Ptr b -> Int -> IO LogFloat)
-> (forall b. Ptr b -> Int -> LogFloat -> IO ())
-> (Ptr LogFloat -> IO LogFloat)
-> (Ptr LogFloat -> LogFloat -> IO ())
-> Storable LogFloat
forall b. Ptr b -> Int -> IO LogFloat
forall b. Ptr b -> Int -> LogFloat -> IO ()
forall a.
(a -> Int)
-> (a -> Int)
-> (Ptr a -> Int -> IO a)
-> (Ptr a -> Int -> a -> IO ())
-> (forall b. Ptr b -> Int -> IO a)
-> (forall b. Ptr b -> Int -> a -> IO ())
-> (Ptr a -> IO a)
-> (Ptr a -> a -> IO ())
-> Storable a
poke :: Ptr LogFloat -> LogFloat -> IO ()
$cpoke :: Ptr LogFloat -> LogFloat -> IO ()
peek :: Ptr LogFloat -> IO LogFloat
$cpeek :: Ptr LogFloat -> IO LogFloat
pokeByteOff :: Ptr b -> Int -> LogFloat -> IO ()
$cpokeByteOff :: forall b. Ptr b -> Int -> LogFloat -> IO ()
peekByteOff :: Ptr b -> Int -> IO LogFloat
$cpeekByteOff :: forall b. Ptr b -> Int -> IO LogFloat
pokeElemOff :: Ptr LogFloat -> Int -> LogFloat -> IO ()
$cpokeElemOff :: Ptr LogFloat -> Int -> LogFloat -> IO ()
peekElemOff :: Ptr LogFloat -> Int -> IO LogFloat
$cpeekElemOff :: Ptr LogFloat -> Int -> IO LogFloat
alignment :: LogFloat -> Int
$calignment :: LogFloat -> Int
sizeOf :: LogFloat -> Int
$csizeOf :: LogFloat -> Int
Storable
#endif
    )

#if __GLASGOW_HASKELL__ >= 710
-- TODO: this version should also work for NHC and Hugs, I think...
-- HACK: we should be able to just unsafeCoerce the functions
-- themselves, instead of coercing the inputs and the outputs; but,
-- GHC 7.10 seems to get confused about trying to coerce the index
-- types too... To fix this we give explicit signatures, as below,
-- but this requires both ScopedTypeVariables and InstanceSigs; and
-- I'm not sure when InstanceSigs was introduced.

instance IArray UArray LogFloat where
    {-# INLINE bounds #-}
    bounds :: forall i. Ix i => UArray i LogFloat -> (i, i)
    bounds :: UArray i LogFloat -> (i, i)
bounds = (UArray i Double -> (i, i)) -> UArray i LogFloat -> (i, i)
forall a b. a -> b
unsafeCoerce (UArray i Double -> (i, i)
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> (i, i)
bounds :: UArray i Double -> (i, i))

    {-# INLINE numElements #-}
    numElements :: forall i. Ix i => UArray i LogFloat -> Int
    numElements :: UArray i LogFloat -> Int
numElements = (UArray i Double -> Int) -> UArray i LogFloat -> Int
forall a b. a -> b
unsafeCoerce (UArray i Double -> Int
forall (a :: * -> * -> *) e i. (IArray a e, Ix i) => a i e -> Int
numElements :: UArray i Double -> Int)

    {-# INLINE unsafeArray #-}
    unsafeArray :: forall i. Ix i => (i,i) -> [(Int,LogFloat)] -> UArray i LogFloat
    unsafeArray :: (i, i) -> [(Int, LogFloat)] -> UArray i LogFloat
unsafeArray = ((i, i) -> [(Int, Double)] -> UArray i Double)
-> (i, i) -> [(Int, LogFloat)] -> UArray i LogFloat
forall a b. a -> b
unsafeCoerce ((i, i) -> [(Int, Double)] -> UArray i Double
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [(Int, e)] -> a i e
unsafeArray :: (i,i) -> [(Int,Double)] -> UArray i Double)

    {-# INLINE unsafeAt #-}
    unsafeAt :: forall i. Ix i => UArray i LogFloat -> Int -> LogFloat
    unsafeAt :: UArray i LogFloat -> Int -> LogFloat
unsafeAt = (UArray i Double -> Int -> Double)
-> UArray i LogFloat -> Int -> LogFloat
forall a b. a -> b
unsafeCoerce (UArray i Double -> Int -> Double
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
unsafeAt :: UArray i Double -> Int -> Double)

    {-# INLINE unsafeReplace #-}
    unsafeReplace :: forall i. Ix i => UArray i LogFloat -> [(Int,LogFloat)] -> UArray i LogFloat
    unsafeReplace :: UArray i LogFloat -> [(Int, LogFloat)] -> UArray i LogFloat
unsafeReplace = (UArray i Double -> [(Int, Double)] -> UArray i Double)
-> UArray i LogFloat -> [(Int, LogFloat)] -> UArray i LogFloat
forall a b. a -> b
unsafeCoerce (UArray i Double -> [(Int, Double)] -> UArray i Double
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> [(Int, e)] -> a i e
unsafeReplace :: UArray i Double -> [(Int,Double)] -> UArray i Double)

    {-# INLINE unsafeAccum #-}
    unsafeAccum :: forall i e. Ix i => (LogFloat -> e -> LogFloat) -> UArray i LogFloat -> [(Int,e)] -> UArray i LogFloat
    unsafeAccum :: (LogFloat -> e -> LogFloat)
-> UArray i LogFloat -> [(Int, e)] -> UArray i LogFloat
unsafeAccum = ((Double -> e -> Double)
 -> UArray i Double -> [(Int, e)] -> UArray i Double)
-> (LogFloat -> e -> LogFloat)
-> UArray i LogFloat
-> [(Int, e)]
-> UArray i LogFloat
forall a b. a -> b
unsafeCoerce ((Double -> e -> Double)
-> UArray i Double -> [(Int, e)] -> UArray i Double
forall (a :: * -> * -> *) e i e'.
(IArray a e, Ix i) =>
(e -> e' -> e) -> a i e -> [(Int, e')] -> a i e
unsafeAccum :: (Double -> e -> Double) -> UArray i Double -> [(Int,e)] -> UArray i Double)

    {-# INLINE unsafeAccumArray #-}
    unsafeAccumArray :: forall i e. Ix i => (LogFloat -> e -> LogFloat) -> LogFloat -> (i,i) -> [(Int,e)] -> UArray i LogFloat
    unsafeAccumArray :: (LogFloat -> e -> LogFloat)
-> LogFloat -> (i, i) -> [(Int, e)] -> UArray i LogFloat
unsafeAccumArray = ((Double -> e -> Double)
 -> Double -> (i, i) -> [(Int, e)] -> UArray i Double)
-> (LogFloat -> e -> LogFloat)
-> LogFloat
-> (i, i)
-> [(Int, e)]
-> UArray i LogFloat
forall a b. a -> b
unsafeCoerce ((Double -> e -> Double)
-> Double -> (i, i) -> [(Int, e)] -> UArray i Double
forall (a :: * -> * -> *) e i e'.
(IArray a e, Ix i) =>
(e -> e' -> e) -> e -> (i, i) -> [(Int, e')] -> a i e
unsafeAccumArray :: (Double -> e -> Double) -> Double -> (i,i) -> [(Int,e)] -> UArray i Double)

#elif __HUGS__ || __NHC__
-- TODO: Storable instance. Though Foreign.Storable isn't in Hugs(Sept06)

-- These two operators make it much easier to read the instance.
-- Hopefully inlining everything will get rid of the eta overhead.
-- <http://matt.immute.net/content/pointless-fun>
(~>) :: (a -> b) -> (d -> c) -> (b -> d) -> a -> c
{-# INLINE (~>) #-}
infixr 2 ~>
f ~> g = (. f) . (g .)

($::) :: a -> (a -> b) -> b
{-# INLINE ($::) #-}
infixl 1 $::
($::) = flip ($)


{-# INLINE logFromLFAssocs #-}
logFromLFAssocs :: [(Int, LogFloat)] -> [(Int, Double)]
#if __GLASGOW_HASKELL__ >= 710
logFromLFAssocs = coerce
#else
logFromLFAssocs = unsafeCoerce
#endif

-- HACK: can't coerce, cf: <https://ghc.haskell.org/trac/ghc/ticket/9220>
{-# INLINE logFromLFUArray #-}
logFromLFUArray :: UArray a LogFloat -> UArray a Double
logFromLFUArray = unsafeCoerce

-- Named unsafe because it could allow injecting NaN if misused
-- HACK: can't coerce, cf: <https://ghc.haskell.org/trac/ghc/ticket/9220>
{-# INLINE unsafeLogToLFUArray #-}
unsafeLogToLFUArray :: UArray a Double -> UArray a LogFloat
unsafeLogToLFUArray = unsafeCoerce

-- Named unsafe because it could allow injecting NaN if misused
{-# INLINE unsafeLogToLFFunc #-}
unsafeLogToLFFunc :: (LogFloat -> a -> LogFloat) -> (Double -> a -> Double)
unsafeLogToLFFunc = ($:: unsafeLogToLogFloat ~> id ~> logFromLogFloat)

-- | Remove the extraneous 'isNaN' test of 'logToLogFloat', when
-- we know it's safe.
{-# INLINE unsafeLogToLogFloat #-}
unsafeLogToLogFloat :: Double -> LogFloat
unsafeLogToLogFloat = LogFloat


instance IArray UArray LogFloat where
    {-# INLINE bounds #-}
    bounds = bounds . logFromLFUArray

-- Apparently this method was added in base-2.0/GHC-6.6 but Hugs
-- (Sept 2006) doesn't have it. Not sure about NHC's base
#if (!(defined(__HUGS__))) || (__HUGS__ > 200609)
    {-# INLINE numElements #-}
    numElements = numElements . logFromLFUArray
#endif

    {-# INLINE unsafeArray #-}
    unsafeArray =
        unsafeArray $:: id ~> logFromLFAssocs ~> unsafeLogToLFUArray

    {-# INLINE unsafeAt #-}
    unsafeAt =
        unsafeAt $:: logFromLFUArray ~> id ~> unsafeLogToLogFloat

    {-# INLINE unsafeReplace #-}
    unsafeReplace =
        unsafeReplace $:: logFromLFUArray ~> logFromLFAssocs ~> unsafeLogToLFUArray

    {-# INLINE unsafeAccum #-}
    unsafeAccum =
        unsafeAccum $:: unsafeLogToLFFunc ~> logFromLFUArray ~> id ~> unsafeLogToLFUArray

    {-# INLINE unsafeAccumArray #-}
    unsafeAccumArray =
        unsafeAccumArray $:: unsafeLogToLFFunc ~> logFromLogFloat ~> id ~> id ~> unsafeLogToLFUArray
#endif

-- TODO: the Nothing branch should never be reachable. Once we get
-- a test suite up and going to *verify* the never-NaN invariant,
-- we should be able to eliminate the branch and the isNaN checks.
instance PartialOrd LogFloat where
    cmp :: LogFloat -> LogFloat -> Maybe Ordering
cmp (LogFloat Double
x) (LogFloat Double
y)
        | Double -> Bool
forall a. Transfinite a => a -> Bool
isNaN Double
x Bool -> Bool -> Bool
|| Double -> Bool
forall a. Transfinite a => a -> Bool
isNaN Double
y = Maybe Ordering
forall a. Maybe a
Nothing
        | Bool
otherwise          = Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just (Ordering -> Maybe Ordering) -> Ordering -> Maybe Ordering
forall a b. (a -> b) -> a -> b
$! Double
x Double -> Double -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` Double
y

instance Read LogFloat where
    readsPrec :: Int -> ReadS LogFloat
readsPrec Int
p String
s =
        [(Double -> LogFloat
LogFloat (Double -> Double
forall a. (Floating a, Transfinite a) => a -> a
log Double
x), String
r) | (Double
x, String
r) <- Int -> ReadS Double
forall a. Read a => Int -> ReadS a
readsPrec Int
p String
s, Bool -> Bool
not (Double -> Bool
forall a. Transfinite a => a -> Bool
isNaN Double
x), Double
x Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
>= Double
0]

----------------------------------------------------------------
-- | Reduce the number of constant string literals we need to store.
errorOutOfRange :: String -> a
{-# NOINLINE errorOutOfRange #-}
errorOutOfRange :: String -> a
errorOutOfRange String
fun =
    String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$! String
"Data.Number.LogFloat."String -> String -> String
forall a. [a] -> [a] -> [a]
++String
funString -> String -> String
forall a. [a] -> [a] -> [a]
++ String
": argument out of range"

-- Both guards are redundant due to the subsequent call to
-- 'Data.Number.Transfinite.log' at all use sites. However we use
-- this function to give local error messages. Perhaps we should
-- catch the exception and throw the new message instead? Portability?

guardNonNegative :: String -> Double -> Double
guardNonNegative :: String -> Double -> Double
guardNonNegative String
fun Double
x
    | Double -> Bool
forall a. Transfinite a => a -> Bool
isNaN Double
x Bool -> Bool -> Bool
|| Double
x Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
< Double
0 = String -> Double
forall a. String -> a
errorOutOfRange String
fun
    | Bool
otherwise        = Double
x

guardIsANumber :: String -> Double -> Double
guardIsANumber :: String -> Double -> Double
guardIsANumber String
fun Double
x
    | Double -> Bool
forall a. Transfinite a => a -> Bool
isNaN Double
x   = String -> Double
forall a. String -> a
errorOutOfRange String
fun
    | Bool
otherwise = Double
x

----------------------------------------------------------------
-- | Constructor which does semantic conversion from normal-domain
-- to log-domain. Throws errors on negative and NaN inputs. If @p@
-- is non-negative, then following equivalence holds:
--
-- > logFloat p == logToLogFloat (log p)
--
-- If @p@ is NaN or negative, then the two sides differ only in
-- which error is thrown.
logFloat :: Double -> LogFloat
{-# INLINE [0] logFloat #-}
-- TODO: should we use NOINLINE or [~0] to avoid the possibility of code bloat?
logFloat :: Double -> LogFloat
logFloat = Double -> LogFloat
LogFloat (Double -> LogFloat) -> (Double -> Double) -> Double -> LogFloat
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> Double
forall a. (Floating a, Transfinite a) => a -> a
log (Double -> Double) -> (Double -> Double) -> Double -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Double -> Double
guardNonNegative String
"logFloat"


-- | Constructor which assumes the argument is already in the
-- log-domain. Throws errors on @notANumber@ inputs.
logToLogFloat :: Double -> LogFloat
logToLogFloat :: Double -> LogFloat
logToLogFloat = Double -> LogFloat
LogFloat (Double -> LogFloat) -> (Double -> Double) -> Double -> LogFloat
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Double -> Double
guardIsANumber String
"logToLogFloat"


-- | Semantically convert our log-domain value back into the
-- normal-domain. Beware of overflow\/underflow. The following
-- equivalence holds (without qualification):
--
-- > fromLogFloat == exp . logFromLogFloat
--
fromLogFloat :: LogFloat -> Double
{-# INLINE [0] fromLogFloat #-}
-- TODO: should we use NOINLINE or [~0] to avoid the possibility of code bloat?
fromLogFloat :: LogFloat -> Double
fromLogFloat (LogFloat Double
x) = Double -> Double
forall a. Floating a => a -> a
exp Double
x


-- | Return the log-domain value itself without conversion.
logFromLogFloat :: LogFloat -> Double
logFromLogFloat :: LogFloat -> Double
logFromLogFloat (LogFloat Double
x) = Double
x


-- These are our module-specific versions of "log\/exp" and "exp\/log";
-- They do the same things but also have a @LogFloat@ in between
-- the logarithm and exponentiation. In order to ensure these rules
-- fire, we have to delay the inlining on two of the four
-- con-\/destructors.

{-# RULES
-- Out of log-domain and back in
"log/fromLogFloat"       forall x. log (fromLogFloat x) = logFromLogFloat x
"logFloat/fromLogFloat"  forall x. logFloat (fromLogFloat x) = x

-- Into log-domain and back out
"fromLogFloat/logFloat"  forall x. fromLogFloat (logFloat x) = x
    #-}

----------------------------------------------------------------
-- To show it, we want to show the normal-domain value rather than
-- the log-domain value. Also, if someone managed to break our
-- invariants (e.g. by passing in a negative and noone's pulled on
-- the thunk yet) then we want to crash before printing the
-- constructor, rather than after.  N.B. This means the show will
-- underflow\/overflow in the same places as normal doubles since
-- we underflow at the @exp@. Perhaps this means we should show the
-- log-domain value instead.

instance Show LogFloat where
    showsPrec :: Int -> LogFloat -> String -> String
showsPrec Int
p (LogFloat Double
x) =
        let y :: Double
y = Double -> Double
forall a. Floating a => a -> a
exp Double
x in Double
y Double -> (String -> String) -> String -> String
`seq`
        Bool -> (String -> String) -> String -> String
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
9)
            ( String -> String -> String
showString String
"logFloat "
            (String -> String) -> (String -> String) -> String -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Double -> String -> String
forall a. Show a => Int -> a -> String -> String
showsPrec Int
11 Double
y
            )


----------------------------------------------------------------
-- Technically these should use 'Foreign.C.CDouble' however there's
-- no isomorphism provided to normal 'Double'. The former is
-- documented as being a newtype of the later, and so this should
-- be safe.

#ifdef __USE_FFI__
#define LOG1P_WHICH_VERSION FFI version.
#else
#define LOG1P_WHICH_VERSION naive version! \
    Contact the maintainer with any FFI difficulties.
#endif


-- | Definition: @log1p == log . (1+)@. Standard C libraries provide
-- a special definition for 'log1p' which is more accurate than
-- doing the naive thing, especially for very small arguments. For
-- example, the naive version underflows around @2 ** -53@, whereas
-- the specialized version underflows around @2 ** -1074@. This
-- function is used by ('+') and ('-') on @LogFloat@.
--
-- N.B. The @statistics:Statistics.Math@ module provides a pure
-- Haskell implementation of @log1p@ for those who are interested.
-- We do not copy it here because it relies on the @vector@ package
-- which is non-portable. If there is sufficient interest, a portable
-- variant of that implementation could be made. Contact the
-- maintainer if the FFI and naive implementations are insufficient
-- for your needs.
--
-- /This installation was compiled to use the LOG1P_WHICH_VERSION/

#ifdef __USE_FFI__
foreign import ccall unsafe "math.h log1p"
    log1p :: Double -> Double
#else
-- See statistics:Statistics.Math for a more accurate Haskell
-- implementation.
log1p :: Double -> Double
{-# INLINE [0] log1p #-}
log1p x = log (1 + x)
#endif


-- | Definition: @expm1 == subtract 1 . exp@. Standard C libraries
-- provide a special definition for 'expm1' which is more accurate
-- than doing the naive thing, especially for very small arguments.
-- This function isn't needed internally, but is provided for
-- symmetry with 'log1p'.
--
-- /This installation was compiled to use the LOG1P_WHICH_VERSION/

#ifdef __USE_FFI__
foreign import ccall unsafe "math.h expm1"
    expm1 :: Double -> Double
#else
expm1 :: Double -> Double
{-# INLINE [0] expm1 #-}
expm1 x = exp x - 1
#endif

-- CPP guarded because they won't fire if we're using the FFI versions
#if !defined(__USE_FFI__)
{-# RULES
-- Into log-domain and back out
"expm1/log1p"    forall x. expm1 (log1p x) = x

-- Out of log-domain and back in
"log1p/expm1"    forall x. log1p (expm1 x) = x
    #-}
#endif

----------------------------------------------------------------
-- These all work without causing underflow. However, do note that
-- they tend to induce more of the floating-point fuzz than using
-- regular floating numbers because @exp . log@ doesn't really equal
-- @id@. In any case, our main aim is for preventing underflow when
-- multiplying many small numbers (and preventing overflow for
-- multiplying many large numbers) so we're not too worried about
-- +\/- 4e-16.

instance Num LogFloat where
    -- N.B. In Hugs (Sept2006) the (>=) always returns True if
    --      either isNaN. This does not constitute a bug since we
    --      maintain the invariant that values wrapped by 'LogFloat'
    --      are not NaN.

    * :: LogFloat -> LogFloat -> LogFloat
(*) (LogFloat Double
x) (LogFloat Double
y)
        |    Double -> Bool
forall a. Transfinite a => a -> Bool
isInfinite Double
x
          Bool -> Bool -> Bool
&& Double -> Bool
forall a. Transfinite a => a -> Bool
isInfinite Double
y
          Bool -> Bool -> Bool
&& Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double -> Double
forall a. Num a => a -> a
negate Double
y = Double -> LogFloat
LogFloat Double
forall a. Transfinite a => a
negativeInfinity -- @0*infinity == 0@
        | Bool
otherwise        = Double -> LogFloat
LogFloat (Double
xDouble -> Double -> Double
forall a. Num a => a -> a -> a
+Double
y)

    + :: LogFloat -> LogFloat -> LogFloat
(+) (LogFloat Double
x) (LogFloat Double
y)
        | Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
y
          Bool -> Bool -> Bool
&& Double -> Bool
forall a. Transfinite a => a -> Bool
isInfinite Double
x
          Bool -> Bool -> Bool
&& Double -> Bool
forall a. Transfinite a => a -> Bool
isInfinite Double
y = Double -> LogFloat
LogFloat Double
x -- @0+0 == 0@, @infinity+infinity == infinity@
        | Double
x Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
>= Double
y          = Double -> LogFloat
LogFloat (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double -> Double
log1p (Double -> Double
forall a. Floating a => a -> a
exp (Double
y Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
x)))
        | Bool
otherwise       = Double -> LogFloat
LogFloat (Double
y Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double -> Double
log1p (Double -> Double
forall a. Floating a => a -> a
exp (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
y)))

    (-) (LogFloat Double
x) (LogFloat Double
y)
        |    Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
forall a. Transfinite a => a
negativeInfinity
          Bool -> Bool -> Bool
&& Double
y Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
forall a. Transfinite a => a
negativeInfinity = Double -> LogFloat
LogFloat Double
forall a. Transfinite a => a
negativeInfinity -- @0-0 == 0@
        | Bool
otherwise =
            -- BUG: Will throw error if x < y
            -- TODO: flip @x@ and @y@ when @y > x@.
            -- Also, will throw error if (x,y) is (infinity,infinity)
            Double -> LogFloat
LogFloat (String -> Double -> Double
guardIsANumber String
"(-)" (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double -> Double
log1p (Double -> Double
forall a. Num a => a -> a
negate (Double -> Double
forall a. Floating a => a -> a
exp (Double
y Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
x)))))

    signum :: LogFloat -> LogFloat
signum (LogFloat Double
x)
        | Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
forall a. Transfinite a => a
negativeInfinity = LogFloat
0
        | Double
x Double -> Double -> Bool
forall a. Ord a => a -> a -> Bool
>  Double
forall a. Transfinite a => a
negativeInfinity = LogFloat
1
        | Bool
otherwise             = String -> LogFloat
forall a. String -> a
errorOutOfRange String
"signum"
        -- The extra guard protects against NaN, in case someone
        -- broke the invariant. That shouldn't be possible and
        -- so noone else bothers to check, but we check here just
        -- in case.

    negate :: LogFloat -> LogFloat
negate LogFloat
_    = String -> LogFloat
forall a. String -> a
errorOutOfRange String
"negate"

    abs :: LogFloat -> LogFloat
abs         = LogFloat -> LogFloat
forall a. a -> a
id

    fromInteger :: Integer -> LogFloat
fromInteger = Double -> LogFloat
LogFloat (Double -> LogFloat) -> (Integer -> Double) -> Integer -> LogFloat
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> Double
forall a. (Floating a, Transfinite a) => a -> a
log
                (Double -> Double) -> (Integer -> Double) -> Integer -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Double -> Double
guardNonNegative String
"fromInteger" (Double -> Double) -> (Integer -> Double) -> Integer -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Double
forall a. Num a => Integer -> a
fromInteger


instance Fractional LogFloat where
    -- n/0 == infinity is handled seamlessly for us. We must catch
    -- 0/0 and infinity/infinity NaNs, and handle 0/infinity.
    / :: LogFloat -> LogFloat -> LogFloat
(/) (LogFloat Double
x) (LogFloat Double
y)
        | Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
y
          Bool -> Bool -> Bool
&& Double -> Bool
forall a. Transfinite a => a -> Bool
isInfinite Double
x
          Bool -> Bool -> Bool
&& Double -> Bool
forall a. Transfinite a => a -> Bool
isInfinite Double
y       = String -> LogFloat
forall a. String -> a
errorOutOfRange String
"(/)"
        | Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
forall a. Transfinite a => a
negativeInfinity = Double -> LogFloat
LogFloat Double
forall a. Transfinite a => a
negativeInfinity -- @0/infinity == 0@
        | Bool
otherwise             = Double -> LogFloat
LogFloat (Double
xDouble -> Double -> Double
forall a. Num a => a -> a -> a
-Double
y)

    fromRational :: Rational -> LogFloat
fromRational = Double -> LogFloat
LogFloat (Double -> LogFloat)
-> (Rational -> Double) -> Rational -> LogFloat
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> Double
forall a. (Floating a, Transfinite a) => a -> a
log
                 (Double -> Double) -> (Rational -> Double) -> Rational -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Double -> Double
guardNonNegative String
"fromRational" (Double -> Double) -> (Rational -> Double) -> Rational -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rational -> Double
forall a. Fractional a => Rational -> a
fromRational


-- Just for fun. The more coercion functions the better. Though
-- Rationals are very buggy when it comes to transfinite values
instance Real LogFloat where
    toRational :: LogFloat -> Rational
toRational (LogFloat Double
x)
        | Double -> Bool
forall a. Transfinite a => a -> Bool
isInfinite Double
ex Bool -> Bool -> Bool
|| Double -> Bool
forall a. Transfinite a => a -> Bool
isNaN Double
ex = String -> Rational
forall a. String -> a
errorOutOfRange String
"toRational"
        | Bool
otherwise                 = Double -> Rational
forall a. Real a => a -> Rational
toRational Double
ex
        where
        ex :: Double
ex = Double -> Double
forall a. Floating a => a -> a
exp Double
x


----------------------------------------------------------------
-- | /O(1)/. Compute powers in the log-domain; that is, the following
-- equivalence holds (modulo underflow and all that):
--
-- > logFloat (p ** m) == logFloat p `pow` m
--
-- /Since: 0.13/
pow :: LogFloat -> Double -> LogFloat
{-# INLINE pow #-}
infixr 8 `pow`
pow :: LogFloat -> Double -> LogFloat
pow (LogFloat Double
x) Double
m
    | Double -> Bool
forall a. Transfinite a => a -> Bool
isNaN Double
mx  = Double -> LogFloat
LogFloat Double
0
    | Bool
otherwise = Double -> LogFloat
LogFloat Double
mx
    where
    -- N.B., will be NaN when @x == negativeInfinity && m == 0@
    -- (which is true when m is -0 as well as +0). We check for NaN
    -- after multiplying, rather than checking this precondition
    -- before multiplying, in an attempt to simplify/optimize the
    -- generated code.
    -- TODO: benchmark.
    mx :: Double
mx = Double
m Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
x


-- N.B., the default implementation of (**) for Complex is wrong.
-- It can be fixed by using the definition:
-- > x ** y = if x == 0 then 0 else exp (log x * y)
-- cf., <https://ghc.haskell.org/trac/ghc/ticket/8539>
-- TODO: Is this relevant to us at all?


-- TODO: check out ekmett's compensated library.


-- Some good test cases:
-- for @logsumexp == log . sum . map exp@:
--     logsumexp[0,1,0] should be about 1.55
-- for correctness of avoiding underflow:
--     logsumexp[1000,1001,1000]   ~~ 1001.55 ==  1000 + 1.55
--     logsumexp[-1000,-999,-1000] ~~ -998.45 == -1000 + 1.55
--
-- | /O(n)/. Compute the sum of a finite list of 'LogFloat's, being
-- careful to avoid underflow issues. That is, the following
-- equivalence holds (modulo underflow and all that):
--
-- > logFloat . sum == sum . map logFloat
--
-- /N.B./, this function requires two passes over the input. Thus,
-- it is not amenable to list fusion, and hence will use a lot of
-- memory when summing long lists.
--
-- /Since: 0.13/
sum :: [LogFloat] -> LogFloat
sum :: [LogFloat] -> LogFloat
sum [LogFloat]
xs = Double -> LogFloat
LogFloat (Double
theMax Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double -> Double
forall a. (Floating a, Transfinite a) => a -> a
log Double
theSum)
    where
    LogFloat Double
theMax = [LogFloat] -> LogFloat
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [LogFloat]
xs

    -- compute @\log \sum_{x \in xs} \exp(x - theMax)@
    theSum :: Double
theSum = (Double -> LogFloat -> Double) -> Double -> [LogFloat] -> Double
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\ Double
acc (LogFloat Double
x) -> Double
acc Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double -> Double
forall a. Floating a => a -> a
exp (Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
theMax)) Double
0 [LogFloat]
xs

-- TODO: expose a single-pass version for the special case where
-- the first element of the list is (promised to be) the maximum
-- element?



-- | /O(n)/. Compute the product of a finite list of 'LogFloat's,
-- being careful to avoid numerical error due to loss of precision.
-- That is, the following equivalence holds (modulo underflow and
-- all that):
--
-- > logFloat . product == product . map logFloat
--
-- /Since: 0.13/
product :: [LogFloat] -> LogFloat
product :: [LogFloat] -> LogFloat
product = Double -> Double -> [LogFloat] -> LogFloat
kahan Double
0 Double
0
    where
    kahan :: Double -> Double -> [LogFloat] -> LogFloat
kahan Double
t Double
c [LogFloat]
_ | Double
t Double -> Bool -> Bool
`seq` Double
c Double -> Bool -> Bool
`seq` Bool
False = LogFloat
forall a. HasCallStack => a
undefined
    kahan Double
t Double
_ []                = Double -> LogFloat
LogFloat Double
t
    kahan Double
t Double
c (LogFloat Double
x : [LogFloat]
xs)
        -- Avoid NaN when there's a negInfty in the list. N.B.,
        -- this causes zero to annihilate infinity.
        | Double
x Double -> Double -> Bool
forall a. Eq a => a -> a -> Bool
== Double
forall a. Transfinite a => a
negativeInfinity = Double -> LogFloat
LogFloat Double
forall a. Transfinite a => a
negativeInfinity
        | Bool
otherwise =
            -- Beware this getting incorrectly optimized away by
            -- constant folding!
            let y :: Double
y  = Double
x Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
c
                t' :: Double
t' = Double
t Double -> Double -> Double
forall a. Num a => a -> a -> a
+ Double
y
                c' :: Double
c' = (Double
t' Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
t) Double -> Double -> Double
forall a. Num a => a -> a -> a
- Double
y
            in Double -> Double -> [LogFloat] -> LogFloat
kahan Double
t' Double
c' [LogFloat]
xs

-- This version *completely* eliminates rounding errors and loss
-- of significance due to catastrophic cancellation during summation.
-- <http://code.activestate.com/recipes/393090/> Also see the other
-- implementations given there. For Python's actual C implementation,
-- see math_fsum in
-- <http://svn.python.org/view/python/trunk/Modules/mathmodule.c?view=markup>
--
-- For merely *mitigating* errors rather than completely eliminating
-- them, see <http://code.activestate.com/recipes/298339/>.
--
-- A good test case is @msum([1, 1e100, 1, -1e100] * 10000) == 20000.0@
{-
-- For proof of correctness, see
-- <www-2.cs.cmu.edu/afs/cs/project/quake/public/papers/robust-arithmetic.ps>
def msum(xs):
    partials = [] # sorted, non-overlapping partial sums
    # N.B., the actual C implementation uses a 32 array, doubling size as needed
    for x in xs:
        i = 0
        for y in partials: # for(i = j = 0; j < n; j++)
            if abs(x) < abs(y):
                x, y = y, x
            hi = x + y
            lo = y - (hi - x)
            if lo != 0.0:
                partials[i] = lo
                i += 1
            x = hi
        # does an append of x while dropping all the partials after
        # i. The C version does n=i; and leaves the garbage in place
        partials[i:] = [x]
    # BUG: this last step isn't entirely correct and can lose
    # precision <http://stackoverflow.com/a/2704565/358069>
    return sum(partials, 0.0)
-}

----------------------------------------------------------------
----------------------------------------------------------- fin.