Package: src/packages/algebra.fdoc

key file
init.flx share/lib/std/algebra/__init__.flx
set.flx share/lib/std/algebra/set.flx
container.flx share/lib/std/algebra/container.flx
equiv.flx share/lib/std/algebra/equiv.flx
pord.flx share/lib/std/algebra/partialorder.flx
tord.flx share/lib/std/algebra/totalorder.flx
group.flx share/lib/std/algebra/group.flx
ring.flx share/lib/std/algebra/ring.flx
trig.flx share/lib/std/algebra/trig.flx
real.flx share/lib/std/algebra/real.flx
complex.flx share/lib/std/algebra/complex.flx
integer.flx share/lib/std/algebra/integer.flx
bits.flx share/lib/std/algebra/bits.flx
sequence.flx share/lib/std/algebra/sequence.flx
monad.flx share/lib/std/algebra/monad.flx

Core Algebraic Structures.

Synopsis.

//[init.flx]
include "std/algebra/predicate";        // in logic.fdoc
include "std/algebra/set";              // in algebra.fdoc
include "std/algebra/container";        // in algebra.fdoc
include "std/algebra/equiv";            // in algebra.fdoc
include "std/algebra/partialorder";     // in algebra.fdoc
include "std/algebra/totalorder";       // in algebra.fdoc
include "std/algebra/sequence";         // in algebra.fdoc
include "std/algebra/group";            // in algebra.fdoc
include "std/algebra/ring";             // in algebra.fdoc
include "std/algebra/bits";             // in algebra.fdoc
include "std/algebra/integer";          // in algebra.fdoc
include "std/algebra/trig";             // in algebra.fdoc
include "std/algebra/real";             // in algebra.fdoc
include "std/algebra/complex";          // in algebra.fdoc
include "std/algebra/monad";            // in algebra.fdoc

Description.

In this section we provide abstract definitions of some basic mathematical stuctures which will be used to specify operations on numeric types.

We use polymorphic classes to do this. A class is introduced by the class keyword followed by its name, then a list of type variables in square brackets. Then the body is presented enclosed in curly braces.

Two kinds of specification are allowed in a polymorphic class: function definitions and assertions.

Functions.

There are two kinds of function definitions. A function or procedure specified with the adjective virtual may have a specialisation provided in an instance declaration. Virtual functions may have definitions, in which case the definition is merely a default. It can be replaced in a specialising instance. However the definition should be taken as a semantic specification which the specialisation should adhere too.

The set of virtual functions of a polymorphic class is known as the <em>basis</em> of the class.

A non-virtual function can be defined in terms of virtual functions and other non-virtual functions. Non virtual functions cannot be specialised by the programmer. Instead, they are automatically specialised by the system for an instance.

Assertions

A polymorphic class may also contain assertions. These are function like specifications which specify semantic constraints.

An axiom specifies a basic assertion, it specifies a class property in terms of relations between the class functions. Since Felix only supports first order assertional logic, higher order semantics must be specified in comments.

If a class contains virtual functions with definitions, the definition is also considered as axiomatic.

The set of all axioms, including those in comments, is known as the <em>assertional basis</em> or <em>semantic specification</em> of the class. Additionally some reductions may be or imply an extension of the semantic basis.

A lemma is an assertion which can be derived from the semantic specifications by logical reasoning. In particular, lemmas in principle should be self-evident, simple and useful and able to be deduced by an automatic theorm proving program.

A theorem is a more complicated derived assertion, which would be too hard to prove with an automatic theorem prover. Instead, it should be derivable with a proof assistant (such as Coq), given various unspecified strategies, tactics and hints.

Sets.

A <em>set</em> is any type with a membership predicate \(\in\) spelled \in. You can also use function mem. The parser also maps in to operator \in.

We also provide a reversed form \(\owns\) spelled \owns, and negated forms \(ni\) spelled \ni or \notin.

Three combinators are provided as well, \(\cap\) spelled cap provides intersection, \(\cup\) spelled \cup provides the usual set union, and \(\setminus\) spelled \setminus the asymmetic set difference or subtraction.

