– Typee Documentation –

4 – Built-in Containers

4.2 – Lists

Lists are indexable containers with unfixed sizes and no need of types specification for their content. They may contain together any type of content and may get multiple dimensions. When speaking about programming language theory, in Typee: arrays are a subset of lists.

4.2.1 Lists Declaration

The formal EBNF specification of the syntax of lists declaration in Typee is:

<list declaration> ::= [<const>] <list type> <identifier>
                            [ '=' <list content> ] ';' 

<items list>        ::= [ <expression> ( ',' expression )* ]

<list content>      ::= '[' (<items list> | <list content>) ']' 

<list type>         ::= 'list' [<contained type>]

<contained type>    ::= '<' <types list> '>' 

<dimensions>        ::= '[' (<integer number> | <dotted name>) ']' 
                            ( '[' (<integer number> | <dotted name>) ']' )*

<dotted name>       ::= <identifier> ( '.' <identifier> )*

<templated type>    ::=  <dotted name>
                            [ '<' <types and exprs list> '>' ]

<types list>        ::= <type>  |  '(' <type> ( ',' <type> )* ')' 

<type>              ::= [ 'const' ] (<scalar type> | <dotted name>)

So, there is no need to specify any contained type for a list in Typee. This is the exact equivalent of list in Python, for instance. Of course, if a type or a list of types are declared, the list may only contain items of these types.

There is no need also to specify dimensions when declaring a list in Typee. Lists are not of fixed size and may grow or shrink along the running of a program. Meanwhile, their exact sizes are always known at any time.

Programmers are encouraged to use arrays when types and sizes for data are known and will not change. Accessing and modifying arrays will most of the time be faster and more efficient than accessing or modifying lists.
Meanwhile, freely modifying a list is far easier and sometimes far faster than modifying an array (for isntance, when inserting a value, appending a value, etc.)

Examples:

list<uint32> primes = [1, 2, 3, 5, 7, 11, 13];
const list identity_matrix = [ [1.0, 0.0, 0.0],
                               [0.0, 1.0, 0.0],
                               [0.0, 0.0, 1.0] ];

4.2.2 Lists Indexation

Exactly as for arrays, there are three ways for indexing a list: subscription, slicing and comprehension.

