NumericPrelude

The exponent has fixed type Integer in order to avoid an arbitrarily limitted range of exponents, but to reduce the need for the compiler to guess the type (default type). In practice the exponent is most oftenly fixed, and is most oftenly 2. Fixed exponents can be optimized away and thus the expensive computation of Integers doesn't matter. The previous solution used a C constrained type and the exponent was converted to Integer before computation. So the current solution is not less efficient.

A variant of ^ with more flexibility is provided by Algebra.Core.ringPower.

zero element of the vector space

inverse with respect to +

add and subtract elements

add and subtract elements

A fixed-precision integer type with at least the range [-2^29 .. 2^29-1]. The exact range for a given implementation can be determined by using Prelude.minBound and Prelude.maxBound from the Prelude.Bounded class.

Arbitrary precision integers. In contrast with fixed-size integral types such as Int, the Integer type represents the entire infinite range of integers.

Integers are stored in a kind of sign-magnitude form, hence do not expect two's complement form when using bit operations.

If the value is small (i.e., fits into an Int), the IS constructor is used. Otherwise IP and IN constructors are used to store a BigNat representing the positive or the negative value magnitude, respectively.

Invariant: IP and IN are used iff the value does not fit in IS.

Single-precision floating point numbers. It is desirable that this type be at least equal in range and precision to the IEEE single-precision type.

Double-precision floating point numbers. It is desirable that this type be at least equal in range and precision to the IEEE double-precision type.

subtract is (-) with swapped operand order. This is the operand order which will be needed in most cases of partial application.

Sum up all elements of a list. An empty list yields zero.

This function is inappropriate for number types like Peano. Maybe we should make sum a method of Additive. This would also make lengthLeft and lengthRight superfluous.

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.

prop> \(QC.NonEmpty ns) -> A.sum ns == (A.sum1 ns :: Integer)

Needed to work around shortcomings in GHC.

Compute the greatest common divisor and solve a respective Diophantine equation.

  (g,(a,b)) = extendedGCD x y ==>
       g==a*x+b*y   &&  g == gcd x y

TODO: This method is not appropriate for the PID class, because there are rings like the one of the multivariate polynomials, where for all x and y greatest common divisors of x and y exist, but they cannot be represented as a linear combination of x and y. TODO: The definition of extendedGCD does not return the canonical associate.

The Greatest Common Divisor is defined by:

  gcd x y == gcd y x
  divides z x && divides z y ==> divides z (gcd x y)   (specification)
  divides (gcd x y) x

Least common multiple

scale a vector by a scalar

A prefix function of (Algebra.Ring.^) with a parameter order that fits the needs of partial application and function composition. It has generalised exponent.

See: Argument order of expNat on http://www.haskell.org/pipermail/haskell-cafe/2006-September/018022.html

A prefix function of (Algebra.Field.^-). It has a generalised exponent.

TODO: Should be moved to a continued fraction module.

Lossless conversion from any representation of a rational to Rational

Right to left function composition.

prop> (f . g) x = f (g x)

prop> f . id = f = id . f

Examples

>>> map ((*2) . length) [[], [0, 1, 2], [0]][0,6,2]

>>> foldr (.) id [(+1), (*3), (^3)] 225

>>> let (...) = (.).(.) in ((*2)...(+)) 5 1030

Conversion of values to readable Strings.

Derived instances of Show have the following properties, which are compatible with derived instances of Text.Read.Read:

• The result of show is a syntactically correct Haskell expression containing only constants, given the fixity declarations in force at the point where the type is declared. It contains only the constructor names defined in the data type, parentheses, and spaces. When labelled constructor fields are used, braces, commas, field names, and equal signs are also used.

• If the constructor is defined to be an infix operator, then showsPrec will produce infix applications of the constructor.

• the representation will be enclosed in parentheses if the precedence of the top-level constructor in x is less than d (associativity is ignored). Thus, if d is 0 then the result is never surrounded in parentheses; if d is 11 it is always surrounded in parentheses, unless it is an atomic expression.

• If the constructor is defined using record syntax, then show will produce the record-syntax form, with the fields given in the same order as the original declaration.

For example, given the declarations

infixr 5 :^:
data Tree a =  Leaf a  |  Tree a :^: Tree a

the derived instance of Show is equivalent to

instance (Show a) => Show (Tree a) where

       showsPrec d (Leaf m) = showParen (d > app_prec) $
            showString "Leaf " . showsPrec (app_prec+1) m
         where app_prec = 10

       showsPrec d (u :^: v) = showParen (d > up_prec) $
            showsPrec (up_prec+1) u .
            showString " :^: "      .
            showsPrec (up_prec+1) v
         where up_prec = 5

Note that right-associativity of :^: is ignored. For example,

• show (Leaf 1 :^: Leaf 2 :^: Leaf 3) produces the string "Leaf 1 :^: (Leaf 2 :^: Leaf 3)".

The Ord class is used for totally ordered datatypes.

Instances of Ord can be derived for any user-defined datatype whose constituent types are in Ord. The declared order of the constructors in the data declaration determines the ordering in derived Ord instances. The Ordering datatype allows a single comparison to determine the precise ordering of two objects.

Ord, as defined by the Haskell report, implements a total order and has the following properties:

Comparability

x <= y || y <= x

=

True

Transitivity

if

x <= y && y <= z

=

True

, then

x <= z

=

True

Reflexivity

x <= x

=

True

Antisymmetry

if

x <= y && y <= x

=

True

, then

x == y

=

True

The following operator interactions are expected to hold:

1. x >= y = y <= x

2. x < y = x <= y && x /= y

3. x > y = y < x

4. x < y = compare x y == LT

5. x > y = compare x y == GT

6. x == y = compare x y == EQ

7. min x y == if x <= y then x else y = True

8. max x y == if x >= y then x else y = True

Note that (7.) and (8.) do not require min and max to return either of their arguments. The result is merely required to equal one of the arguments in terms of (==).

Minimal complete definition: either compare or <=. Using compare can be more efficient for complex types.