numeric-prelude 0.4.2 → 0.4.3
raw patch · 13 files changed
+327/−146 lines, 13 filesdep +semigroupsdep ~base
Dependencies added: semigroups
Dependency ranges changed: base
Files
- Makefile +3/−0
- README.md +139/−0
- docs/NOTES +2/−0
- numeric-prelude.cabal +13/−134
- src/Algebra/Additive.hs +8/−0
- src/Algebra/Module.hs +18/−1
- src/Algebra/RealRing.hs +118/−6
- src/MathObj/Polynomial.hs +2/−3
- src/MathObj/Polynomial/Core.hs +9/−1
- src/MathObj/PowerSeries.hs +6/−0
- src/Number/GaloisField2p32m5.hs +4/−0
- src/Number/NonNegativeChunky.hs +4/−0
- src/NumericPrelude/List.hs +1/−1
Makefile view
@@ -16,3 +16,6 @@ ghci-compile: $(HCI7) -Wall -i:src:test +RTS -M256m -c30 -RTS -fobject-code -O -hidir=dist/build -odir=dist/build test/Demo.hs++%.html: %.md+ pandoc $< --output=$@
+ README.md view
@@ -0,0 +1,139 @@+# Revisiting the Numeric Classes++## Introduction++The Prelude for Haskell 98 offers a well-considered set of numeric classes+which covers the standard numeric types+(`Integer`, `Int`, `Rational`, `Float`, `Double`, `Complex`) quite well.+But they offer limited extensibility and have a few other flaws.+In this proposal we will revisit these classes, addressing the following concerns:++1. The current Prelude defines no semantics for the fundamental operations.+ For instance, presumably addition should be associative+ (or come as close as feasible),+ but this is not mentioned anywhere.++2. There are some superfluous superclasses.+ For instance, `Eq` and `Show` are superclasses of `Num`.+ Consider the data type+ ` data IntegerFunction a = IF (a -> Integer) `.+ One can reasonably define all the methods of `Algebra.Ring.C` for+ `IntegerFunction a` (satisfying good semantics),+ but it is impossible to define non-bottom instances of `Eq` and `Show`.+ In general, superclass relationship should indicate+ some semantic connection between the two classes.++3. In a few cases, there is a mix of semantic operations and+ representation-specific operations.+ `toInteger`, `toRational`,+ and the various operations in `RealFloating` (`decodeFloat`, ...)+ are the main examples.++4. In some cases, the hierarchy is not finely-grained enough:+ Operations that are often defined independently are lumped together.+ For instance, in a financial application one might want a type "Dollar",+ or in a graphics application one might want a type "Vector".+ It is reasonable to add two Vectors or Dollars,+ but not, in general, reasonable to multiply them.+ But the programmer is currently forced to define a method for `(*)`+ when she defines a method for `(+)`.++In specifying the semantics of type classes,+I will state laws as follows:++~~~~+ (a + b) + c === a + (b + c)+~~~~++The intended meaning is extensional equality:+The rest of the program should behave in the same way+if one side is replaced with the other.+Unfortunately, the laws are frequently violated by standard instances;+the law above, for instance, fails for `Float`:++~~~~+ (1e20 + (-1e20)) + 1.0 = 1.0+ 1e20 + ((-1e20) + 1.0) = 0.0+~~~~++For inexact number types like floating point types,+thus these laws should be interpreted as guidelines rather than absolute rules.+In particular, the compiler is not allowed to use them for optimization.+Unless stated otherwise, default definitions should also be taken as laws.++Thanks to Brian Boutel, Joe English, William Lee Irwin II, Marcin+Kowalczyk, Ketil Malde, Tom Schrijvers, Ken Shan, and Henning+Thielemann for helpful comments.+++## Usage++Write modules in the following style:++~~~~+ {-# LANGUAGE RebindableSyntax #-}+ module MyModule where++ ... various specific imports ...++ import NumericPrelude+~~~~++Importing `NumericPrelude` is almost the same as++~~~~+ import NumericPrelude.Numeric+ import NumericPrelude.Base .+~~~~++Instead of the `NoImplicitPrelude` pragma+you could also write `import Prelude ()`+but this will yield problems with numeric literals.++There are two wrapper types that allow types+to be used with both Haskell98 and NumericPrelude type classes+that are initially implemented for only one of them.+++## Scope & Limitations/TODO++* It might be desireable to split `Ord` up into `Poset` and `Ord`+ (a total ordering).+ This is not addressed here.++* In some cases, this hierarchy may not yet be fine-grained enough.+ For instance, time spans ("5 minutes") can be added to times ("12:34"),+ but two times are not addable. ("12:34 + 8:23")+ As it stands,+ users have to use a different operator for adding time spans to times+ than for adding two time spans.+ Similar issues arise for vector space et al.+ This is a consciously-made tradeoff, but might be changed.+ This becomes most serious when dealing with quantities with units+ like `length/distance^2`, for which `(*)` as defined here is useless.+ (One way to see the issue: should+ ` f x y = iterate (x *) y `+ have principal type+ ` (Ring.C a) => a -> a -> [a] `+ or something like+ ` (Ring.C a, Module a b) => a -> b -> [b] `+ ?)++* I stuck with the Haskell 98 names.+ In some cases I find them lacking.+ Neglecting backwards compatibility, we have renamed classes as follows:++ ~~~~+ Num --> Additive, Ring, Absolute+ Integral --> ToInteger, IntegralDomain, RealIntegral+ Fractional --> Field+ Floating --> Algebraic, Transcendental+ Real --> ToRational+ RealFrac --> RealRing, RealField+ RealFloat --> RealTranscendental+ ~~~~+++Additional standard libraries might include `Enum`, `IEEEFloat`+(including the bulk of the functions in Haskell 98's `RealFloat` class),+`VectorSpace`, `Ratio`, and `Lattice`.
docs/NOTES view
@@ -1,5 +1,7 @@ * Positional: test suite +Test against 'compensated' package.+ * Positional and zero Represent zero with empty mantissa?
numeric-prelude.cabal view
@@ -1,5 +1,5 @@ Name: numeric-prelude-Version: 0.4.2+Version: 0.4.3 License: BSD3 License-File: LICENSE Author: Dylan Thurston <dpt@math.harvard.edu>, Henning Thielemann <numericprelude@henning-thielemann.de>, Mikael Johansson@@ -7,141 +7,20 @@ Homepage: http://www.haskell.org/haskellwiki/Numeric_Prelude Category: Math Stability: Experimental-Tested-With: GHC==6.4.1, GHC==6.8.2, GHC==6.10.4, GHC==6.12.3-Tested-With: GHC==7.2.2, GHC==7.4.1, GHC==7.6.3, GHC==7.8.4, GHC==7.10.1+Tested-With: GHC==7.4.2, GHC==7.6.3, GHC==7.8.4, GHC==7.10.3+Tested-With: GHC==8.4.1 Cabal-Version: >=1.8 Build-Type: Simple Synopsis: An experimental alternative hierarchy of numeric type classes Description:- Revisiting the Numeric Classes- .- The Prelude for Haskell 98 offers a well-considered set of numeric classes- which covers the standard numeric types- ('Integer', 'Int', 'Rational', 'Float', 'Double', 'Complex') quite well.- But they offer limited extensibility and have a few other flaws.- In this proposal we will revisit these classes, addressing the following concerns:- .- [1] The current Prelude defines no semantics for the fundamental operations.- For instance, presumably addition should be associative- (or come as close as feasible),- but this is not mentioned anywhere.- .- [2] There are some superfluous superclasses.- For instance, 'Eq' and 'Show' are superclasses of 'Num'.- Consider the data type- @ data IntegerFunction a = IF (a -> Integer) @- One can reasonably define all the methods of 'Algebra.Ring.C' for- @IntegerFunction a@ (satisfying good semantics),- but it is impossible to define non-bottom instances of 'Eq' and 'Show'.- In general, superclass relationship should indicate- some semantic connection between the two classes.- .- [3] In a few cases, there is a mix of semantic operations and- representation-specific operations.- 'toInteger', 'toRational',- and the various operations in 'RealFloating' ('decodeFloat', ...)- are the main examples.- .- [4] In some cases, the hierarchy is not finely-grained enough:- Operations that are often defined independently are lumped together.- For instance, in a financial application one might want a type \"Dollar\",- or in a graphics application one might want a type \"Vector\".- It is reasonable to add two Vectors or Dollars,- but not, in general, reasonable to multiply them.- But the programmer is currently forced to define a method for '(*)'- when she defines a method for '(+)'.- .- In specifying the semantics of type classes,- I will state laws as follows:- .- > (a + b) + c === a + (b + c)- .- The intended meaning is extensional equality:- The rest of the program should behave in the same way- if one side is replaced with the other.- Unfortunately, the laws are frequently violated by standard instances;- the law above, for instance, fails for 'Float':- .- > (1e20 + (-1e20)) + 1.0 = 1.0- > 1e20 + ((-1e20) + 1.0) = 0.0- .- For inexact number types like floating point types,- thus these laws should be interpreted as guidelines rather than absolute rules.- In particular, the compiler is not allowed to use them for optimization.- Unless stated otherwise, default definitions should also be taken as laws.- .- Thanks to Brian Boutel, Joe English, William Lee Irwin II, Marcin- Kowalczyk, Ketil Malde, Tom Schrijvers, Ken Shan, and Henning- Thielemann for helpful comments.- .- .- Usage:- .- Write modules in the following style:- .- > [-# LANGUAGE NoImplicitPrelude #-]- > module MyModule where- >- > ... various specific imports ...- >- > import NumericPrelude- .- Importing @NumericPrelude@ is almost the same as- .- > import NumericPrelude.Numeric- > import NumericPrelude.Base .- .- Instead of the @NoImplicitPrelude@ pragma- you could also write @import Prelude ()@- but this will yield problems with numeric literals.- .- There are two wrapper types that allow types- to be used with both Haskell98 and NumericPrelude type classes- that are initially implemented for only one of them.- .- .- Scope & Limitations\/TODO:- .- * It might be desireable to split Ord up into Poset and Ord- (a total ordering).- This is not addressed here.- .- * In some cases, this hierarchy may not yet be fine-grained enough.- For instance, time spans (\"5 minutes\") can be added to times (\"12:34\"),- but two times are not addable. (\"12:34 + 8:23\")- As it stands,- users have to use a different operator for adding time spans to times- than for adding two time spans.- Similar issues arise for vector space et al.- This is a consciously-made tradeoff, but might be changed.- This becomes most serious when dealing with quantities with units- like @length\/distance^2@, for which @(*)@ as defined here is useless.- (One way to see the issue: should- @ f x y = iterate (x *) y @- have principal type- @ (Ring.C a) => a -> a -> [a] @- or something like- @ (Ring.C a, Module a b) => a -> b -> [b] @- ?)- .- * I stuck with the Haskell 98 names.- In some cases I find them lacking.- Neglecting backwards compatibility, we have renamed classes as follows:- Num --> Additive, Ring, Absolute- Integral --> ToInteger, IntegralDomain, RealIntegral- Fractional --> Field- Floating --> Algebraic, Transcendental- Real --> ToRational- RealFrac --> RealRing, RealField- RealFloat --> RealTranscendental- .- .- Additional standard libraries might include Enum, IEEEFloat (including- the bulk of the functions in Haskell 98's RealFloat class),- VectorSpace, Ratio, and Lattice.+ The package provides an experimental alternative hierarchy+ of numeric type classes.+ The type classes are more oriented at mathematical structures+ and their methods come with laws that the instances must fulfill. Extra-Source-Files: Makefile+ README.md docs/NOTES docs/README src/Algebra/GenerateRules.hs@@ -151,13 +30,13 @@ default: False Source-Repository this- Tag: 0.4.2+ Tag: 0.4.3 Type: darcs- Location: http://code.haskell.org/numeric-prelude/+ Location: http://hub.darcs.net/thielema/numeric-prelude/ Source-Repository head Type: darcs- Location: http://code.haskell.org/numeric-prelude/+ Location: http://hub.darcs.net/thielema/numeric-prelude/ Library Build-Depends:@@ -165,15 +44,15 @@ QuickCheck >=1 && <3, storable-record >=0.0.1 && <0.1, non-negative >=0.0.5 && <0.2,+ semigroups >=0.1 && <1.0, utility-ht >=0.0.6 && <0.1, deepseq >=1.1 && <1.5 - -- splitBase Build-Depends: array >=0.1 && <0.6, containers >=0.1 && <0.6, random >=1.0 && <1.2,- base >= 2 && <5+ base >=4.5 && <5 If impl(ghc>=7.0) CPP-Options: -DNoImplicitPrelude=RebindableSyntax
src/Algebra/Additive.hs view
@@ -97,6 +97,7 @@ Sum up all elements of a non-empty list. This avoids including a zero which is useful for types where no universal zero is available.+ToDo: Should have NonEmpty type. -} sum1 :: (C a) => [a] -> a sum1 = foldl1 (+)@@ -365,6 +366,13 @@ negate = Elem.run $ pure (,,) <*>.-$ fst3 <*>.-$ snd3 <*>.-$ thd3 +{- |+The 'Additive' instantiations treat lists+as prefixes of infinite lists with zero filled tail.+This interpretation is not always appropriate.+The end of a list may just mean: End of available data.+In this case the shortening 'zip' semantics would be more appropriate.+-} instance (C v) => C [v] where zero = [] negate = map negate
src/Algebra/Module.hs view
@@ -29,6 +29,7 @@ import Control.Applicative (Applicative(pure, (<*>)), ) import qualified Data.Complex as Complex98+import Data.Int (Int, Int8, Int16, Int32, Int64, ) import Data.Function.HT (powerAssociative, ) import Data.List (map, zipWith, )@@ -36,7 +37,7 @@ import Data.Tuple (fst, snd, ) import qualified Prelude as P-import Prelude((.), Eq, Bool, Int, Integer, Float, Double, ($), )+import Prelude((.), Eq, Bool, Integer, Float, Double, ($), ) -- Is this right?@@ -82,6 +83,22 @@ (*>) = (*) instance C Int Int where+ {-# INLINE (*>) #-}+ (*>) = (*)++instance C Int8 Int8 where+ {-# INLINE (*>) #-}+ (*>) = (*)++instance C Int16 Int16 where+ {-# INLINE (*>) #-}+ (*>) = (*)++instance C Int32 Int32 where+ {-# INLINE (*>) #-}+ (*>) = (*)++instance C Int64 Int64 where {-# INLINE (*>) #-} (*>) = (*)
src/Algebra/RealRing.hs view
@@ -170,6 +170,20 @@ splitFraction (x:%y) = (fromIntegral q, r:%y) where (q,r) = divMod x y +instance C Integer where+ {-# INLINE splitFraction #-}+ {-# INLINE fraction #-}+ {-# INLINE floor #-}+ {-# INLINE ceiling #-}+ {-# INLINE round #-}+ {-# INLINE truncate #-}+ splitFraction x = (fromInteger x, zero)+ fraction _ = zero+ floor x = fromInteger x+ ceiling x = fromInteger x+ round x = fromInteger x+ truncate x = fromInteger x+ instance C Int where {-# INLINE splitFraction #-} {-# INLINE fraction #-}@@ -184,19 +198,117 @@ round x = fromIntegral x truncate x = fromIntegral x -instance C Integer where+instance C Int8 where {-# INLINE splitFraction #-} {-# INLINE fraction #-} {-# INLINE floor #-} {-# INLINE ceiling #-} {-# INLINE round #-} {-# INLINE truncate #-}- splitFraction x = (fromInteger x, zero)+ splitFraction x = (fromIntegral x, zero) fraction _ = zero- floor x = fromInteger x- ceiling x = fromInteger x- round x = fromInteger x- truncate x = fromInteger x+ floor x = fromIntegral x+ ceiling x = fromIntegral x+ round x = fromIntegral x+ truncate x = fromIntegral x++instance C Int16 where+ {-# INLINE splitFraction #-}+ {-# INLINE fraction #-}+ {-# INLINE floor #-}+ {-# INLINE ceiling #-}+ {-# INLINE round #-}+ {-# INLINE truncate #-}+ splitFraction x = (fromIntegral x, zero)+ fraction _ = zero+ floor x = fromIntegral x+ ceiling x = fromIntegral x+ round x = fromIntegral x+ truncate x = fromIntegral x++instance C Int32 where+ {-# INLINE splitFraction #-}+ {-# INLINE fraction #-}+ {-# INLINE floor #-}+ {-# INLINE ceiling #-}+ {-# INLINE round #-}+ {-# INLINE truncate #-}+ splitFraction x = (fromIntegral x, zero)+ fraction _ = zero+ floor x = fromIntegral x+ ceiling x = fromIntegral x+ round x = fromIntegral x+ truncate x = fromIntegral x++instance C Int64 where+ {-# INLINE splitFraction #-}+ {-# INLINE fraction #-}+ {-# INLINE floor #-}+ {-# INLINE ceiling #-}+ {-# INLINE round #-}+ {-# INLINE truncate #-}+ splitFraction x = (fromIntegral x, zero)+ fraction _ = zero+ floor x = fromIntegral x+ ceiling x = fromIntegral x+ round x = fromIntegral x+ truncate x = fromIntegral x++instance C Word8 where+ {-# INLINE splitFraction #-}+ {-# INLINE fraction #-}+ {-# INLINE floor #-}+ {-# INLINE ceiling #-}+ {-# INLINE round #-}+ {-# INLINE truncate #-}+ splitFraction x = (fromIntegral x, zero)+ fraction _ = zero+ floor x = fromIntegral x+ ceiling x = fromIntegral x+ round x = fromIntegral x+ truncate x = fromIntegral x++instance C Word16 where+ {-# INLINE splitFraction #-}+ {-# INLINE fraction #-}+ {-# INLINE floor #-}+ {-# INLINE ceiling #-}+ {-# INLINE round #-}+ {-# INLINE truncate #-}+ splitFraction x = (fromIntegral x, zero)+ fraction _ = zero+ floor x = fromIntegral x+ ceiling x = fromIntegral x+ round x = fromIntegral x+ truncate x = fromIntegral x++instance C Word32 where+ {-# INLINE splitFraction #-}+ {-# INLINE fraction #-}+ {-# INLINE floor #-}+ {-# INLINE ceiling #-}+ {-# INLINE round #-}+ {-# INLINE truncate #-}+ splitFraction x = (fromIntegral x, zero)+ fraction _ = zero+ floor x = fromIntegral x+ ceiling x = fromIntegral x+ round x = fromIntegral x+ truncate x = fromIntegral x++instance C Word64 where+ {-# INLINE splitFraction #-}+ {-# INLINE fraction #-}+ {-# INLINE floor #-}+ {-# INLINE ceiling #-}+ {-# INLINE round #-}+ {-# INLINE truncate #-}+ splitFraction x = (fromIntegral x, zero)+ fraction _ = zero+ floor x = fromIntegral x+ ceiling x = fromIntegral x+ round x = fromIntegral x+ truncate x = fromIntegral x instance C Float where {-# INLINE splitFraction #-}
src/MathObj/Polynomial.hs view
@@ -270,11 +270,10 @@ lift1 $ foldr (\c p -> [c] + Core.mulLinearFactor d p) [] shrink :: Ring.C a => a -> T a -> T a-shrink k =- lift1 $ zipWith (*) (iterate (k*) one)+shrink = lift1 . Core.shrink dilate :: Field.C a => a -> T a -> T a-dilate = shrink . Field.recip+dilate = lift1 . Core.dilate instance (Arbitrary a, ZeroTestable.C a) => Arbitrary (T a) where
src/MathObj/Polynomial/Core.hs view
@@ -21,7 +21,7 @@ stdUnit, progression, differentiate, integrate, integrateInt, mulLinearFactor,- alternate,+ alternate, dilate, shrink, ) where import qualified Algebra.Module as Module@@ -211,6 +211,14 @@ {-# INLINE alternate #-} alternate :: Additive.C a => [a] -> [a] alternate = zipWith ($) (cycle [id, Additive.negate])++{-# INLINE shrink #-}+shrink :: Ring.C a => a -> [a] -> [a]+shrink k = zipWith (*) (iterate (k*) one)++{-# INLINE dilate #-}+dilate :: Field.C a => a -> [a] -> [a]+dilate = shrink . Field.recip {-
src/MathObj/PowerSeries.hs view
@@ -189,3 +189,9 @@ if isZero y then Cons (Core.compose x ys) else error "PowerSeries.compose: inner series must not have an absolute term."++shrink :: Ring.C a => a -> T a -> T a+shrink = lift1 . Poly.shrink++dilate :: Field.C a => a -> T a -> T a+dilate = lift1 . Poly.dilate
src/Number/GaloisField2p32m5.hs view
@@ -12,6 +12,7 @@ module Number.GaloisField2p32m5 where import qualified Number.ResidueClass as RC+import qualified Algebra.ZeroTestable as ZeroTestable import qualified Algebra.Module as Module import qualified Algebra.Field as Field import qualified Algebra.Ring as Ring@@ -90,3 +91,6 @@ instance Module.C T T where (*>) = (*)++instance ZeroTestable.C T where+ isZero x = zero == x
src/Number/NonNegativeChunky.hs view
@@ -35,6 +35,7 @@ import qualified Algebra.Monoid as Monoid import qualified Data.Monoid as Mn98+import qualified Data.Semigroup as Sg98 import Control.Monad (liftM, liftM2, ) import Data.Tuple.HT (mapFst, mapSnd, mapPair, )@@ -323,6 +324,9 @@ instance (NonNeg98.C a, P98.Fractional a) => P98.Fractional (T a) where fromRational = fromNumber_ . P98.fromRational (/) = notImplemented "(/)"++instance (NonNeg.C a) => Sg98.Semigroup (T a) where+ (<>) = (Monoid.<*>) instance (NonNeg.C a) => Mn98.Monoid (T a) where mempty = Monoid.idt
src/NumericPrelude/List.hs view
@@ -27,7 +27,7 @@ in aux {--This is exported Checked.zipWith.+This is exported as Checked.zipWith. We need to define it here in order to prevent an import cycle. -} zipWithChecked