-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Log-domain floating point numbers
--   
--   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 probabilities as is done in Hidden Markov Models. It is also
--   helpful for preventing overflow.
@package logfloat
@version 0.13.3.3


-- | Hugs (September 2006) has buggy definitions for <a>isNaN</a> and
--   <a>isInfinite</a> on Float and Double. If this module is run through
--   CPP with the macro <tt><b>HUGS</b></tt> set to a value no larger than
--   200609, then correct definitions are used. Otherwise the Prelude
--   definitions are used (which should be correct for other compilers).
--   For example, run Hugs with
--   
--   <pre>
--   hugs -F'cpp -P -D<b>HUGS</b>=200609' Hugs/RealFloat.hs
--   </pre>
--   
--   N.B. The corrected definitions have only been tested to work for
--   <a>Float</a> and <a>Double</a>. These definitions should probably not
--   be used for other <a>RealFloat</a> types.
--   
--   <i>This installation was compiled with the normal Prelude version.
--   This should be correct.</i>
module Hugs.RealFloat
isInfinite :: (RealFloat a) => a -> Bool
isNaN :: (RealFloat a) => a -> Bool


-- | The Prelude's <a>Ord</a> class for dealing with ordered types is often
--   onerous to use because it requires <a>Eq</a> as well as a total
--   ordering. While such total orderings are common, partial orderings are
--   more so. This module presents a class for partially ordered types.
module Data.Number.PartialOrd

-- | This class defines a partially ordered type. The method names were
--   chosen so as not to conflict with <a>Ord</a> and <a>Eq</a>. We use
--   <a>Maybe</a> instead of defining new types <tt>PartialOrdering</tt>
--   and <tt>FuzzyBool</tt> because this way should make the class easier
--   to use.
--   
--   Minimum complete definition: <a>cmp</a>
class PartialOrd a where gt x y = case x `cmp` y of { Just GT -> Just True Just _ -> Just False Nothing -> Nothing } ge x y = case x `cmp` y of { Just LT -> Just False Just _ -> Just True Nothing -> Nothing } eq x y = case x `cmp` y of { Just EQ -> Just True Just _ -> Just False Nothing -> Nothing } ne x y = case x `cmp` y of { Just EQ -> Just False Just _ -> Just True Nothing -> Nothing } le x y = case x `cmp` y of { Just GT -> Just False Just _ -> Just True Nothing -> Nothing } lt x y = case x `cmp` y of { Just LT -> Just True Just _ -> Just False Nothing -> Nothing } maxPO x y = do { o <- x `cmp` y; case o of { GT -> Just x EQ -> Just x LT -> Just y } } minPO x y = do { o <- x `cmp` y; case o of { GT -> Just y EQ -> Just x LT -> Just x } }

-- | like <a>compare</a>
cmp :: PartialOrd a => a -> a -> Maybe Ordering

-- | like (<a>&gt;</a>)
gt :: PartialOrd a => a -> a -> Maybe Bool

-- | like (<a>&gt;=</a>)
ge :: PartialOrd a => a -> a -> Maybe Bool

-- | like (<a>==</a>)
eq :: PartialOrd a => a -> a -> Maybe Bool

-- | like (<a>/=</a>)
ne :: PartialOrd a => a -> a -> Maybe Bool

-- | like (<a>&lt;=</a>)
le :: PartialOrd a => a -> a -> Maybe Bool

-- | like (<a>&lt;</a>)
lt :: PartialOrd a => a -> a -> Maybe Bool

-- | like <a>max</a>. The default instance returns the left argument when
--   they're equal.
maxPO :: PartialOrd a => a -> a -> Maybe a

-- | like <a>min</a>. The default instance returns the left argument when
--   they're equal.
minPO :: PartialOrd a => a -> a -> Maybe a

-- | Like <tt>Data.Ord.comparing</tt>. Helpful in conjunction with the
--   <tt>xxxBy</tt> family of functions from <a>Data.List</a>
comparingPO :: (PartialOrd b) => (a -> b) -> a -> a -> Maybe Ordering
instance GHC.Classes.Ord a => Data.Number.PartialOrd.PartialOrd a
instance Data.Number.PartialOrd.PartialOrd GHC.Types.Float
instance Data.Number.PartialOrd.PartialOrd GHC.Types.Double


