logfloat 0.8.3 → 0.8.4

raw patch · 4 files changed

+187/−113 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Data/Number/LogFloat.hs +41/−56
• Data/Number/LogFloat.lhs +41/−56
• Data/Number/Transfinite.hs +103/−0
• logfloat.cabal +2/−1

@@ -16,9 +16,13 @@  -- {-# OPTIONS_GHC -ddump-simpl-stats #-} +{-# OPTIONS_GHC -Wall -Werror        #-} {-# OPTIONS_GHC -O2 -fvia-C -optc-O3 #-}  -- Version History+-- (v0.8.4) Broke out Transfinite+-- (v0.8.3) Documentation updates+-- (v0.8.2) Announced release -- (v0.8) Did a bunch of tweaking. Things should be decent now -- (v0.7) Haddockified -- (v0.6) Fixed monomorphism.@@ -29,7 +33,7 @@ -- (v0.1) Initial version created for hw5 for NLP with Jason Eisner. -- -------------------------------------------------------------------                                                     ~ 2008.08.15+--                                                     ~ 2008.08.16 -- | -- Module      :  Data.Number.LogFloat -- Copyright   :  Copyright (c) 2007--2008 wren ng thornton@@ -38,7 +42,7 @@ -- Stability   :  stable -- Portability :  portable ----- This module presents a class for storing numbers in the log-domain.+-- 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.@@ -62,43 +66,31 @@     -- or see:     -- <http://code.haskell.org/~wren/logfloat/dist/doc/html/logfloat/> -    -- * IEEE floating-point special values-    -- | "GHC.Real" defines 'infinity' and 'notANumber' as-    -- 'Rational'. We export variants which are polymorphic because-    -- that can be more helpful at times.-    -- -    -- BUG: At present these constants are broken for @Ratio@-    -- types including 'Rational', since @Ratio@ types do not-    -- typically permit a zero denominator. In GHC (6.8.2) the-    -- result for 'infinity' is a rational with a numerator-    -- sufficiently large that 'fromRational' will yield infinity-    -- for @Float@ and @Double@. In Hugs (September 2006) it-    -- yields an arithmetic overflow error. For GHC, our 'notANumber'-    -- yields @0%1@ rather than @0%0@ as "GHC.Real" does.--      infinity, negativeInfinity, notANumber-     -- * Basic functions-    , log, toFractional+      log, toFractional      -- * @LogFloat@ data type and conversion functions     , LogFloat     , logFloat,     logToLogFloat     , fromLogFloat, logFromLogFloat++    -- * Exceptional numeric values+    , module Data.Number.Transfinite     ) where -import Prelude hiding (log)-import qualified Prelude (log)+import Prelude hiding    (log, isNaN)+import qualified Prelude (log, isNaN) --- Not portable, and we can do it ourselves.--- import qualified GHC.Real (infinity, notANumber)+import Data.Number.Transfinite  ---------------------------------------------------------------- -- -- Try to add in some optimizations. Why the first few need to be down -- here and localized to the module, I don't know. We don't do anything--- foolish like this, but our clients might or they might be generated--- by other code transformations.+-- foolish like this, but our clients might, or they might be generated+-- by other code transformations. Note that due to the fuzz, these+-- equations are not actually true, even though they are mathematically+-- correct.  {-# RULES "log/exp"  forall x. log (exp x) = x@@ -110,7 +102,7 @@  -- These are general rule versions of our operators for 'LogFloat'. I -- had some issues inducing 'Ord' on @x@ and @y@, even though they're--- 'Num' so I can't do "(+)/log" and "(-)/log" so easily.+-- 'Num' so I can't do "(+)\/log" and "(-)\/log" so easily.  {-# RULES "(*)/log"  forall x y. log x * log y = log (x + y)@@ -120,37 +112,30 @@  ---------------------------------------------------------------- ----- The type signature is necessary for them not to default to Double.--infinity, negativeInfinity, notANumber :: (Fractional a) => a-infinity         = toFractional (1/0)  -- == fromRational GHC.Real.infinity-{-# SPECIALIZE negativeInfinity :: Double #-}-negativeInfinity = negate infinity-notANumber       = infinity - infinity -- == fromRational GHC.Real.notANumber---- The dictionaries for these are really ugly in core.--- TODO: be sure to check that these don't give eggregious performance hits----------------------------------------------------------------------- -- | Since the normal 'Prelude.log' throws an error on zero, we have -- to redefine it in order for things to work right. Arguing from--- limits it's obvious that @log 0 == negativeInfinity@.+-- limits we can see that @log 0 == negativeInfinity@. ----- If you're using some 'Floating' type that's not built in, verify--- this equation holds for your @0@ and @negativeInfinity@. If it--- doesn't, then you should avoid importing our 'log' and will probably--- want converters to handle the discrepency.+-- In order to improve portability, the 'Transfinite' class is required+-- to indicate that the 'Floating' type does in fact have a representation+-- for negative infinity. Both native @Floating@ types ('Double' and+-- 'Float') are supported. If you define your own instance of+-- @Transfinite@, verify the above equation holds for your @0@ and+-- @negativeInfinity@. If it doesn't, then you should avoid importing+-- our @log@ and will probably want converters to handle the discrepancy+-- when dealing with @LogFloat@s.  {-# SPECIALIZE log :: Double -> Double #-}-log  :: (Floating a) => a -> a+log  :: (Floating a, Transfinite a) => a -> a log 0 = negativeInfinity log x = Prelude.log x   -- | The most generic numeric converter I can come up with. All the -- built-in numeric types are 'Real', though 'Int' and 'Integer' aren't--- 'Fractional'.+-- 'Fractional'. Beware that converting transfinite values into @Ratio@+-- types is error-prone and non-portable, as discussed in+-- "Data.Number.Transfinite".  {-# SPECIALIZE toFractional :: (Real a)       => a -> Double #-} {-# SPECIALIZE toFractional :: (Fractional b) => Double -> b #-}@@ -190,8 +175,8 @@ -- fun = guardIsANumber fun . log@ in order to remove guardNonNegative.  guardIsANumber        :: String -> Double -> Double-guardIsANumber   fun x | x >= negativeInfinity = x-                       | otherwise             = errorOutOfRange fun+guardIsANumber   fun x | Prelude.isNaN x = errorOutOfRange fun+                       | otherwise       = x  ---------------------------------------------------------------- --@@ -213,7 +198,7 @@ -- Even more particularly, you should /avoid addition/ whenever possible. -- Addition is provided because it's necessary at times and the proper -- implementation is not immediately transparent. However, between two--- @LogFloat@s addition requires crossing the exp/log boundary twice;+-- @LogFloat@s addition requires crossing the exp\/log boundary twice; -- with a @LogFloat@ and a regular number 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 plain operations@@ -235,7 +220,7 @@ -- constructor. We present it mainly because we hide the constructor -- in order to make the type a bit more opaque. If the polymorphism -- turns out to be a performance liability because the rewrite rules--- can't remove it, then we need to rethink all four constructors/destructors.+-- can't remove it, then we need to rethink all four constructors\/destructors. -- -- | Constructor which assumes the argument is already in the log-domain. @@ -245,21 +230,21 @@   -- | Return our log-domain value back into normal-domain. Beware of--- overflow/underflow.+-- overflow\/underflow.  {-# SPECIALIZE fromLogFloat :: LogFloat -> Double #-}-fromLogFloat :: (Floating a) => LogFloat -> a+fromLogFloat :: (Fractional a, Transfinite a) => LogFloat -> a fromLogFloat (LogFloat x) = toFractional (exp x)   -- | Return the log-domain value itself without costly conversion  {-# SPECIALIZE logFromLogFloat :: LogFloat -> Double #-}-logFromLogFloat :: (Floating a) => LogFloat -> a+logFromLogFloat :: (Fractional a, Transfinite a) => LogFloat -> a logFromLogFloat (LogFloat x) = toFractional x  --- These are our module-specific versions of "log/exp" and "exp/log";+-- 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. @@ -281,7 +266,7 @@ -- 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+-- 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. @@ -296,7 +281,7 @@ -- 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.+-- many large numbers) so we're not too worried about +\/- 4e-16.  instance Num LogFloat where      (*) (LogFloat x) (LogFloat y) = LogFloat (x+y)

@@ -16,9 +16,13 @@  > -- {-# OPTIONS_GHC -ddump-simpl-stats #-} >+> {-# OPTIONS_GHC -Wall -Werror        #-} > {-# OPTIONS_GHC -O2 -fvia-C -optc-O3 #-}  Version History+(v0.8.4) Broke out Transfinite+(v0.8.3) Documentation updates+(v0.8.2) Announced release (v0.8) Did a bunch of tweaking. Things should be decent now (v0.7) Haddockified (v0.6) Fixed monomorphism.@@ -29,7 +33,7 @@ (v0.1) Initial version created for hw5 for NLP with Jason Eisner.  -----------------------------------------------------------------                                                    ~ 2008.08.15+                                                    ~ 2008.08.16 | Module      :  Data.Number.LogFloat Copyright   :  Copyright (c) 2007--2008 wren ng thornton@@ -38,7 +42,7 @@ Stability   :  stable Portability :  portable -This module presents a class for storing numbers in the log-domain.+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.@@ -62,43 +66,31 @@ >     -- or see: >     -- <http://code.haskell.org/~wren/logfloat/dist/doc/html/logfloat/> >->     -- * IEEE floating-point special values->     -- | "GHC.Real" defines 'infinity' and 'notANumber' as->     -- 'Rational'. We export variants which are polymorphic because->     -- that can be more helpful at times.->     -- ->     -- BUG: At present these constants are broken for @Ratio@->     -- types including 'Rational', since @Ratio@ types do not->     -- typically permit a zero denominator. In GHC (6.8.2) the->     -- result for 'infinity' is a rational with a numerator->     -- sufficiently large that 'fromRational' will yield infinity->     -- for @Float@ and @Double@. In Hugs (September 2006) it->     -- yields an arithmetic overflow error. For GHC, our 'notANumber'->     -- yields @0%1@ rather than @0%0@ as "GHC.Real" does.->->       infinity, negativeInfinity, notANumber-> >     -- * Basic functions->     , log, toFractional+>       log, toFractional > >     -- * @LogFloat@ data type and conversion functions >     , LogFloat >     , logFloat,     logToLogFloat >     , fromLogFloat, logFromLogFloat+>+>     -- * Exceptional numeric values+>     , module Data.Number.Transfinite >     ) where > -> import Prelude hiding (log)-> import qualified Prelude (log)+> import Prelude hiding    (log, isNaN)+> import qualified Prelude (log, isNaN) >-> -- Not portable, and we can do it ourselves.-> -- import qualified GHC.Real (infinity, notANumber)+> import Data.Number.Transfinite  ----------------------------------------------------------------  Try to add in some optimizations. Why the first few need to be down here and localized to the module, I don't know. We don't do anything-foolish like this, but our clients might or they might be generated-by other code transformations.+foolish like this, but our clients might, or they might be generated+by other code transformations. Note that due to the fuzz, these+equations are not actually true, even though they are mathematically+correct.  > {-# RULES > "log/exp"  forall x. log (exp x) = x@@ -110,7 +102,7 @@  These are general rule versions of our operators for 'LogFloat'. I had some issues inducing 'Ord' on @x@ and @y@, even though they're-'Num' so I can't do "(+)/log" and "(-)/log" so easily.+'Num' so I can't do "(+)\/log" and "(-)\/log" so easily.  > {-# RULES > "(*)/log"  forall x y. log x * log y = log (x + y)@@ -120,37 +112,30 @@  ---------------------------------------------------------------- -The type signature is necessary for them not to default to Double.--> infinity, negativeInfinity, notANumber :: (Fractional a) => a-> infinity         = toFractional (1/0)  -- == fromRational GHC.Real.infinity-> {-# SPECIALIZE negativeInfinity :: Double #-}-> negativeInfinity = negate infinity-> notANumber       = infinity - infinity -- == fromRational GHC.Real.notANumber--The dictionaries for these are really ugly in core.-TODO: be sure to check that these don't give eggregious performance hits------------------------------------------------------------------- | Since the normal 'Prelude.log' throws an error on zero, we have to redefine it in order for things to work right. Arguing from-limits it's obvious that @log 0 == negativeInfinity@.+limits we can see that @log 0 == negativeInfinity@. -If you're using some 'Floating' type that's not built in, verify-this equation holds for your @0@ and @negativeInfinity@. If it-doesn't, then you should avoid importing our 'log' and will probably-want converters to handle the discrepency.+In order to improve portability, the 'Transfinite' class is required+to indicate that the 'Floating' type does in fact have a representation+for negative infinity. Both native @Floating@ types ('Double' and+'Float') are supported. If you define your own instance of+@Transfinite@, verify the above equation holds for your @0@ and+@negativeInfinity@. If it doesn't, then you should avoid importing+our @log@ and will probably want converters to handle the discrepancy+when dealing with @LogFloat@s.  > {-# SPECIALIZE log :: Double -> Double #-}-> log  :: (Floating a) => a -> a+> log  :: (Floating a, Transfinite a) => a -> a > log 0 = negativeInfinity > log x = Prelude.log x   | The most generic numeric converter I can come up with. All the built-in numeric types are 'Real', though 'Int' and 'Integer' aren't-'Fractional'.+'Fractional'. Beware that converting transfinite values into @Ratio@+types is error-prone and non-portable, as discussed in+"Data.Number.Transfinite".  > {-# SPECIALIZE toFractional :: (Real a)       => a -> Double #-} > {-# SPECIALIZE toFractional :: (Fractional b) => Double -> b #-}@@ -190,8 +175,8 @@ fun = guardIsANumber fun . log@ in order to remove guardNonNegative.  > guardIsANumber        :: String -> Double -> Double-> guardIsANumber   fun x | x >= negativeInfinity = x->                        | otherwise             = errorOutOfRange fun+> guardIsANumber   fun x | Prelude.isNaN x = errorOutOfRange fun+>                        | otherwise       = x  ---------------------------------------------------------------- @@ -213,7 +198,7 @@ Even more particularly, you should /avoid addition/ whenever possible. Addition is provided because it's necessary at times and the proper implementation is not immediately transparent. However, between two-@LogFloat@s addition requires crossing the exp/log boundary twice;+@LogFloat@s addition requires crossing the exp\/log boundary twice; with a @LogFloat@ and a regular number 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 plain operations@@ -235,7 +220,7 @@ constructor. We present it mainly because we hide the constructor in order to make the type a bit more opaque. If the polymorphism turns out to be a performance liability because the rewrite rules-can't remove it, then we need to rethink all four constructors/destructors.+can't remove it, then we need to rethink all four constructors\/destructors.  | Constructor which assumes the argument is already in the log-domain. @@ -245,21 +230,21 @@   | Return our log-domain value back into normal-domain. Beware of-overflow/underflow.+overflow\/underflow.  > {-# SPECIALIZE fromLogFloat :: LogFloat -> Double #-}-> fromLogFloat :: (Floating a) => LogFloat -> a+> fromLogFloat :: (Fractional a, Transfinite a) => LogFloat -> a > fromLogFloat (LogFloat x) = toFractional (exp x)   | Return the log-domain value itself without costly conversion  > {-# SPECIALIZE logFromLogFloat :: LogFloat -> Double #-}-> logFromLogFloat :: (Floating a) => LogFloat -> a+> logFromLogFloat :: (Fractional a, Transfinite a) => LogFloat -> a > logFromLogFloat (LogFloat x) = toFractional x  -These are our module-specific versions of "log/exp" and "exp/log";+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. @@ -281,7 +266,7 @@ 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+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. @@ -296,7 +281,7 @@ 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.+many large numbers) so we're not too worried about +\/- 4e-16.  > instance Num LogFloat where  >     (*) (LogFloat x) (LogFloat y) = LogFloat (x+y)

@@ -0,0 +1,103 @@++{-# OPTIONS_GHC -Wall -Werror #-}++----------------------------------------------------------------+--                                                  ~ 2008.08.16+-- |+-- Module      :  Data.Number.Transfinite+-- Copyright   :  Copyright (c) 2007--2008 wren ng thornton+-- License     :  BSD3+-- Maintainer  :  wren@community.haskell.org+-- Stability   :  stable+-- Portability :  portable+-- +-- This module presents a type class for numbers which have+-- representations for transfinite values. The idea originated from+-- the IEEE-754 floating-point special values, used by+-- "Data.Number.LogFloat". However not all 'Fractional' types+-- necessarily support transfinite values. In particular, @Ratio@+-- types including 'Rational' do not have portable representations.+-- +-- For the Glasgow compiler (GHC 6.8.2), "GHC.Real" defines @1%0@+-- and @0%0@ as representations for 'infinity' and 'notANumber',+-- but most operations on them will raise exceptions. If 'toRational'+-- is used on an infinite floating value, the result is a rational+-- with a numerator sufficiently large that it will overflow when+-- converted back to a @Double@. If used on NaN, the result would+-- convert back as 'negativeInfinity'.+-- +-- Hugs (September 2006) stays closer to the haskell98 spec and+-- offers no way of constructing those values, raising arithmetic+-- overflow errors if attempted.+----------------------------------------------------------------+module Data.Number.Transfinite (Transfinite(..)) where++import Prelude hiding    (isInfinite, isNaN)+import qualified Prelude (isInfinite, isNaN)++----------------------------------------------------------------+-- | Many numbers are not 'Bounded' yet, even though they can+-- represent arbitrarily large values, they are not necessarily+-- able to represent transfinite values such as infinity itself.+-- This class is for types which are capable of representing such+-- values. Notably, this class does not require the type to be+-- 'Fractional' nor 'Floating' since integral types could also have+-- representations for transfinite values.+--+-- In particular, this class extends the 'Ord' projection to have+-- a maximum value 'infinity' and a minimum value 'negativeInfinity',+-- as well as an exceptional value 'notANumber'. All the natural+-- laws regarding @infinity@ and @negativeInfinity@ should pertain.+-- Additionally, @infinity - infinity@ should return @notANumber@+-- (as should @0\/0@ and @infinity\/infinity@ if the type is+-- @Fractional@). Any operations on @notANumber@ will also return+-- @notANumber@, and any equality or ordering comparison on+-- @notANumber@ must return @False@.+--+-- Minimum complete definition is @infinity@, @isInfinite@, and+-- @isNaN@.++class (Num a, Ord a) => Transfinite a where+    +    -- | A transfinite value which is greater than all finite values.+    -- Adding or subtracting any finite value is a no-op. As is+    -- multiplying by any non-zero positive value (including+    -- @infinity@), and dividing by any positive finite value. Also+    -- obeys the law @negate infinity = negativeInfinity@ with all+    -- appropriate ramifications.+    infinity         :: a+    +    -- | A transfinite value which is less than all finite values.+    -- Obeys all the same laws as @infinity@ with the appropriate+    -- changes for the sign difference.+    negativeInfinity :: a+    negativeInfinity  = negate infinity+    +    -- | An exceptional transfinite value for dealing with undefined+    -- results when manipulating infinite values. Since NaN shall+    -- return false for all ordering and equality operations, there+    -- may be more than one machine representation of this `value'.+    notANumber       :: a+    notANumber        = infinity - infinity+    +    -- | Return true for both @infinity@ and @negativeInfinity@,+    -- false for all other values.+    isInfinite :: a -> Bool+    +    -- | Return true only for @notANumber@.+    isNaN      :: a -> Bool+++instance Transfinite Double where+    infinity   = 1 / 0+    isInfinite = Prelude.isInfinite+    isNaN      = Prelude.isNaN+++instance Transfinite Float where+    infinity   = 1 / 0+    isInfinite = Prelude.isInfinite+    isNaN      = Prelude.isNaN++----------------------------------------------------------------+----------------------------------------------------------- fin.

@@ -1,6 +1,6 @@ ---------------------------------------------------------------- Name:           logfloat-Version:        0.8.3+Version:        0.8.4 Cabal-Version:  >= 1.2 Build-Type:     Custom Stability:      stable@@ -20,6 +20,7 @@  Library     Exposed-Modules: Data.Number.LogFloat+                   , Data.Number.Transfinite     Build-Depends:   base     Ghc-Options:     -O2 -fvia-C -optc-O3