Note that sets are not necessarily finite.

//[set.flx]
// note: eq is not necessarily required for a membership test
// for example: string member of regexp doesn't require
// string equality
// Set need not be finite (example regexp again)
// A list is a set, despite the duplications
class Set[c,t] {
  fun mem (elt:t, container:c):bool => elt \in container;
  virtual fun \in : t * c-> bool;
  fun \owns (container:c, elt:t) => elt \in container;
  fun \ni (container:c, elt:t) => elt \in container;
  fun \notin (elt:t, container:c) => not (elt \in container);

  fun \cup[c2 with Set[c2,t]]
    (x:c, y:c2) =>
    { e : t | e \in x or e \in y }
  ;

  fun \cap[c2 with Set[c2,t]]
    (x:c, y:c2) =>
    { e : t | e \in x and e \in y }
  ;

  fun \setminus[c2 with Set[c2,t]]
    (x:c, y:c2) =>
    { e : t | e \in x and e \notin y }
  ;
}

Set forms.

A set_form is a record type with a single member has_elt which returns true if it’s argument is intended as a member of some particular set.

We construe a set_form as a Set by providing an instance.

A set_form is basically just the membership predicate remodelled as a noun by encapsulating the predicate in a closure and thereby abstracting it.

//[set.flx]
interface set_form[T] { has_elt: T -> bool; }

instance[T] Set[set_form[T], T] {
  fun \in (elt:T, s:set_form[T]) => s.has_elt elt;
}
open[T] Set[set_form[T],T];

// INVERSE image of a set under a function
// For a function f: t -> t2, an element e
// is in a restriction of the domain t if its
// image in t2 is in the specified set.
fun invimg[t,c2,t2 with Set[c2,t2]]
  (f:t->t2, x:c2) : set_form[t] =>
  { e : t | (f e) \in x }
;

Cartesian Product of set_forms.

This uses some advanced instantiation technology to allow you to define the cartesian product of a sequence of sets using the infix TeX operator \(\otimes\) which is spelled \otimes. There’s also a left associative binary operator \(\times\) spelled \times.

//[set.flx]

fun \times[U,V] (x:set_form[U],y:set_form[V]) =>
  { u,v : U * V | u \in x and v \in y }
;

fun \otimes[U,V] (x:set_form[U],y:set_form[V]) =>
  { u,v : U * V | u \in x and v \in y }
;

fun \otimes[U,V,W] (head:set_form[U], tail:set_form[V*W]) =>
  { u,v,w : U * V * W | u \in head and (v,w) \in tail }
;

fun \otimes[NH,OH,OT] (head:set_form[NH], tail:set_form[OH**OT]) =>
  { h,,(oh,,ot) : NH ** (OH ** OT) | h \in head and (oh,,ot) \in tail }
;

Containers.

//[container.flx]
// roughly, a finite Set
class Container [c,v]
{
  inherit Set[c,v];
  virtual fun len: c -> size;
  fun \Vert (x:c) => len x;
  virtual fun empty(x: c): bool => len x == size(0);
}

Orders

Equivalence Relation.

An equivalence relation is a reflexive, symmetric, transitive relation. It is one of the most fundamental concepts in mathematics. One can show that for any set \(S\) , for any element \(s \in S\) , the subset \(\lbrack s\rbrack\) of \(S\) consisting of all elements equivalent to \(s\) are also equivalent to each other, and not equivalent to any other element outside that set.

Therefore, every equivalence relation on a set \(S\) specifies a partition of \(S\) which is a set of subsets of \(S\) known as equivalence classes, or just plain classes, such that no two classes have a common intersection, and the union of the classes spans the whole set.

In other words a partition consists of a disjoint union of subsets.

The most fundamential relation in computing which is required to be an equivalence relation is the equality operator. In particular, it allows us to have distinct encodings of a value, but still consider them equal semantically, and to provide an operational measure of that equivalence.