-- | 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
--   <a>Data.Number.LogFloat</a>. However not all <a>Fractional</a> types
--   necessarily support transfinite values. In particular, <tt>Ratio</tt>
--   types including <a>Rational</a> do not have portable representations.
--   
--   For the Glasgow compiler (GHC 6.8.2), <a>GHC.Real</a> defines
--   <tt>1%0</tt> and <tt>0%0</tt> as representations for <a>infinity</a>
--   and <a>notANumber</a>, but most operations on them will raise
--   exceptions. If <a>toRational</a> 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 <tt>Double</tt>. If
--   used on NaN, the result would buggily convert back as
--   <a>negativeInfinity</a>. For more discussion on why this approach is
--   problematic, see:
--   
--   <ul>
--   
--   <li><a>http://www.haskell.org/pipermail/haskell-prime/2006-February/000791.html</a></li>
--   
--   <li><a>http://www.haskell.org/pipermail/haskell-prime/2006-February/000821.html</a></li>
--   </ul>
--   
--   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

-- | Many numbers are not <a>Bounded</a> 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 <a>Fractional</a> nor
--   <a>Floating</a> since integral types could also have representations
--   for transfinite values. By popular demand the <a>Num</a> restriction
--   has been lifted as well, due to complications of defining <a>Show</a>
--   or <a>Eq</a> for some types.
--   
--   In particular, this class extends the ordered projection to have a
--   maximum value <a>infinity</a> and a minimum value
--   <a>negativeInfinity</a>, as well as an exceptional value
--   <a>notANumber</a>. All the natural laws regarding <tt>infinity</tt>
--   and <tt>negativeInfinity</tt> should pertain. (Some of these are
--   discussed below.)
--   
--   Hugs (September 2006) has buggy Prelude definitions for <a>isNaN</a>
--   and <a>isInfinite</a> on Float and Double. This module provides
--   correct definitions, so long as <a>Hugs.RealFloat</a> is compiled
--   correctly.
class (PartialOrd a) => Transfinite a

-- | 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 <tt>infinity</tt>), and dividing by
--   any positive finite value. Also obeys the law <tt>negate infinity =
--   negativeInfinity</tt> with all appropriate ramifications.
infinity :: Transfinite a => a

-- | A transfinite value which is less than all finite values. Obeys all
--   the same laws as <tt>infinity</tt> with the appropriate changes for
--   the sign difference.
negativeInfinity :: Transfinite a => a

-- | An exceptional transfinite value for dealing with undefined results
--   when manipulating infinite values. The following operations must
--   return <tt>notANumber</tt>, where <tt>inf</tt> is any value which
--   <tt>isInfinite</tt>:
--   
--   <ul>
--   <li><pre>infinity + negativeInfinity</pre></li>
--   <li><pre>negativeInfinity + infinity</pre></li>
--   <li><pre>infinity - infinity</pre></li>
--   <li><pre>negativeInfinity - negativeInfinity</pre></li>
--   <li><pre>inf * 0</pre></li>
--   <li><pre>0 * inf</pre></li>
--   <li><pre>inf / inf</pre></li>
--   <li><pre>inf `div` inf</pre></li>
--   <li><pre>0 / 0</pre></li>
--   <li><pre>0 `div` 0</pre></li>
--   </ul>
--   
--   Additionally, any mathematical operations on <tt>notANumber</tt> must
--   also return <tt>notANumber</tt>, and any equality or ordering
--   comparison on <tt>notANumber</tt> must return <tt>False</tt>
--   (violating the law of the excluded middle, often assumed but not
--   required for <a>Eq</a>; thus, <a>eq</a> and <a>ne</a> are preferred
--   over (<a>==</a>) and (<a>/=</a>)). Since it returns false for
--   equality, there may be more than one machine representation of this
--   <tt>value</tt>.
notANumber :: Transfinite a => a

-- | Return true for both <tt>infinity</tt> and <tt>negativeInfinity</tt>,
--   false for all other values.
isInfinite :: Transfinite a => a -> Bool

-- | Return true only for <tt>notANumber</tt>.
isNaN :: Transfinite a => a -> Bool

-- | Since the normal <a>log</a> throws an error on zero, we have to
--   redefine it in order for things to work right. Arguing from limits we
--   can see that <tt>log 0 == negativeInfinity</tt>. Newer versions of GHC
--   have this behavior already, but older versions and Hugs do not.
--   
--   This function will raise an error when taking the log of negative
--   numbers, rather than returning <a>notANumber</a> as the newer GHC
--   implementation does. The reason being that typically this is a logical
--   error, and <tt>notANumber</tt> allows the error to propagate silently.
--   
--   In order to improve portability, the <a>Transfinite</a> class is
--   required to indicate that the <a>Floating</a> type does in fact have a
--   representation for negative infinity. Both native floating types
--   (<a>Double</a> and <a>Float</a>) are supported. If you define your own
--   instance of <tt>Transfinite</tt>, verify the above equation holds for
--   your <tt>0</tt> and <tt>negativeInfinity</tt>. If it doesn't, then you
--   should avoid importing our <tt>log</tt> and will probably want
--   converters to handle the discrepancy.
--   
--   For GHC, this version of <tt>log</tt> has rules for fusion with
--   <tt>exp</tt>. These can give different behavior by preventing overflow
--   to <tt>infinity</tt> and preventing errors for taking the logarithm of
--   negative values. For <a>Double</a> and <a>Float</a> they can also give
--   different answers due to eliminating floating point fuzz. The rules
--   strictly improve mathematical accuracy, however they should be noted
--   in case your code depends on the implementation details.
log :: (Floating a, Transfinite a) => a -> a
instance Data.Number.Transfinite.Transfinite GHC.Types.Double
instance Data.Number.Transfinite.Transfinite GHC.Types.Float


