Traits

A trait unifies types which share certain characteristics under a common name. Working with traits requires somewhat abstract thinking. The reward: functions can be defined for multiple types at once.

Algebra inspired traits

A handful of traits inspired by algebraic structures build upon each other. They are described in detail below, but let us look at a graph which illustrates their relationship first:

         ┌───────┐
         │ Soup  │ add
         └───┬───┘
        ╭────┴────╮
    ┌───┴───┐ ┌───┴───┐
neg │ Group │ │  Sing │ mul
    └───┬───┘ └───┬───┘
        ╰────┬────╯
         ┌───┴───┐
         │ Ring  │
         └───┬───┘
         ┌───┴───┐
     inv │ Field │
         └───┬───┘
         ┌───┴───┐
     con │Complex│
         └───────┘

The Soup trait with its associated core function add is the most elementary trait in the graph. Any trait below it inherits its properties, but defines additional properties which allow for working with more of Quirl's core functions. The Complex trait inherits all earlier capabilities, but only few types share this trait.

Soup

Types with the Soup trait define a binary operation that we call addition and are closed under it. A binary operation is an operation that takes two input values. Being closed under an operation means that the output of the operation is of the same type as its input values. Addition is made accessible via the add core function. By the way, Soup is a contraction of semigroup. Like semigroups in mathematics, Soup requires an additional property of its operation:

Additive associativity:: add(add(A B) C) is equal to add(A add(B C)).

The Text type is one of many examples that implement Soup. It defines addition as concatenation so that add("butter" "fly") results in "butterfly".

Group

Types with the Group trait always have the Soup trait. Additionally, they are guaranteed to have an additive identity element and they define a unary operation that returns the additive inverse. Unary means the operation takes a single input value. We call that operation negation. It is made accessible via the neg core function. Types with the Group trait are closed under negation. The following requirements hold for an arbitrary value A and the additive identity O:

Additive identity:: Both add(A O) and add(O A) are equal to A.
Additive inverse:: Both add(A neg(A)) and add(neg(A) A) are equal to O.

The Turn type is an example for a Group. It defines negation of an angle as its explementary angle. By definition, explementary angles add up to a full turn, which is the same as 0t: think of how an analog clock displays exactly the same state before and after a full turn of the hour hand.

Sing

Types with the Sing trait always have the Soup trait. Additionally, they define a second binary operation that we call multiplication and they are closed under it. Multiplication is made available via the mul core function. By the way, Sing is derived from semiring. Unfortunately literature does not agree on the requirements for semirings. But here are the properties that Sing implies in Quirl additionally to those mentioned for Soup for any values A, B, C:

Additive commutativity:: add(A B) is equal to add(B A).
Mulplicative associativity:: mul(mul(A B) C) is equal to mul(A mul(B C)).
Distributivity of multiplication over addition:: mul(A add(B C)) is equal to add(mul(A B) mul(A C)).
mul(add(B C) A) is equal to add(mul(B A) mul(C A)).

The Set type is an example for the Sing trait. It defines addition as the union of sets and multiplication as the intersection of sets.

Ring

A type with the Ring trait satisfies the Group and Sing traits. Literature does not universally agree on the properties of rings. You may find definitions that require more than implied in Quirl. Quirl does not make any additional requirements except those made by Group and Sing. However, a consequence is worth mentioning. Let's denote additive identity by O and an arbitrary value by A:

Annihilation through multiplication with additive identity:: Both mul(A O) and mul(O A) are equal to O.

The integer type Int is a good example for the Ring trait. It is closed under classical addition and multiplication. It has 0 as its additive identity element. Negation is typically denoted by a minus sign.

Field

Types with the Field trait satisfy the Ring trait. Additionally, they have a multiplicative identity element and define a second unary operation that produces the multiplicative inverse of any value except for the additive identity. The inverse operation is made accessible via the inv core function. Further properties of fields hold for arbitrary values A, B and the additive and multiplicative identity elements O and I:

Multiplicative commutativity:: mul(A B) is equal to mul(B A).
Multiplicative identity:: mul(A I) and of course mul(I A) are equal to A.
Multiplicative inverse:: mul(C inv(C)) and of course mul(inv(C) C) are equal to I for any C that is distinct from O.