As a simple example, consider that the rational numbers \(1/2\) and \(2/4\) have distinct encodings but none-the-less are semantically equivalent.

An online reference on Wikibooks

//[equiv.flx]
// equality: technically, equivalence relation
class Eq[t] {
  virtual fun == : t * t -> bool;
  virtual fun != (x:t,y:t):bool => not (x == y);

  axiom reflex(x:t): x == x;
  axiom sym(x:t, y:t): (x == y) == (y == x);
  axiom trans(x:t, y:t, z:t): x == y and y == z implies x == z;

  fun eq(x:t, y:t)=> x == y;
  fun ne(x:t, y:t)=> x != y;
  fun \ne(x:t, y:t)=> x != y;
  fun \neq(x:t, y:t)=> x != y;
}

Partial Order

A proper partial order \(\subset\) spelled \subset is a transitive, antisymmetric irreflexive relation.

We also provide an improper operator \(\subseteq\) spelled \subseteq which is transitive, antisymmetric, and reflexive, for which either the partial order or equivalence operator == applies.

The choice of operators is motivated by the canonical exemplar of subset containment relations.

//[pord.flx]
// partial order
class Pord[t]{
  inherit Eq[t];
  virtual fun \subset: t * t -> bool;
  virtual fun \supset(x:t,y:t):bool =>y \subset x;
  virtual fun \subseteq(x:t,y:t):bool => x \subset y or x == y;
  virtual fun \supseteq(x:t,y:t):bool => x \supset y or x == y;

  fun \subseteqq(x:t,y:t):bool => x \subseteq y;
  fun \supseteqq(x:t,y:t):bool => x \supseteq y;

  fun \nsubseteq(x:t,y:t):bool => not (x \subseteq y);
  fun \nsupseteq(x:t,y:t):bool => not (x \supseteq y);
  fun \nsubseteqq(x:t,y:t):bool => not (x \subseteq y);
  fun \nsupseteqq(x:t,y:t):bool => not (x \supseteq y);

  fun \supsetneq(x:t,y:t):bool => x \supset y;
  fun \supsetneqq(x:t,y:t):bool => x \supset y;
  fun \supsetneq(x:t,y:t):bool => x \supset y;
  fun \supsetneqq(x:t,y:t):bool => x \supset y;

  axiom trans(x:t, y:t, z:t): \subset(x,y) and \subset(y,z) implies \subset(x,z);
  axiom antisym(x:t, y:t): \subset(x,y) or \subset(y,x) or x == y;
  axiom reflex(x:t, y:t): \subseteq(x,y) and \subseteq(y,x) implies x == y;
}

Bounded Partial Order

A partial order may bave an upper or lower bound known as the supremum and infimum, respectively. If these values are in the type, they are called the maximum and minimum, respectively.

//[pord.flx]
class UpperBoundPartialOrder[T] {
  inherit Pord[T];
  virtual fun upperbound: 1 -> T;
}
class LowerBoundPartialOrder[T] {
  inherit Pord[T];
  virtual fun lowerbound: 1 -> T;
}
class BoundPartialOrder[T] {
  inherit LowerBoundPartialOrder[T];
  inherit UpperBoundPartialOrder[T];
}

Total Order

A total order is a partial order with a totality law.

However we do not derive it from our partial order because we use different comparison operators. Here we use the standard ascii art comparison operators commonly found in programming languages along with the more beautiful TeX operators used in mathematical papers.

The spelling of the TeX operators can be found by holding the mouse over the symbol briefly.

//[tord.flx]
// total order
class Tord[t]{
  inherit Eq[t];
  // defined in terms of <, argument order swap, and boolean negation

  // less
  virtual fun < : t * t -> bool;
  fun lt (x:t,y:t): bool=> x < y;
  fun \lt (x:t,y:t): bool=> x < y;
  fun \lneq (x:t,y:t): bool=> x < y;
  fun \lneqq (x:t,y:t): bool=> x < y;