-- | This module presents a type class for generic conversion between
--   numeric types, generalizing <tt>realToFrac</tt> in order to overcome
--   problems with pivoting through <a>Rational</a>
module Data.Number.RealToFrac

-- | The <a>realToFrac</a> function is defined to pivot through a
--   <a>Rational</a> according to the haskell98 spec. This is non-portable
--   and problematic as discussed in <a>Data.Number.Transfinite</a>. Since
--   there is resistance to breaking from the spec, this class defines a
--   reasonable variant which deals with transfinite values appropriately.
--   
--   There is a generic instance from any Transfinite Real to any
--   Transfinite Fractional, using checks to ensure correctness. GHC has
--   specialized versions for some types which use primitive converters
--   instead, for large performance gains. (These definitions are hidden
--   from other compilers via CPP.) Due to a bug in Haddock the specialized
--   instances are shown twice and the generic instance isn't shown at all.
--   Since the instances are overlapped, you'll need to give type
--   signatures if the arguments to <a>realToFrac</a> are polymorphic.
--   There's also a generic instance for any Real Fractional type to
--   itself, thus if you write any generic instances beware of incoherence.
--   
--   If any of these restrictions (CPP, GHC-only optimizations,
--   OverlappingInstances) are onerous to you, contact the maintainer (we
--   like patches). Note that this <i>does</i> work for Hugs with suitable
--   options (e.g. <tt>hugs -98 +o -F'cpp -P'</tt>). However, Hugs doesn't
--   allow <tt>IncoherentInstances</tt> nor does it allow diamonds with
--   <tt>OverlappingInstances</tt>, which restricts the ability to add
--   additional generic instances.
class (Real a, Fractional b) => RealToFrac a b
realToFrac :: RealToFrac a b => a -> b
instance (GHC.Real.Real a, GHC.Real.Fractional a) => Data.Number.RealToFrac.RealToFrac a a
instance (GHC.Real.Real a, Data.Number.Transfinite.Transfinite a, GHC.Real.Fractional b, Data.Number.Transfinite.Transfinite b) => Data.Number.RealToFrac.RealToFrac a b
instance Data.Number.RealToFrac.RealToFrac GHC.Types.Int GHC.Types.Float
instance Data.Number.RealToFrac.RealToFrac GHC.Types.Int GHC.Types.Double
instance Data.Number.RealToFrac.RealToFrac GHC.Integer.Type.Integer GHC.Types.Float
instance Data.Number.RealToFrac.RealToFrac GHC.Integer.Type.Integer GHC.Types.Double
instance Data.Number.RealToFrac.RealToFrac GHC.Types.Float GHC.Types.Double
instance Data.Number.RealToFrac.RealToFrac GHC.Types.Double GHC.Types.Float


-- | 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 <i>O(n^3)</i> loop.
--   
--   The <a>LogFloat</a> of this module is restricted to non-negative
--   numbers for efficiency's sake, see <a>Data.Number.LogFloat.Signed</a>
--   for doing signed log-domain calculations.
module Data.Number.LogFloat