<subscription or slicing>   ::= <subscription or slicing'>
                                    (<subscription or slicing'>)*
<subscription or slicing'>  ::= '[' <expression>
                                    ( ']'                     |
                                      <if comprehension> ']'  |
                                      <slice form> <slice end> )
<for comprehension>         ::= 'for' '(' <target list> 
                                    'in' <or test> <iter comprehension> ')' 

<if comprehension>          ::= 'if' '(' (<or test> | <unnamed func>) ')' 
                                    <iter comprehension>

<iter comprehension>        ::= [ <for comprehension>  |  <if comprehension> ]

<slice end>                 ::= ']'  |  ')' 

<slice form>                ::= ':' [<expression>]  [ ':' [<expression>] ]

4.2.2.1 Subscription

Subscription, or indexing, only involves the use of a single expression between two brackets. It directly accesses the content of the indexed entity. If the list gets one dimension only, the subscription gets access to the contained item at this index in the list. It the list gets two dimensions, the first subscription gets access to the indexed line in the list. The use of a secondary subscription in this line directly accesses the item contained at this index in this line of the list. Easy to extend to more than two dimensions. Indexing in Typee starts at 0.

As with Python, negative subscripting is allowed. It starts from -1 which is the index of the very last item. Index -2 stands then for the index of the item that is before the last one and index -3 stands for the antepenultimate one, etc.

Let’s have a few examples:

list<uint8> the_list = [ [ 0,  1,  2],
                         [10, 11, 12],
                         [20, 21, 22],
                         [30, 31, 32] ];

print( the_list [0] );      // prints "[0, 1, 2]"
print( the_list [3] );      // prints "[30, 31, 32]"
print( the_list [3][2] );   // prints "32"

the_list [2][11] = 121;
print( the_list [2] );      // prints "[20, 121, 22]"

print( the_list [-1][-2] ); // prints "121"
print( the_list [ 1][-1] ); // prints "12"

4.2.2.2 Slicing

Slicing is a well known concept in Python. It selects a range within a list. Easier to understand with a few examples. Notice that it is exactly the same for lists as for arrays.

First, about slicing itself:

[start:end]
// means "indexing of all items ranging
// from index 'start' up to index 'end'> included".

[start:end)
// means "indexing of all items ranging
// from index 'start' up to index 'end' excluded".

[start:end:step]
// means "indexing of all items ranging
// from index 'start' up to index 'end' included
// by steps of value 'step'".

[start:end:step)
// means "indexing of all items ranging
// from index 'start' up to index 'end' excluded
// by steps of value 'step'".

Slicing may be done in reverse order:
[10:0:-1] is a slice form index 10 down to index 0 included with a step of -1.

Bounds as well as step values may be omitted:
[4::2] is a slice from index 4 up to max index included, with a step of 2 (i.e. indexes 4, 6, 8, …; max index being the default value for end)

[::2] is a slice from index 0 up to max index included, with a step of 2 (i.e. indexes 0, 2, 4, …; 0 being the default for start value and max index being the default one for end)

[0:10] is a slice from index 0 up to index 10 included, with a step of 1 (1 is the default step)

[:] is a slice from index 0 up to max index included, with a step of 1 (these are the three respective default values for start, end and step).

Last exemple:
[::10] is a slice from index 0 up to max index included, with a step of 10.

Then, about slicing in a list:

list the_list = [ [ 0, 1, 2],
                  [10,11,12],
                  [20,21,22],
                  [30,31,32] ];

print( the_list [0:2] );
// prints "[[0, 1, 2], [10, 11, 12], [21, 21, 22]]"

print( the_list [3:2:-1] );
// prints "[[30, 31, 32], [20, 21, 22]]"

print( the_list [0:1][0:2) );
// prints "[[0, 1], [10, 11]]"

the_list [1:2][1] = [100, 100];

print( the_list );
// prints "[[0, 1, 2], [10, 100, 12], [20, 100, 22], [30, 31, 32]]"

print( the_list [2][2:0:-1) );
// prints "[22, 21]", last index (0) being excluded from the slice

print( the_list [2][-1:-3:-1) );
// prints "[22, 21]", last index (-3) being excluded from the slice

4.2.2.3 Comprehension

Comprehension is also a well known concept in Python. It selects items according to some condition within a range.
Let us see a few complete examples:

list the_list = [ [ 0, 1, 2],
                  [10,11,12],
                  [20,21,22],
                  [30,31,32] ];

for( uint8 i in [0:3] ) {
    print( i, '-', the_list [i][j] if( j > 0 ) for( uint8 j in [0:2] ) );
// prints:
// "0 - 1 2
//  1 - 11 12
//  2 - 21 22
//  3 - 31 32"

print( i, '-', the_list [i][j]
                   for( uint8 j in [0:2] )
                       for( uint8 i in [0:3] )
                           if( the_list [i][j] > 20) );
// prints:
// "0 - 
//  1 - 
//  2 - 21 22
//  3 - 30 31 32"

A special case is when a parenthesis form is used after keyword in. Python programmers know this as function zip() which runs through many lists simultaneously. If passed lists in the parenthesis form are of different lenghts, shorter lists are completed with value none.

Let’s have a simple exemple:

list<uint8> indexes = [ 1, 3, 127, 255, 24, 0 ];             // 6 items
list<str> strings = [ "first", "third", "one twenty-seventh",
                      "two fifty-fifth", "twenty-fourth" ];  // 5 items

map table = [ i: s for( uint8 i, str s in (indexes, strings) ) ];
print( table.sort() );
// prints:
//  [ 1: "first", 3: "third", 24: "twenty-fourth", 
//    127: "one twenty-seventh", 255: "two fifty-fifth" ]

Comprehension is a powerfull concept originated by Python that you will really enjoy to use once you will get used to. It allows very concise and very sure programmation.

4.2.3 Lists Iterations

Lists are iterable. Iterating through a list is done via statement for.

A one-dimensional list can be fully iterated this way:

list the_list = [ 0, 1.0, 2.3, 'quatre', '5', [[6,7], 8, [9]] ];

for( uint32 item in the_list )
    print( item );
// prints 0, 1.0, 2.3, 'quatre', '5', [[6, 7], 8, [9]]

Iterating multiple dimensional lists acts the same, but the iterating runs through external dimensions first. For instance:

const uint8 LINES = 4;
const uint8 COLS  = 3;

//-- using comprehension (which is great programming):list the_list =
    [ [10*i+j for( uint16 j in [0:COLS) )] for( uint16 i in [0:LINES) )];

//-- using classical for loops (which is conventional programming):
for( list line in the_list ) {
    // iterating is done on first dimension
    // the iteration runs then through lines

    for( ? cell_value in line ) {
        // iterating is done then on second dimension
        // the iteration is done through the extracted line
        // and every returned item is the value contained in current cell
        print( cell_value );
    }

    print();
}

// prints on successive lines the whole content of the list
// - first line first, one cell value per line,
//   with a line gap before second line
// - next lines then, one cell value per line,
//   with a gap line between each of them

4.2.4 Lists Manipulations

Typee provides built-in functions and operators for the manipulation of lists. They are of a few kinds and are all presented in next sub-sections. They all are available whatever the type of the contained items in a list, except for statistics functions which are available for only integer and float contained values. Notice: objects may be turned into integers or floats via cast operators and hash operator. More about this at related sub-sections.

All of these functions are methods-like. They can be applied to a list as would be built-in methods:
my_list.list_function(...)

4.2.4.1 List emptying and deleting

list empty()

Empties the list: every item contained in it is deleted. This may lead to a call to their destructors when they are instancies of classes that define a destructor. Programmers have to take care there because some items may have been previously referenced in code. These references will then reference released resources (most of the time, memory space) and should not be later accessed in the code.
Example:

list my_list = [ 0.1, 2, '3', 'four' ];
print( my_list.empty() );  // prints: []

delete

del

Typee instruction delete applied to a list deletes the list and all its content. This may lead to a call to their destructors when they are instancies of classes that define a destructor. Programmers have to take care there because some items may have been previously referenced in code. These references will then reference released resources (most of the time, memory space) and should not be later accessed in the code.
Keyword del is a wrapper to keyword delete.
Example:

list my_list = [ 0.1, 2, '3', 'four' ];
del my_list;
print( my_list );  // prints: none

4.2.4.2 List concatenating

list operator + ( list left, list right )

The concatenation of lists is operated by Typee operator +. It creates a new list which is the concatenation of lists left and right.
Example:

list my_list = [0.1, 2];
print( my_list + ['3', 'four'] );  // prints: [0.1, 2, ['3', 'four']]

list operator += ( list other )

The in-place concatenation of lists is operated by Typee operator +=. The argument list other is appended at the end of the operated list. This operator returns a reference to the operated list.
Example:

list my_list  = [0.1, 2];
list my_list2 = [3, 4.0];
my_list += my_list2;
print( my_list );  // prints: [0.1 2 3 4.0]

4.2.4.3 Items appending, inserting, picking, poping, pushing, deleting

Lists are of variable length. Items of any type may be inserted in them, appended to them at their end or removed from them. When comparing lists and arrays, these operations are specific to lists and are not available for arrays.

list append( const ? item )

list operator << ( list left, const ? right )

list operator <<= ( list left, const ? right )

Item may be of any type. It is appended at the end of the operated list.
The streaming operators << and <<= append the item argument right at the end of the list argument left.
Function append() returns a reference to the operated list, so that function calls may be cascaded.
Operator << returns also reference to the operated list, so that it can be cascaded.
Operator <<= operates in-place.
Example:

list my_list;
my_list.append( 0.1 ).append( 2 ).append( '3' ).append( 'four' );
print( my_list );  // prints: [0.1, 2, "3", "four"]
my_list <<= 5;
print( my_list );  // prints: [0.1, 2, "3", "four", 5]

list insert( ? item )

Item may be of any type. It is inserted at the head of the operated list, right before its first item.
This function returns a reference to the operated list, so that function calls may be cascaded.
Example:

list my_list = [ 0.1, 2, '3', 'four' ];
my_list.insert( 5 );
print( my_list );  // prints: [5, 0.1, 2, "3", "four"]

list insert( uint64 n, const ? item )

Item may be of any type. It is inserted right before the n-th item in list. Indexes start at 0. So, insert(item) is equivalent to insert(0,item). Indexes may be negative, starting at -1, in which case indexes are counted from the end (or tail) of the list.
This function returns a reference to the operated list, so that function calls may be cascaded.
This function raises an exception OutOfBoundsException if n is out of bounds.
Example:

list my_list;
my_list.insert( 0.1 ).insert( 2 ).insert( '3' ).insert( 'four' );
print( my_list );  // prints: ["four", "3", 2, 0.1]
my_list.insert( 2, 5 );
print( my_list );  // prints: ["four", "3", 5, 2, 0.1]
my_list.insert( -1, ["six", 7] );
print( my_list );  // prints: ["four", "3", 5, 2, ["six", 7], 0.1]

? pick( uint64 n )

This function removes the n-th item from the list and returns it to the caller. Indexes may be negative, starting at -1, in which case indexes are counted from the end (or tail) of the list.
This function raises an exception OutOfBoundsException if n is out of bounds.
Example:

list my_list = [0.1, 2, "3", "four"];
print( my_list.pick(1), my_list );  // prints: 2 [0.1, "3", "four"]]

? pickitem( const ? item )

This function removes the first occurrence of item from the list and returns a reference to it. Search for the item starts at head of list (i.e. at index 0).
This function raises an exception NotFoundException if item is not found.
Example:

list my_list = [0.1, 2, "3", "four", 2];
print( my_list.pickitem(2), my_list );  // prints: 2 [0.1, "3", "four", 2]

? pop()

ItemT pop< ItemT >()

Removes the ending item of the list and returns a reference to it. If list is empty, returns none.
The templated form of this function returns the last item of type ItemT found in the list and removes it from the list. Returns none if no item of type ItemT exists in the list. In this last case, the list is not modified.
Example:

list my_list = [0.1, "four"];
print( my_list.pop(), my_list );  // prints: four [0.1]
print( my_list<str>.pop(), my_list );  // prints: none [0.1]
print( my_list.pop(), my_list );  // prints: 0.1 []
print( my_list.pop(), my_list );  // prints: none []

list push( ? item )

This is the pendant of function pop() and is a wrapper to append(). The item is appended at the end of the list.
Example:

list my_list = [0.1, 2, "3", "four"];
my_list.push( 'five' );
print( my_list );                 // prints: [0.1, 2, "3", "four", "five"]
print( my_list.pop(), my_list );  // prints: five [0.1, 2, "3", "four"]

delete

del

Typee statement delete and its wrapper del delete indexed (or sliced) items from list.
If index or slice is out of bounds an exception OutOfBoundsException is raised. This may be detected at translation time, in which case Typee translators will set en error. But most of the time, this will not be detectable before run-time. The exception will then be raised.
Examples:

list my_list = [0.1, 2, "3", "four", 2];
del my_list[1:3); // notice that index 3 is excluded from slice
print( my_list );  // prints: [0.1, "four", 2]
del my_list[-2]; // notice the inversed indexing
print( my_list );  // prints: [0.1, 2]

list delitem( const ? item )

This function removes the item from the list, searching it from the head of the list. It returns a reference to the list for function calls to be cascadable. If item is not found, an exception NotFoundException is raised. This may be detected at translation time for a very few cases. Typee translators will then set en error. But most of the time, this will not be detectable before run-time. The exception will then be raised.
Example:

list my_list = [0.1, 2, "3", "four", 2];
my_list.delitem( 2 ).delitem( "four" );
print( my_list );  // prints: [0.1, "3", 2]

list reverse_delitem( const ? item )

This function removes the item from the list, searching it from the end of the list. It returns a reference to the list for function calls to be cascadable. If item is not found, an exception NotFoundException is raised. This may be detected at translation time for a very few cases. Typee translators will then set en error. But most of the time, this will not be detectable before run-time. The exception will then be raised.
Example:

list my_list = [0.1, 2, "3", "four", 2];
my_list.reverse_delitem( 2 ).reverse_delitem( "3" );
print( my_list );  // prints: [0.1, 2, "four"]

4.2.4.4 Items counting

How many items in a list?

const uint64 count()

const uint64 count< ItemT >()

Returns the number of items contained in a list.
Example:

list<uint8> grey_image = [ [0x80 for( uint16 col in [1:256] )]
                                     for( uint16 line in [1:256] ) ];
// this is a list of 256 lines of 256 pixels each
print( grey_image.count() );  // prints: 65536

const uint64 count( const ? item )

Returns the number of occurences of argument item contained in a list.

Example:

list<uint8> matrix = [ [1,0,0], [0,1,0], [0,0,1] ];
print( matrix.count(0), matrix.count(1), matrix.count(2) );  // prints: 6 3 0

4.2.4.5 Items searching

Is some item present in an list? What is the index of the first found one? What are the indexes of many of them? What are the indexes of all of them?

const bool operator in ( const ? item, list container)

Operator keyword in checks for the presence of an item into a list. Result is either true if item has been found in the list and false otherwise.
Examples:

list<uint16> the_list = [0,1,2,3];
print(  2 in the_list );  // prints true
print( 10 in the_list );  // prints false

list<uint8> the_list = [ [0,1], [10,11] ];
print(  2 in the_list );  // prints false
print( 10 in the_list );  // prints true

const bool operator not in ( const ? item, list container)

The association of these two keywords is the counterpart of keyword in.
Examples:

list<uint16> the_list = [0,1,2,3];
print(  2 not in the_list );  // prints false
print( 10 not in the_list );  // prints true

list the_list = [ [0,1], [10,11] ];
print(  2 not in the_list );  // prints true
print( 10 not in the_list );  // prints false

const ? in (uint64, list<uint64>) index( const ? item )

Returns the index in the list of the first found occurence of argument item. Returns special value none if item is not found in the list.
Example:

list<uint16> the_list = [0,10,20,30];
print( the_list.index( 2) );  // prints none
print( the_list.index(10) );  // prints 1

list the_list = [ [0,1], [10,11] ];
print( the_list.index( 2) );  // prints none
print( the_list.index(10) );  // prints [1,0]

const list indexes( const ? item, const uint64 n_max )

Returns a list of indexes of the n_max first ocurences of argument item in the list. If none is found, returns an empty list.
Example:

list<uint8> unit_mat =
    [ [1,0,0],
      [0,1,0],
      [0,0,1] ];
print( unit_mat.indexes(1,2) );      // prints [[0,0], [1,1]]
print( unit_mat.indexes(0,3) );      // prints [[0,1], [0,2], [1,0]]
print( unit_mat[-1:].indexes(0,3) ); // prints [[2,1], [2,0], [1,2]]

const list indexes( const ? item )

Returns the list of indexes of all occurences of argument item in the the list. If none is found, returns an empty list.
Example:

list unit_mat =
    [ [1,0,0],
      [0,1,0],
      [0,0,1] ];
print( unit_mat.indexes(1) ); // prints [[0,0], [1,1], [2,2]
print( unit_mat.indexes(0) ); // prints [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]
print( unit_mat[-1:].indexes(1) ); // prints [[2,2], [1,1], [0,0]]

4.2.4.6 Items clearing

list clear()

Sets all items contained in the list to their “default” value. Returns a reference to the operated list for calls to methods to be cascadable.

• for integers, the default value is 0
• for floats, the default value is 0.0
• for chars, the default value is ' '
• for strings, the default value is the empty string ""
• for containers, the default value is the empty container except for lists, for which every item is set to its default value
• for instances of classes, the default value is the instance created with the “default” constructor (the one with no arguments. If no default constructor is defined, then the default value is none

Example:

list<uint8> unit_mat = [ [9, 9], [9, 9] ];
unit_mat.clear();
print( unit_mat ); // prints [[0,0, [0,0]]
unit_mat[0][0] = unit_mat[1][1] = 1;
print( unit_mat ); // prints [[1,0, [0,1]]

4.2.4.7 List copying and referencing

Copying a list means creating a new list with same size in heap or stack memory, then duplicate the whole content from origin to destination. Any transformation done then on one of the lists will not modify the other one.

Referencing a list is to understand as creating an alias or defining a pointer to the original list. Any transformation applied then to the list will be reflected through its reference. Any transformation applied also to its reference will be applied in the original list.

Syntax is straightforward. Let’s illustrate it with simple examples:

list<uint8> src_list = [0, 1, 2, 3];
list<uint8> dst_list;

dst_list = src_list;          // list copy
dst_list[0] = 10;
print( src_list, dst_list );  // prints [0,1,2,3] [10,1,2,3]

dst_list = &src_list;         // list reference
print( src_list, dst_list );  // prints [0,1,2,3] [0,1,2,3]
src_list = [10, 20, 30, 40];
dst_list[0] = 100;
print( src_list, dst_list );  // prints [100,20,30,40] [100,20,30,40]

4.2.4.8 List sorting

There are two main classes of sorting algorithms: unstable and stable. Stable sorting means that equal items will stay ordered the same way they where before sorting. Such sorts are most of the time a little bit slower than unstable sorts, but they are much appreciated because of this particular main characteristic.

It appears that some other programming languages offer by default a stable sorting function, based on the Timsort algorithm. This is a hybrid algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. (source: Wikipedia). This algorithm had been first introduced in [1] by Peter McIlroy in 1993 and had been implemented by Tim Peters (Timsort…) in 2002 for the Python sort() built-in function. Since then, this algorithm has been enhanced (a bug has been found) and has also been implemented for Java.
[1]: “Optimistic Sorting and Information Theoretic Complexity“, Peter McIlroy, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 467–474, January 1993.

So, it may be that the unstable sorting function built in Typee will finally be translated into a stable version of a sorting algorithm, depending on the targeted programming language. This will enventually be the case when translating Typee code to Python and Java.

Notice that whatever the function used to sort a list, the list is always sorted in-place, i.e. the content of the list is directly modified. Applying a sort on a reference to a list will sort the original list as well. Then, sorting a constant list is illegal in Typee – such lists are unmutable.

list sort()

This is the basic sort function in Typee. Lists are sorted in the ascending order of their content. The result of sorting is a sorted list containing items in their ascending order.
Example:

list<uint8> the_list = [8, 4, 5, 2, 8, 0, 1, 7, 3];
the_list.sort();
print( the_list );  // prints [0, 1, 2, 3, 4, 5, 7, 8, 8]

It can be applied to any list for which content is comparable. This is the case for every scalar types in Typee: integers, floats, chars, strings and booleans (false is smaller than true in Typee). It is the case also for any object that is an instance of a class for which at least the comparison operator < or the hashing operator # have been defined. For instance:

class C {
    C ( const int16 value ) {
        me.val = value;
    }

    const bool operator < ( const C other ) {
        return me.val < other.val;
    }

    private int16 val;
}

Some programming language do not provide comparators for different scalar types (e.g. between integers and strings). If no such comparator is available, Typee compares values against their hash values. If some item is not hashable, a TypeException will be raised at run-time unless this will have been detected before, at translation time, in which case Typee translators will set en error.

About sorting multi-dimensional lists, let’s illustrate this with an example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
the_list.sort()
print( the_list );  // prints: [ [2, 4, 5, 8], [0, 1, 7, 8] ]

list sort( const int32 comp_func(const ?, const ?) )

liqst sort( const int32 comp_func< ItemT >(const ItemT, const ItemT) )

These signatures of built-in function sort() specifies the comparison function to be used for the sorting operation. Comparison functions here have to accept two arguments of any type with a constraint: these arguments have to be comparable together. If they are not, either a type error will be set at translation time or (most often) a TypeException will be raised at run-time. Be cautious there. These comparison functions are expected to return a signed integer value:

• less than 0 if first argument is less than second one;
• equal to 0 if both arguments are equal;
• greater than 0 if first argument is greater than second one.

list stable_sort()

This function is the stable version of function sort(). It is applicable the same way than sort().

list stable_sort( const int32 comp_func(const ?, const ?) )

list stable_sort( const int32 comp_func< ItemT >(const ItemT, const ItemT) )

This function is the stable version of function sort() with a comparison function as argument. It is applicable the same way than sort().

list reverse_sort()

This is the counter part of function sort(). It sorts lists in a descending order. It can be applied to any list for which content is comparable. This is the case for every scalar types in Typee: integers, floats, chars, strings and booleans (false is smaller than true in Typee). It is the case also for any object that is an instance of a class for which at least the comparison operator < or the hashing operator # have been defined.

list reverse_sort( const int32 comp_func(const ?, const ?) )

list reverse_sort( const int32 comp_func< ItemT >(const ItemT, const ItemT) )

This is the counter part of function sort() when passed a comparison function as argument. It sorts lists in the reverse order that the comparison function results in.

list reverse_stable_sort()

This function is the stable version of function reverse_sort(). It is applicable the same way.

list reverse_stable_sort( const int32 comp_func(const ?, const ?) )

list reverse_stable_sort( const int32 comp_func< ItemT >(const ItemT, const ItemT) )

This function is the stable version of function reverse_sort() with a comparison function as argument. It is applicable the same way.

4.2.4.9 List and apply

Method apply() is a generic method for containers. It helps applying a same function to every item contained in a container.

list apply( none func( ? item, const uint64 item_index, … args) )

list<ItemT> apply( none func( ItemT item, const uint64 item_index, … args) )

func is a reference to a function that takes as parameters a reference to the currently processed item in the list, its index and any other argument that would be useful for its processing.
The templated form of this function only applies to the items of type ItemT that are contained in the list.
Returns a reference to the list that has been modified in-place.

Examples:

//-- 1st Example --
list<uint32> buf32 = [0,1,2,3,4,5,6,7,8,9];

none plusN (uint32 val, const uint64 index, const int32 n)
{
    val += n;
}

print( buf32.apply( plusN, 10 ) );
// prints: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

//-- 2nd Example --
print(
    buf32.apply(
        unnamed( uint32 item, const uint64 index, list<uint32> container ){
            if (index > 0)
                item += container[ index - 1 ];
        },
        buf32
    )
);
// prints: [10, 21, 33, 46, 60, 75, 91, 108, 126, 145]

Explanations:
In the first example, a constant value 10 is added to each item of the list. The defined function plusN is used for this, a reference to it being passed to method apply(). A second argument is passed to apply(): this is the constant value to be added to the items of the list and which is passed as a complementary argument to the applied funciton plusN(). Once completed, method apply() returns a reference to the list which is used for its printing.

In the second example, an unnamed function is declared in the arguments list of method apply(). This unnamed function accepts three arguments: the two mandatory ones item and index of the item, plus as a third one: a reference to the processed list itself.
This function successively adds the content of two consecutive items of the list and assigns the result to the currently processed item. Once completed, method apply() returns a reference to the processed list which is used for the printing of its new content.

We can see in this second example the internal functionning of apply(). It operates on the list items sequentially, starting from first item up to its last one. This is something like:

class list {
  // ...

  list apply( none func( ? item, const uint64 item_index, ... args)
  {
    for( const uint64 item_index, ? item in indexed(me) )
      func( item, item_index, args );
    return me;
  }

  list<T> apply( none func( T item, const uint64 item_index, ... args)
  {
    for( const uint64 item_index, T item in indexed(me) )
      func( item, item_index, args );
    return me;
  }

  // ...
}

4.2.4.10 List statistics

A few statistics functions are available in Typee with lists.

const uint64 size()

Returns the size of the list in memory with bytes as the measure unit.
Caution: while the returned value will be exact for lists containing char, integer and float scalars, it might be not exact for strings, booleans and instances of classes. The memory space reserved for these last entities may greatly vary according to the targeted language and the final compilers or interpretors implementations which can’t be exactly known at translation time.

Example:

list<uint32> buf32 = [0,1,2,3,4,5,6,7,8,9];
print( buf32.size() );                   // prints 40
list<uint8> buf8 = [0,1,2,3,4,5,6,7,8,9];
print( buf8.size() );                    // prints 10

const ? min()

const ItemT min< ItemT >()

Returns the minimum value contained in a list. If the list contains objects rather than scalar values, the class that these objects inherit from must own a defined comparison operator <. If not, this class must otherwise define at least one char, string, integer or float casting operator or the hash operator #. If many are defined, priority for the casting before comparision will be hash first and char last, in the inverse order of previous list. If no such operator is defined, an error will occur at translation time.
The templated form of this function returns the minimum value of all items of type ItemT.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.min() );            // prints: 0
print( the_list[0].min<uint8>() );  // prints: 2

const ? in (uint64, list) argmin()

const ? in (uint64, list) argmin< ItemT >()

const ? in (uint64, list) indexmin()

const ? in (uint64, list) indexmin< ItemT >()

Returns the index of the first minimal value found in a list. If the list contains objects rather than scalar values, the class these objects inherit from must own a defined comparison operator <. If not, this class must otherwise define at least one char, string, integer or float casting operator or the hash operator #. If many are defined, priority for the casting before comparision will be hash first and char last, in the inverse order of previous list. If no such operator is defined, an error will occur at translation time.
The templated versions of these functions only apply to items of type ItemT that are contained within the list.
argmin is the “mathematical” name of this function which may also be named indexmin as well.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list<uint8>.argmin() );     // prints: [0,3]
print( the_list[1].argmin() );         // prints: 1

const list argsmin()

const list argsmin< ItemT >()

const list indexesmin()

const list indexesmin< ItemT >()

Returns the index of all minimal values found in a list. If the list contains objects rather than scalar values, the class these objects inherit from must own a defined comparison operator <. If not, this class must otherwise define at least one char, string, integer or float casting operator or the hash operator #. If many are defined, priority for the casting before comparision will be hash first and char last, in the inverse order of previous list. If no such operator is defined, an error will occur at translation time.
The templated versions of these functions only apply to items of type ItemT that are contained within the list.
argsmin is the “mathematical” name of this function which may also be named indexesmin as well.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.argsmin() );            // prints: [[0,3],[1,1]]
print( the_list[0]<uint8>.argsmin() );  // prints: [3]

const ? max()

const ItemT max< ItemT >()

Returns the maximum value contained in a list. If the list contains objects rather than scalar values, the class that these objects inherit from must own a defined comparison operato  <. If not, this class must otherwise define at least one char, string, integer or float casting operator or the hash operator #. If many are defined, priority for the casting before comparision will be hash first and char last, in the inverse order of previous list. If no such operator is defined, an error will occur at translation time.
The tempalted version of this function returns the max of the sole items of type ItemT that are contained in the list.

Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.max() );  // prints: 8

const ? in (uint64, list) argmax()

const ? in (uint64, list) argmax< ItemT >()

const ? in (uint64, list) indexmax()

const ? in (uint64, list) indexmax< ItemT >()

Returns the index of the first maximal value found in a list. If the list contains objects rather than scalar values, the class these objects inherit from must own a defined comparison operator <. If not, this class must otherwise define at least one char, string, integer or float casting operator or the hash operator #. If many are defined, priority for the casting before comparision will be hash first and char last, in the inverse order of previous list. If no such operator is defined, an error will occur at translation time.
The templated versions of these functions only apply to items of type ItemT that are contained within the list.
argmax is the “mathematical” name of this function which may also be named indexmax as well.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.argmax() );     // prints: [0,0]
print( the_list[1].argmax() );  // prints: 0

const list argsmax()

const list argsmax< ItemT >()

const list indexesmax()

const list indexesmax< ItemT >()

Returns the index of all maximal values found in a list. If the list contains objects rather than scalar values, the class these objects inherit from must own a defined comparison operator <. If not, this class must otherwise define at least one char, string, integer or float casting operator or the hash operator #. If many are defined, priority for the casting before comparision will be hash first and char last, in the inverse order of previous list. If no such operator is defined, an error will occur at translation time.
The templated versions of these functions only apply to items of type ItemT that are contained within the list.
argsmax is the “mathematical” name of this function which may also be named indexesmax as well.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.argsmax() );     // prints: [[0,0], [1,0]]
print( the_list[0] );            // prints: [0]