  axiom trans(x:t, y:t, z:t): x < y and y < z implies x < z;
  axiom antisym(x:t, y:t): x < y or y < x or x == y;
  axiom reflex(x:t, y:t): x < y and y <= x implies x == y;
  axiom totality(x:t, y:t): x <= y or y <= x;


  // greater
  fun >(x:t,y:t):bool => y < x;
  fun gt(x:t,y:t):bool => y < x;
  fun \gt(x:t,y:t):bool => y < x;
  fun \gneq(x:t,y:t):bool => y < x;
  fun \gneqq(x:t,y:t):bool => y < x;

  // less equal
  fun <= (x:t,y:t):bool => not (y < x);
  fun le (x:t,y:t):bool => not (y < x);
  fun \le (x:t,y:t):bool => not (y < x);
  fun \leq (x:t,y:t):bool => not (y < x);
  fun \leqq (x:t,y:t):bool => not (y < x);
  fun \leqslant (x:t,y:t):bool => not (y < x);


  // greater equal
  fun >= (x:t,y:t):bool => not (x < y);
  fun ge (x:t,y:t):bool => not (x < y);
  fun \ge (x:t,y:t):bool => not (x < y);
  fun \geq (x:t,y:t):bool => not (x < y);
  fun \geqq (x:t,y:t):bool => not (x < y);
  fun \geqslant (x:t,y:t):bool => not (x < y);

  // negated, strike-through
  fun \ngtr (x:t,y:t):bool => not (x < y);
  fun \nless (x:t,y:t):bool => not (x < y);

  fun \ngeq (x:t,y:t):bool => x < y;
  fun \ngeqq (x:t,y:t):bool => x < y;
  fun \ngeqslant (x:t,y:t):bool => x < y;

  fun \nleq (x:t,y:t):bool => not (x <= y);
  fun \nleqq (x:t,y:t):bool => not (x <= y);
  fun \nleqslant (x:t,y:t):bool => not (x <= y);


  // maxima and minima
  fun max(x:t,y:t):t=> if x < y then y else x endif;
  fun \vee(x:t,y:t) => max (x,y);

  fun min(x:t,y:t):t => if x < y then x else y endif;
  fun \wedge(x:t,y:t):t => min (x,y);


}

Bounded Total Orders.

//[tord.flx]
class UpperBoundTotalOrder[T] {
  inherit Tord[T];
  virtual fun maxval: 1 -> T = "::std::numeric_limits<?1>::max()";
}
class LowerBoundTotalOrder[T] {
  inherit Tord[T];
  virtual fun minval: 1 -> T = "::std::numeric_limits<?1>::min()";
}
class BoundTotalOrder[T] {
  inherit LowerBoundTotalOrder[T];
  inherit UpperBoundTotalOrder[T];
}

Sequences

Sequences are discrete total orders.

//[sequence.flx]

// Forward iterable
class ForwardSequence[T] {
  inherit Tord[T];
  virtual fun succ: T -> T;
  virtual proc pre_incr: &T;
  virtual proc post_incr: &T;
}

// Bidirectional
class BidirectionalSequence[T] {
  inherit ForwardSequence[T];
  virtual fun pred: T -> T;
  virtual proc pre_decr: &T;
  virtual proc post_decr: &T;
}

// Bounded Random access totally ordered
// int should be any integer type really .. fix later
class RandomSequence[T] {
  inherit BidirectionalSequence[T];
  virtual fun advance : int * T -> T;
}

// Bounded totally ordered forward iterable
class BoundForwardSequence[T] {
  inherit ForwardSequence[T];
  inherit UpperBoundTotalOrder[T];
}

// Bounded totally ordered bidirectional
class BoundBidirectionalSequence[T] {
  inherit BidirectionalSequence[T];
  inherit BoundTotalOrder[T];
}

// Bounded Random access totally ordered
class BoundRandomSequence[T] {
  inherit RandomSequence[T];
  inherit BoundBidirectionalSequence[T];
}

Groupoids.

Approximate Additive Group