-- | A <tt>LogFloat</tt> is just a <a>Double</a> with a special
--   interpretation. The <a>logFloat</a> function is presented instead of
--   the constructor, in order to ensure semantic conversion. At present
--   the <a>Show</a> instance will convert back to the normal-domain, and
--   hence will underflow at that point. This behavior may change in the
--   future.
--   
--   Because <a>logFloat</a> 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:
--   
--   <pre>
--   logFloat (p + q) == logFloat p + logFloat q
--   logFloat (p * q) == logFloat p * logFloat q
--   </pre>
--   
--   (Do note, however, that subtraction can and negation will throw
--   errors: since <tt>LogFloat</tt> can only represent the positive half
--   of <a>Double</a>. <a>Num</a> 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 <tt>lp * logFloat q * logFloat
--   r</tt> it's faster to do <tt>lp * logFloat (q * r)</tt> 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 <a>product</a>
--   rather than using '(*)' repeatedly.
--   
--   Even more particularly, you should <i>avoid addition</i> whenever
--   possible. Addition is provided because sometimes we need it, and the
--   proper implementation is not immediately apparent. However, between
--   two <tt>LogFloat</tt>s addition requires crossing the exp/log boundary
--   twice; with a <tt>LogFloat</tt> and a <a>Double</a> 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!
--   
--   <ul>
--   <li><i>1</i> That is, true up-to underflow and floating point
--   fuzziness. Which is, of course, the whole point of this module.</li>
--   </ul>
data LogFloat

-- | Constructor which does semantic conversion from normal-domain to
--   log-domain. Throws errors on negative and NaN inputs. If <tt>p</tt> is
--   non-negative, then following equivalence holds:
--   
--   <pre>
--   logFloat p == logToLogFloat (log p)
--   </pre>
--   
--   If <tt>p</tt> is NaN or negative, then the two sides differ only in
--   which error is thrown.
logFloat :: Double -> LogFloat

-- | Semantically convert our log-domain value back into the normal-domain.
--   Beware of overflow/underflow. The following equivalence holds (without
--   qualification):
--   
--   <pre>
--   fromLogFloat == exp . logFromLogFloat
--   </pre>
fromLogFloat :: LogFloat -> Double

-- | Constructor which assumes the argument is already in the log-domain.
--   Throws errors on <tt>notANumber</tt> inputs.
logToLogFloat :: Double -> LogFloat

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

-- | <i>O(n)</i>. Compute the sum of a finite list of <a>LogFloat</a>s,
--   being careful to avoid underflow issues. That is, the following
--   equivalence holds (modulo underflow and all that):
--   
--   <pre>
--   logFloat . sum == sum . map logFloat
--   </pre>
--   
--   <i>N.B.</i>, 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.
--   
--   <i>Since: 0.13</i>
sum :: [LogFloat] -> LogFloat

-- | <i>O(n)</i>. Compute the product of a finite list of <a>LogFloat</a>s,
--   being careful to avoid numerical error due to loss of precision. That
--   is, the following equivalence holds (modulo underflow and all that):
--   
--   <pre>
--   logFloat . product == product . map logFloat
--   </pre>
--   
--   <i>Since: 0.13</i>
product :: [LogFloat] -> LogFloat

-- | <i>O(1)</i>. Compute powers in the log-domain; that is, the following
--   equivalence holds (modulo underflow and all that):
--   
--   <pre>
--   logFloat (p ** m) == logFloat p `pow` m
--   </pre>
--   
--   <i>Since: 0.13</i>
pow :: LogFloat -> Double -> LogFloat
infixr 8 `pow`

-- | Definition: <tt>log1p == log . (1+)</tt>. Standard C libraries provide
--   a special definition for <a>log1p</a> which is more accurate than
--   doing the naive thing, especially for very small arguments. For
--   example, the naive version underflows around <tt>2 ** -53</tt>,
--   whereas the specialized version underflows around <tt>2 ** -1074</tt>.
--   This function is used by (<a>+</a>) and (<a>-</a>) on
--   <tt>LogFloat</tt>.
--   
--   N.B. The <tt>statistics:Statistics.Math</tt> module provides a pure
--   Haskell implementation of <tt>log1p</tt> for those who are interested.
--   We do not copy it here because it relies on the <tt>vector</tt>
--   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.
--   
--   <i>This installation was compiled to use the FFI version.</i>
log1p :: Double -> Double

-- | Definition: <tt>expm1 == subtract 1 . exp</tt>. Standard C libraries
--   provide a special definition for <a>expm1</a> 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
--   <a>log1p</a>.
--   
--   <i>This installation was compiled to use the FFI version.</i>
expm1 :: Double -> Double
instance Foreign.Storable.Storable Data.Number.LogFloat.LogFloat
instance GHC.Classes.Ord Data.Number.LogFloat.LogFloat
instance GHC.Classes.Eq Data.Number.LogFloat.LogFloat
instance Data.Array.Base.IArray Data.Array.Base.UArray Data.Number.LogFloat.LogFloat
instance Data.Number.PartialOrd.PartialOrd Data.Number.LogFloat.LogFloat
instance GHC.Show.Show Data.Number.LogFloat.LogFloat
instance GHC.Num.Num Data.Number.LogFloat.LogFloat
instance GHC.Real.Fractional Data.Number.LogFloat.LogFloat
instance GHC.Real.Real Data.Number.LogFloat.LogFloat