const float64 mean()

Evaluates the mean over the whole list. Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.mean() );     // prints: 4.375
print( the_list[0].mean() );  // prints: 4.75

const float64 stdev()

Evaluates the standard deviation over the whole list. Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.stdev() );     // prints: 3.1594529
print( the_list[0].stdev() );  // prints: 2.5

const float64 median()

Evaluates the median value over the whole list. The computed value may not belong to the list – see median_low() and median-high() to get median value belonging to the list.
Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.median() );     // prints: 4.5
print( the_list[1].median() );  // prints: 4.0

const ? medianlow()

const ItemT medianlow< ItemT >()

Evaluates the median value over the whole list. The computed value is forced to belong to the list and is the highest contained value that is less than the true median value – see examples.
The templated version of this function only applies to items of type ItemT that are contained in the list.
Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.medianlow<uint16>() );     // prints: 4
print( the_list[1].medianlow() );          // prints: 1

const ? medianhigh()

const ItemT medianhigh< ItemT >()

Evaluates the median value over the whole list. The computed value is forced to belong to the listand is the lowest contained value that is greater than the true median value – see examples.
The templated version of this function only applies to items of type ItemT that are contained in the list.
Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.medianhigh() );            // prints: 5
print( the_list[1].medianhigh<uint8>() );  // prints: 7