An approximate additive group is a type for which there is a symmetric binary addition operator, a zero element, and for which there is an additive inverse or negation operator.

It is basically an additive group without the associativity requirement, and is intended to apply to floating point numbers.

Note we use the inherit statement to include the functions from class Eq.

//[group.flx]
//$ Additive symmetric float-approximate group, symbol +.
//$ Note: associativity is not assumed.
class FloatAddgrp[t] {
  inherit Eq[t];
  virtual fun zero: unit -> t;
  virtual fun + : t * t -> t;
  virtual fun neg : t -> t;
  virtual fun prefix_plus : t -> t = "$1";
  virtual fun - (x:t,y:t):t => x + -y;
  virtual proc += (px:&t,y:t) { px <- *px + y; }
  virtual proc -= (px:&t,y:t) { px <- *px - y; }

  reduce id (x:t): x+zero() => x;
  reduce id (x:t): zero()+x => x;
  reduce inv(x:t): x - x => zero();
  reduce inv(x:t): - (-x) => x;
  axiom sym (x:t,y:t): x+y == y+x;

  fun add(x:t,y:t)=> x + y;
  fun plus(x:t)=> +x;
  fun sub(x:t,y:t)=> x - y;
  proc pluseq(px:&t, y:t) {  += (px,y); }
  proc  minuseq(px:&t, y:t) { -= (px,y); }
}

Additive Group

A proper additive group is derived from FloatAddgrp with associativity added.

//[group.flx]
//$ Additive symmetric group, symbol +.
class Addgrp[t] {
  inherit FloatAddgrp[t];
  axiom assoc (x:t,y:t,z:t): (x + y) + z == x + (y + z);
  reduce inv(x:t,y:t): x + y - y => x;
}

Approximate Multiplicative Semi-Group With Unit.

An approximate multiplicative semigroup is a set with a symmetric binary multiplication operator and a unit.

//[group.flx]
//$ Multiplicative symmetric float-approximate semi group with unit symbol *.
//$ Note: associativity is not assumed.
class FloatMultSemi1[t] {
  inherit Eq[t];
  proc muleq(px:&t, y:t) { *= (px,y); }
  fun mul(x:t, y:t) => x * y;
  fun sqr(x:t) => x * x;
  fun cube(x:t) => x * x * x;
  virtual fun one: unit -> t;
  virtual fun * : t * t -> t;
  virtual proc *= (px:&t, y:t) { px <- *px * y; }
  reduce id (x:t): x*one() => x;
  reduce id (x:t): one()*x => x;
}

Multiplicative Semi-Group With Unit.

A multiplicative semigroup with unit is an approximate multiplicative semigroup with unit and associativity and satisfies the cancellation law.

//[group.flx]
//$ Multiplicative semi group with unit.
class MultSemi1[t] {
  inherit FloatMultSemi1[t];
  axiom assoc (x:t,y:t,z:t): (x * y) * z == x * (y * z);
  reduce cancel (x:t,y:t,z:t): x * z ==  y * z => x == y;
}

Rings

Approximate Unit Ring.

An approximate ring is a set which has addition and multiplication satisfying the rules for approximate additive group and multiplicative semigroup respectively.

//[ring.flx]
//$ Float-approximate ring.
class FloatRing[t] {
  inherit FloatAddgrp[t];
  inherit FloatMultSemi1[t];
}

Ring

A ring is a type which is a both an additive group and multiplicative semigroup with unit, and which in addition satisfies the distributive law.

//[ring.flx]
//$ Ring.
class Ring[t] {
  inherit Addgrp[t];
  inherit MultSemi1[t];
  axiom distrib (x:t,y:t,z:t): x * ( y + z) == x * y + x * z;
}

Approximate Division Ring

An approximate division ring is an approximate ring with unit with a division operator.

//[ring.flx]
//$ Float-approximate division ring.
class FloatDring[t] {
  inherit FloatRing[t];
  virtual fun / : t * t -> t; // pre t != 0
  fun \over (x:t,y:t) => x / y;