The type Rat for rational numbers is a good example for a Field. In case of rationals, a multiplicative inverse is also called reciprocal.

Complex

Types with the Complex trait represent (a subset of) complex numbers and satisfy the Field trait. Additionally to Field properties, they are closed under a third unary operation: conjugation. It is made accessible via the con core function whose output has the same real part as the input, but its negative imaginary part. Furthermore, Complex also sponsors the arg core function which returns the angle between the positive real axis and the line from the origin of the complex plane to the input value.

Float is an example for a type that implements the Complex trait in Quirl.

Universal and impossible traits

Operand

The Operand trait is universally shared by all types whose values can be supplied as an argument to a function. In other words, any argument is matched by this trait, similar to how any argument is matched by a wildcard ?. However, Operand and ? differ when multiple such parameters occur in a parameter list:

Arguments that are matched by wildcards are always accepted when a function is called. They are taken by the function unchanged.
Multiple arguments that are matched by Operand parameters are converted to a common type before being processed by the function. Arguments that can not be converted to a common type do not meet the requirements of the function, even though each individual argument could be matched by the Operand trait.

Impossible

There is no type that has the Impossible trait. Hence no value is matched by it.

But why is it defined then? It exists to label the result of impossible demands such as Bool*Int (no value can be boolean and an integer at the same time) and happens to be the additive identity element of the Type type.

Other traits

Angle

Nomen est omen: types with the Angle trait represent angles. The associated sin core function returns the sine of any given angle.

Callable

An instance of a Callable type can be used as a function that accepts arguments in parenthesis as inputs, does computations with them and returns an output value. Typical examples for Callable types are Fun and the polynomial type Pol.

Ordered

Types with the Ordered trait define a total order on their values. It is made accessible via the binary core function ord. The boolean return value expresses whether the given arguments are in order. The properties of a total order imply that the following propositions hold for any values A, B, C of an Ordered type:

Reflexivity:: ord(A A) is true.
Totality:: ord(A B) is true or ord(B A) is true, if A and B are distinct.
Anti-symmetry:: A and B are equal, if both ord(A B) and ord(B A) are true.
Transitivity:: ord(A C) is true, if both ord(A B) and ord(B C) are true.

For example, Int has the Ordered trait and its intrinsic order is the less than or equal relation. So, for two integers M and N, ord(M N) means M ≤ N.

Peelable

Sets and tuples are Peelable types: they wrap an arbitrary number of items in curly brackets or square brackets respectively. The contained items can be extracted with the peel core function, which returns a list of these values which can be of various types.

Rootable

The Rootable trait is shared by types that can extract n-th roots. An n-th root is the answer to the following task: find a value that results in a given argument, if you multiply n instances of the value with one another. So finding a root is an inverse operation of repeated multiplication, also known as exponentiation. Hence Rootable types usually also have the Sing trait, which introduces multiplication.

Finding an n-th root is made accessible via the root core function. Note that there are usually multiple n-th roots, but the core function just returns one of them. It does not need to be what conventions call the principal root either. Rootable types are not necessarily closed under root extraction, so the returned value can be of a different type than the argument. But Quirl prefers a solution of the same or simpler type.

Quad is an example for a Rootable type.

Scalable

Values of types with the Scalable trait can be multiplied by a rational scale factor. This is done with the scale core function.

The following properties typically hold for rational scale factors R and S and arbitrary values A, B and the additive identity O of a Scalable type that also has the Group trait:

scale(A 1) is equal to A
scale(A 0) is equal to O
scale(A -1) is equal to neg(A)
scale(add(A B) S) is equal to add(scale(A S) scale(B S))
scale(A add(R S)) is equal to add(scale(A R) scale(A S))

The polynomial type Pol is an example for a Scalable type.

Splittable

Types with the Splittable trait also have the Soup trait. Characteristically, values of Splittable types tend to be composed of additive terms that can not be merged further into a single term. The split core function returns a list of these additive terms of a given input. All returned values are of the same type as the input. Mind that an additive identity element is never included in the returned list, since an additive identity could be merged with any other term. An empty list is returned, if the input is nothing but an additive identity element.

The Text type is an example for a Splittable type. A textual value splits into the characters that it is made of. The empty text is the type's additive identity and splits into nothing, as it does not contain any characters.