const ? in (uint64, list) argmedianlow()

const ? in (uint64, list) argmedianlow< ItemT >()

const ? in (uint64, list) indexmedianlow()

const ? in (uint64, list) indexmedianlow< ItemT >()

Returns the index of the first value found in a list that is the greatest of all values that are lower than the true median value – see examples.
The templated versions of these functions only apply to items of type ItemT that are contained within the list.
Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
argmedianlow and indexmedianlow are two available names for the same function.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.argmedianlow() );     // prints: [0,1]
print( the_list[1].argmedianlow() );  // prints: 2

const list argsmedianlow()

const list argsmedianlow< ItemT >()

const list indexesmedianlow()

const list indexesmedianlow< ItemT >()

Returns the indexes of all values found in a list that are the greatest of all values that are lower than the true median value – see examples.
The templated versions of these functions only apply to items of type ItemT that are contained within the list.
Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
argsmedianlow and indexesmedianlow are two available names for the same function.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 4, 7] ];
print( the_list.argmedianlow() );     // prints: [[0,1], [1,2]]
print( the_list[1].argmedianlow() );  // prints: [2]

const ? in (uint64, list) argmedianhigh()

const ? in (uint64, list) argmedianhigh< ItemT >()

const ? in (uint64, list) indexmedianhigh()