  virtual proc /= : &t * t;
  virtual fun % : t * t -> t;
  virtual proc %= : &t * t;

  fun div(x:t, y:t) => x / y;
  fun mod(x:t, y:t) => x % y;
  fun \bmod(x:t, y:t) => x % y;
  fun recip (x:t) => #one / x;

  proc diveq(px:&t, y:t) { /= (px,y); }
  proc modeq(px:&t, y:t) { %= (px,y); }
}

Division Ring

//[ring.flx]
//$ Division ring.
class Dring[t] {
  inherit Ring[t];
  inherit FloatDring[t];
}

Integral.

Bitwise operations

//[bits.flx]

//$ Bitwise operators.
class Bits[t] {
  virtual fun \^ : t * t -> t = "(?1)($1^$2)";
  virtual fun \| : t * t -> t = "$1|$2";
  virtual fun \& : t * t -> t = "$1&$2";
  virtual fun ~: t -> t = "(?1)(~$1)";
  virtual proc ^= : &t * t = "*$1^=$2;";
  virtual proc |= : &t * t = "*$1|=$2;";
  virtual proc &= : &t * t = "*$1&=$2;";

  fun bxor(x:t,y:t)=> x \^ y;
  fun bor(x:t,y:t)=> x \| y;
  fun band(x:t,y:t)=> x \& y;
  fun bnot(x:t)=> ~ x;

}

Integer

//[integer.flx]

//$ Integers.
class Integer[t] {
  inherit Tord[t];
  inherit Dring[t];
  inherit RandomSequence[t];
  virtual fun << : t * t -> t = "$1<<$2";
  virtual fun >> : t * t -> t = "$1>>$2";

  fun shl(x:t,y:t)=> x << y;
  fun shr(x:t,y:t)=> x >> y;
}

//$ Signed Integers.
class Signed_integer[t] {
  inherit Integer[t];
  virtual fun sgn: t -> int;
  virtual fun abs: t -> t;
}

//$ Unsigned Integers.
class Unsigned_integer[t] {
  inherit Integer[t];
  inherit Bits[t];
}

Float kinds

Trigonometric Functions.

Trigonometric functions are shared by real and complex numbers.

//[trig.flx]

//$ Float-approximate trigonometric functions.
class Trig[t] {
  inherit FloatDring[t];

  // NOTE: most of the axioms here WILL FAIL because they require
  // exact equality, but they're only going to succeed with approximate
  // equality, whatever that means. This needs to be fixed!

  // circular
  // ref http://en.wikipedia.org/wiki/Circular_functions

  // core trig
  virtual fun sin: t -> t;
  fun \sin (x:t)=> sin x;

  virtual fun cos: t -> t;
  fun \cos (x:t)=> cos x;

  virtual fun tan (x:t)=> sin x / cos x;
  fun \tan (x:t)=> tan x;

  // reciprocals
  virtual fun sec (x:t)=> recip (cos x);
  fun \sec (x:t)=> sec x;

  virtual fun csc (x:t)=> recip (sin x);
  fun \csc (x:t)=> csc x;

  virtual fun cot (x:t)=> recip (tan x);
  fun \cot (x:t)=> cot x;

  // inverses
  virtual fun asin: t -> t;
  fun \arcsin (x:t) => asin x;

  virtual fun acos: t -> t;
  fun \arccos (x:t) => acos x;

  virtual fun atan: t -> t;
  fun \arctan (x:t) => atan x;

  virtual fun asec (x:t) => acos ( recip x);
  virtual fun acsc (x:t) => asin ( recip x);
  virtual fun acot (x:t) => atan ( recip x);

  // hyperbolic
  // ref http://en.wikipedia.org/wiki/Hyperbolic_functions
  virtual fun sinh: t -> t;
  fun \sinh (x:t) => sinh x;

  virtual fun cosh: t -> t;
  fun \cosh (x:t) => cosh x;

