ExpandCollapseNext Index

+ 1.1 Arrays

Felix is using type classes to describe some array properties. The classes are in the file


The most basic class is {ArrayValue[t,v]} where t is the array type and v is the element value type. ArrayValue is the concept of an array as a value. It has two virtual functions:

    virtual fun len: t -> size; 
    Unchecked common indexing. 
    virtual fun unsafe_get: t * size -> v; 

Any type which wants to be considered as an ArrayValue simply instantiates these functions, and it automatically gets all the rest. These other derived methods are:

   Checked common indexing.
   fun get[I in ints] (x:t, i:I)
    Checked common indexing.
   fun apply [I in ints] (i:I, x:t) => get (x,i.size);
   Callback based value iterator.
   proc iter (_f:v->void) (x:t) 
   Callback based index and value iterator.
   Callback f index value.
   proc iiter (_f:size -> v->void) (x:t) {
   Stream  value iterator.
   gen iterator(xs:t) () : opt[v] = 
   Traditional left fold.
   fun fold_left[u] (_f:u->v->u) (init:u) (x:t): u = {
   Traditional right fold.
   fun fold_right[u] (_f:v->u->u) (x:t) (init:u): u = {
   Membership by predicate.
   fun mem(pred:v->bool) (x:t): bool = {
   Membership by relation to given value. 
   fun mem[u] (rel:v*u->bool) (x:t) (e:u): bool =>
   Array as Set:
   Membership by equality of value type.
   instance[with Eq[v]] Set[t,v] {
     fun \(\in\) (elt:v, a:t) => mem eq of (v * v) a elt;
   Searching for value satisfying relation to given value.
   fun find (rel:v*v->bool) (x:t) (e:v): opt[v] = {
   Searching for value satisfying predicate.
   fun find(pred:v->bool) (x:t): opt[v] = {

and more may be added.

+ 1.1.1 Getting an element by index.

The {get(a,i)} method is a checked version of the unsafe_get method.

The apply function is interesting. When you write:

    f a

where a has type A, and f has type {A -> X}, then {f a} is a function application. But suppose we want

    assert 1 (1,2,3,4) == 2;

that is, we want to apply an integer to an array as an index, which indeed we do want. When a value is syntactically applied to another value, and the type of the first value is NOT a function type, Felix tries to find an function named apply with a tuple argument consisting of the type of the applicator and the applicatee. In this case it tries to find a function that matches the name and signature

    apply: int * int ^ 4

This indeed matches the library function:

    fun apply [I in ints] (i:I, x:t) => get (x,i.size);

where {I in ints} means "any integer type". So the application

    1 (1,2,3,4)

is replaced by

    get ( (1,2,3,4),  1)

and we have that integers can be used "as projection functions" for arrays. And now we can write this too:

    (1,2,3,4) . 1

because Felix compiler has another piece of magic: when it sees:

    a . f

and a isn't a struct or record or pointer thereto, it consider the operator to mean "reverse application" and replaces it with

    f a

This is how Felix gets "OO like method calls" without any OO involved.

+ 1.1.2 Iteration

Next we have iter and iiter. These are your usual higher order functions which take a callback procedure as an argument and call it for every entry in the array. The iter function is called with each array value in sequence, the iiter function also gets the index. Here's an example:

  proc p(x:double) => 
    println$ "value="+ str x
  iter p (1.0,2.0,3.0,4.0);
  proc pp(i:size, v:int) => 
    println$ "index=" + str i + ", value="+str v
  iiter pp (1.0, 2.0, 3.0, 4.0);

The iterator function is a stream generator. For our sample array {(1,2,3,4)} it produces the infinite stream of values

    Some 1, Some 2, Some 3, Some 4, None, None, None .....

Generators work by assigning the generator to a variable and then repeatedly calling it through the variable, like this:

    var g = iterator (1,2,3,4);
    var v1 = g(); // Some 1
    var v2 = g(); // Some 2

although usually its done in a loop. Here is how you do it in a loop:

    for v in g do
      println$ v; 

This loop sets v to the argument of the Some value the generator produces until it gets a None, which signals the end of the stream. Felix also allows you to write it like this:

    for v in (1,2,3,4) do .. done

This works for any data type with a suitable method named "iterator". [BTW: do NOT call your variables "iterator", its a special name due to the above magic]

+ 1.1.3 Folds

The two folds are traditional fold operations, called "accumulate" in C++. However folds are purely functional. They accept a binary operator such as "add" which is used to aggregate the array values. Fold_left goes from left to right. Fold_right goes from right to left.

    val sum = 
        (fun (acc:double) (elt:double) => acc + elt) 
        (1.0, 2.0, 3.0, 4.0)
    val sum2 = 
        (fun (elt:double) (acc:double) => acc + elt) 
        (1.0, 2.0, 3.0, 4.0)

Note the order of arguments of both the fold and the argument function.

+ 1.1.4 Membership test

The first mem function test if the array contains a value that has the given property (predicate). The second one accepts a comparison and a value instead. The third one is the easiest to use and just uses the standard equality operator for the type (but of course only works if the type has a standard equality operator). You can also use the infix operator \in for this method. That is a TeX symbol and will be displayed as the usual "e" set membership operator by the Felix webserver.

+ 1.1.5 Searching

The two find functions are similar to the first two mem functions, only they return the first value in the array that matches the predicate as Some v, or None if there's no such value.

The following SHOULD be defined in the library but isn't:


which find the index of a matching value instead of the value, and


which returns both the index and value.