const ? in (uint64, list) indexmedianhigh< ItemT >()

Returns the index of the first value found in a list that is the lowest of all values that are greater than the true median value – see example.
The templated versions of these functions only apply to items of type ItemT that are contained within the list.
Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
argmedianhigh and indexmedianhigh are two available names for a same function.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 7] ];
print( the_list.argmedianhigh() );     // prints: [0,2]
print( the_list[1].argmedianhigh() );  // prints: 3

const list argsmedianhigh()

const list argsmedianhigh< ItemT >()

const list indexesmedianhigh()

const list indexesmedianhigh< ItemT >()

Returns the indexes of all values found in a list array that is the lowest of all values that are greater than the true median value – see examples.
The templated versions of these functions only apply to items of type ItemT that are contained within the list.
Lists have to contain either integer or float values. Such values may be obtained via integer or float casting operators defined in classes from which inherit the objects that are contained in the list. When cast operators exist, the related casting will be silently applied by Typee translators. If many casting operators are defined, the largest floating one will be first and if none is defined, the largest integer one will be applied.
argsmedianhigh and indexesmedianhigh are two available names for a same function.
Example:

list<uint8> the_list = [ [8, 4, 5, 2], [8, 0, 1, 5] ];
print( the_list.argsmedianhigh() );     // prints: [[0,2], [1,3]
print( the_list[1].argsmedianhigh() );  // prints: [3]

4.2.5 Lists as arguments

Functions and methods signatures are constituted of the types of their arguments and the type of value they return. Lists may be passed as arguments to functions and methods and may be passed back to caller on return. Keyword list is a generic type to specify any kind of list, whatever its size and the maybe declared types for its content.

 
Next section formerly explains built-in maps.

< previous (4.1 built-in arrays) | (4.3 built-in maps) next >