  virtual fun tanh (x:t) => sinh x / cosh x;
  fun \tanh (x:t) => tanh x;

  // reciprocals
  virtual fun sech (x:t) => recip (cosh x);
  fun \sech (x:t) => sech x;

  virtual fun csch (x:t) => recip (sinh x);
  fun \csch (x:t) => csch x;

  virtual fun coth (x:t) => recip (tanh x);
  fun \coth (x:t) => coth x;

  // inverses
  virtual fun asinh: t -> t;

  virtual fun acosh: t -> t;

  virtual fun atanh: t -> t;

  virtual fun asech (x:t) => acosh ( recip x);
  virtual fun acsch (x:t) => asinh ( recip x );
  virtual fun acoth (x:t) => atanh ( recip x );

  // exponential
  virtual fun exp: t -> t;
  fun \exp (x:t) => exp x;

  // log
  virtual fun log: t -> t;
  fun \log (x:t) => log x;
  fun ln (x:t) => log x;
  fun \ln (x:t) => log x;

  // power
  virtual fun pow: t * t -> t;
  virtual fun pow (a:t, b:int) : t => pow (a, C_hack::cast[t] b);
  fun ^ (x:t,y:t) => pow (x,y);
  fun ^ (x:t,y:int) => pow (x,y);


}

//$ Finance and Statistics.
class Special[t] {
  virtual fun erf: t -> t;
  virtual fun erfc: t -> t;
}

Approximate Reals.

//[real.flx]
//$ Float-approximate real numbers.
class Real[t] {
  inherit Tord[t];
  inherit Trig[t];
  inherit Special[t];
  virtual fun embed: int -> t;

  virtual fun log10: t -> t;
  virtual fun abs: t -> t;

  virtual fun sqrt: t -> t;
  fun \sqrt (x:t) => sqrt x;
  virtual fun ceil: t -> t;
    // tex \lceil \rceil defined in grammar

  virtual fun floor: t -> t;
    // tex \lfloor \rfloor defined in grammar

  virtual fun trunc: t -> t;

  // this trig function is included here because it
  // is not available for complex numbers
  virtual fun atan2: t * t -> t;

}

Complex numbers

//[complex.flx]
//$ Float-approximate Complex.
class Complex[t,r] {
  inherit Eq[t];
  inherit Special[t];
  inherit Trig[t];
  virtual fun real: t -> r;
  virtual fun imag: t -> r;
  virtual fun abs: t -> r;
  virtual fun arg: t -> r;
  virtual fun sqrt: t -> r;

  virtual fun + : r * t -> t;
  virtual fun + : t * r -> t;
  virtual fun - : r * t -> t;
  virtual fun - : t * r -> t;
  virtual fun * : t * r -> t;
  virtual fun * : r * t -> t;
  virtual fun / : t * r -> t;
  virtual fun / : r * t -> t;
}

Summation and Product Quantifiers.

To be moved. Folds over streams.

//[group.flx]
open class Quantifiers_add_mul {
  fun \sum[T,C with FloatAddgrp[T], Streamable[C,T]] (a:C):T =
  {
    var init = #zero[T];
    for x in a perform init = init + x;
    return init;
  }

  fun \prod[T,C with FloatMultSemi1[T], Streamable[C,T]] (a:C):T =
  {
    var init = #one[T];
    for x in a perform init = init * x;
    return init;
  }

  fun \sum[T with FloatAddgrp[T]] (f:1->opt[T])  =
  {
    var init = #zero[T];
    for x in f perform init = init + x;
    return init;
  }

  fun \prod[T with FloatMultSemi1[T]] (f:1->opt[T])  =
  {
    var init = #one[T];
    for x in f perform init = init * x;
    return init;
  }

}

Monad

//[monad.flx]

class Monad [M: TYPE->TYPE] {
  virtual fun ret[a]: a -> M a;
  virtual fun bind[a,b]: M a * (a -> M b) -> M b;
  fun join[a] (n: M (M a)): M a => bind (n , (fun (x:M a):M a=>x));
}