6 Structured Types

6.1 Array Type

The array is a sequence type, like a list, but with a focus on the efficiency of indexing and slicing operations.

6.1.1 Array Literals

The general array type is written as Array['1], where '1 denotes a type variable (a pure polymorphic type). Each specific array in a program must have a specialized type, where this free type is fully determined.

Array literals syntax is similar to list literals. The only difference is that square brackets with hash symbols are used instead of square brackets.

{#
    [# #],
    [#1,2,3#],                      //  Array[Int]
    [#'a','b','c','d'#],            //  Array[String]
    [#[#1,2#],[#3,4,5#],[#6,7,8#]#] //  Array[Array[Int]]
#}

{# [#  #], [# 1, 2, 3 #], [# 'a', 'b', 'c', 'd' #], [# [# 1, 2 #], [# 3, 4, 5 #], [# 6, 7, 8 #] #] #}

6.1.2 Common Sequence Functions

Many of the presented list functions work with arrays as well:

Function / Type and Description

A = B

('1 * '1 -> Bool)
Equality comparison operator.

A != B

('1 * '1 -> Bool)
Inequality comparison operator.

empty

(Indexable['1]['2]['3] -> Bool)
Check if the collection is empty.

length

(Indexable['1]['2]['3] -> Int)
Get the collection size.

size

(Indexable['1]['2]['3] -> Int)
Get the collection size.

sub

(SequenceStr['2]['1] * Int * Int -> SequenceStr['2]['1])
Extracts the subsequence from given 0-based position and given length:
    sub(seq,pos,len)

A[ : B ]

(SequenceStr['2]['1] * Int -> SequenceStr['2]['1])
Extracts a suffix of the sequence with N elements:
    seq[N:]

A[ B : C ]

(SequenceStr['2]['1] * Int * Int -> SequenceStr['2]['1])
Extracts a sequence segment from Nth to (M-1)th element:
    seq[N:M]

A[ B : ]

(SequenceStr['2]['1] * Int -> SequenceStr['2]['1])
Extracts a prefix of the sequence with N elements:
    seq[:N]

A[ B ]

(Indexable['1]['2]['3] * '2 -> '3)
Extracts an element from the indexable collection:
    col[idx]

map

(Sequence['2]['1] * ('1 -> '3) -> Sequence['2]['3])
Map the function to sequence elements:
    map(seq,fun)

mapIdx

(Sequence['1]['2] * (Int * '2 -> '3) -> Sequence['1]['3])
Map the function to sequence elements:
    mapIdx(seq,fun)

zipWith

(Sequence['4]['1] * Sequence['4]['2] * ('1 * '2 -> '3) -> Sequence['4]['3])
Zips two sequences with given function:
    zipWith(seq1, seq2 ,fun)

foldr

(Sequence['3]['2] * ('2 * '1 -> '1) * '1 -> '1)
Right associative folding of sequence elements:
    foldr([a,b,c],fn,zero) = fn(a,fn(b,fn(c,zero)))

foldl

(Sequence['3]['2] * ('1 * '2 -> '1) * '1 -> '1)
Left associative folding of sequence elements:
    foldl([a,b,c],fn,zero) = fn(fn(fn(zero,a),b),c)

filter

(Sequence['2]['1] * ('1 -> Bool) -> Sequence['2]['1])
Extracts the sequence elements which satisfy the given condition.

filterMap

(Sequence['3]['1] * ('1 -> Bool) * ('1 -> '2) -> Sequence['3]['2])
Maps a function to sequence elements which satisfy the condition.
    mapFilter(seq,cond,fn) == map(filter(seq,cond),fn)

forall

(Sequence['2]['1] * ('1 -> Bool) -> Bool)
Check if the given condition applies to all sequence elements:
    forall(list,cond).

exists

(Sequence['2]['1] * ('1 -> Bool) -> Bool)
Check if there is any sequence element satisfying the condition:
    exists(sequence,cond)

count

(Sequence['2]['1] * ('1 -> Bool) -> Int)
Count the sequence elements satisfying the condition:
    count(seq,cond)

sort

(Sequence['2][Value['1]] -> Sequence['2][Value['1]])
Sort value sequence.

sortBy

(Sequence['2]['1] * ('1 * '1 -> Bool) -> Sequence['2]['1])
Sort the sequence using given comparator.

These functions are already presented for list type and will not be discussed in details again. Their usage on arrays is absolutely the same as on the lists.

6.1.3 Functions newArray and newArrayFn

Function / Type and Description

newArray

(Int * '1 -> Array['1])
Creates an array with given number of elements of given value:
    newArray(5,'a') == [# 'a', 'a', 'a', 'a', 'a' #]

newArrayFn

(Int * (Int -> '1) -> Array['1])
Creates an array with given number of elements and computes each of the elements using given function on its index:
    newArrayFn(5,\x:x*x) == [# 0, 1, 4, 9, 16 #]

Function newArray(n,x) returns an array with n elements, where all elements are set to x.

Function newArray(n,fn) returns an array with n elements, where element at position idx is initialized as fn(idx).

{#
    newArray( 5, 1 ),
    newArray( 5, 'a' ),
    newArrayFn( 5, \x:x ),             
    newArrayFn( 5, \x:x*x ),
    newArrayFn( 5, \x: random(5) )
#}

{# [# 1, 1, 1, 1, 1 #], [# 'a', 'a', 'a', 'a', 'a' #], [# 0, 1, 2, 3, 4 #], [# 0, 1, 4, 9, 16 #], [# 2, 2, 3, 3, 3 #] #}

6.1.4 Array Conversion Functions

Array and lists are similar but not the same types. They are both sequences, but have different internal structure. Arrays are assumed to have a fixed content, which is usually used for indexing and slicing, while lists are often used for decomposing to head and tail. The usual sequence operations work the same on both.

Moreover, the internal implementation of list type may be the same as for the array type. Depending on the context and the applied creation method, interpreter decides whether a list is structured as usual or as an array.

This is why there are functions for conversion of a list to an array an vice versa. To force the array organization of a list, transform it to array and then back to list: lst.asArray().asList().

Function / Type and Description

asArray

(List['1] -> Array['1])
Converts a list to an array.

asList

(Array['1] -> List['1])
Converts an array to a list.

{#
    [].asArray(),
    [##].asList(),
    [1,2,3].asArray(),
    [1,2,3].asArray().asList(),
    ['1','2','3'].asArray(),
    ['1','2','3'].asArray().asList(),
    [#1,2,3#] == [#1,2,3#],
    [#1,2,3#] == [#1,2,3,4,5#],
    [#1,2,3#] != [#1,2,3#],
    [#1,2,3#] != [#1,2,3,4,5#]
#}

{# [#  #], [], [# 1, 2, 3 #], [1, 2, 3], [# '1', '2', '3' #], ['1', '2', '3'], true, false, false, true #}

6.2 Map Type

The map is an indexable type. It has a catalog structure, where the elements are accessed by keys. Both keys and values can be of any valid type.

6.2.1 Creating a Map

Function createMap

There are no map literals in Wafl. The maps are usually created using the createMap function.

Function / Type and Description

createMap

(Array[Value['1]] * Array['2] -> Map[Value['1]]['2])
Create a catalog from given arrays.

Function createMap takes two arrays of the same size and creates a map with keys from the first array and the corresponding values from the second.

The elements are accessed by indexing.

In the following example, a map is created with string keys and list values. The map is indexed by some keys:

{#
    aMap['a'],
    aMap
#}
where {
    aMap = createMap(
        [# 'a', 'b', 'c' #],
        [#
            [1,2,3],
            [4,5],
            [6]
        #]
    );
}

{# [1, 2, 3], [<'a',[1, 2, 3]>, <'b',[4, 5]>, <'c',[6]>] #}

Map is not a safe type. The indexing operator behavior is not defined if a non-existing index is used.

Function groupBy

If it is necessary to categorize list elements according to some criteria, then it can be useful to create a map that has different values of the categorization criteria for keys, and the lists of categorized elements for values. This is what function groupBy computes.

Function / Type and Description

groupBy

(Sequence['3]['1] * ('1 -> '2) -> Map['2][List['1]])
Create a catalog from the sequence. Each catalog element is a list of all elements mapped to the key value by the given function.

For example, we will categorize a list of integers by their last digit:

{#  aMap, aMap[1] #}
where {
    aMap = (1..20).groupBy(\x:x%4);
}

{# [<1,[1, 5, 9, 13, 17]>, <2,[2, 6, 10, 14, 18]>, <3,[3, 7, 11, 15, 19]>, <0,[4, 8, 12, 16, 20]>], [1, 5, 9, 13, 17] #}

6.2.2 Using a Map

The usual way to use the maps is by indexing. However, if it is not clear what exact key values are allowed, then some other usage methods can be useful.

Functions keys and values

Function / Type and Description

keys

(Map['2]['1] -> Array['2])
Get map keys.

values

(Map['2]['1] -> Array['1])
Get map values.

key

(Map['2]['1] * Int -> '2)
Get Nth key (from 0).

value

(Map['2]['1] * Int -> '1)
Get Nth value.

Functions keys and values return the arrays used to construct the map.

Functions key(n) and value(n) return nth key (value) from the corresponding arrays. They are equivalent to indexing the arrays, like keys()[n] and values()[n].

{#
    aMap.keys(),
    aMap.key(0),
    aMap.values(),
    aMap.value(0)
#}
where {
    aMap = createMap([# 'a', 'b', 'c' #], [# 11, 22, 33 #]);
}

{# [# 'a', 'b', 'c' #], 'a', [# 11, 22, 33 #], 11 #}

Functions hasKey, hasValue, findKey and findValue

Function / Type and Description

hasKey

(Map['2]['1] * '2 -> Bool)
Check if there is a given key in the map.

hasValue

(Map['2]['1] * '1 -> Bool)
Check if there is a given value in the map.

findKey

(Map['2]['1] * '2 -> Int)
Find a position of the given key, or -1 if not found.

findValue

(Map['2]['1] * '1 -> Int)
Find a position of the given value, or -1 if not found.

Functions hasKey and hasValue check if there is a map key (value) with the given value.

Functions findKey and findValue look for the key (value) in the corresponding array and return the index of the found key (value), or -1 if it is not found.

So, if a key x exists in a map m, then must stand:

m.keys()[ m.findKey(x) ] == x m.key( m.findKey(x) ) == x

and same for the values.

{#
    aMap['a'],
    aMap.hasKey('a'),
    aMap.hasKey('A'),
    aMap['c'],
    aMap.findKey('c'),
    aMap.findKey('C')
#}
where {
    aMap = createMap([# 'a', 'b', 'c' #], [# 11, 22, 33 #]);
}

{# 11, true, false, 33, 2, -1 #}

6.3 Tuple Type

Tuple is a structured data type. It consists of a number of unnamed elements, which are referenced by position. Tuple elements may have different types.

6.3.1 Tuple Literals

Tuples are written using curly brackets with hashes: {# ... #}, and tuple elements are separated by commas. The elements can be listed as literals or as expressions.

Tuple must not be empty.

In the following example there is a tuple with three tuple elements of different types.

{#
    {# 1 #}, 
    {# 1 + 2,'a'+'b' #}, 
    {# 1,{# 'list',[1,2,3] #}#}
#}

{# {# 1 #}, {# 3, 'ab' #}, {# 1, {# 'list', [1, 2, 3] #} #} #}

The type of this tuple is:

Tuple[
    Tuple[Integer],
    Tuple[Integer, String],
    Tuple[Integer,Tuple[String,List[Integer]]]
]

6.3.2 Tuple Selectors

Tuple elements are accessed by tuple selectors. Because tuple elements are not named, their position is used to select them. Tuple elements positions are enumerated from 1.

Tuple selectors use dot-syntax <tuple>.<n>, with a positive integer number representing the position of the element to read.

{# 1, 2, 3, 4, 5 #}.f()
where{
    f(t) = {#
        t.1,
        t.1 + t.2,
        t.1 + t.2 + t.3,
        t.1 + t.2 + t.3 + t.4,
        t.1 + t.2 + t.3 + t.4 + t.5
    #};
}

{# 1, 3, 6, 10, 15 #}

The selector indexes and element types are check in type-checking phase, so it is not possible to have an invalid selector usage.

::note To support the syntax similar to records, the symbol ‘$’ can be used instead of dot. The two syntaxes are equivalent - x$1 is the same as x.1. :::

6.3.3 Tuple Updater

Tuple updaters are operator which replace one of the tuple elements with given value. They are called updaters but they do not modify the given tuple - they construct a new one with the copied and modified values instead.

Tuple updaters have the following basic syntax: <tuple>^<n>(<value>), with a positive integer number <n> representing the position of the element to replace and <value> representing the new value.

{# 
    {# 1, 2, 3 #}^1(11),
    {# 1, 2, 3 #}^2(22),
    {# 1, 2, 3 #}^3(33)
#}

{# {# 11, 2, 3 #}, {# 1, 22, 3 #}, {# 1, 2, 33 #} #}

As for selectors, the updaters indexes and types are check in type-checking phase, so it is not possible to have an invalid selector usage.

6.3.4 Tuple Type-Checking

Tuple data type is written as: Tuple[<el1-type>, <el2-type>, ..., <eln-type>]

If T1 is a tuple type with N elements, and T2 is another tuple type with K elements, where 0 < K < N, and for each i (0 < i <= K) the type of ith element of T1 is the same as the type of ith element of T2, then the T1 is subtype of T2.

If a selector works with tuple of type T2, then it will work for T1, too (it is obvious: the selector has index n <= K, so it is also n <= N and it works with T1). That same rule stands for updaters, too.

Moreover, if a function is defined to work with an argument of a tuple type, then it is applicable to subtypes of that type, too.

In the following example, the function f sums first two elements of a tuple. The function is applicable to all tuples with at least two elements, where, of course, the first two elements are of the same value type:

{#
    {# 1, 2 #}.f(),
    {# 1, 2, 3 #}.f(),
    {# 1, 2, 'a string' #}.f(),
    {# 1.2, 2.4, 'a string' #}.f(),
    {# 'a', 'b', 1.2, 2.4, 'a string' #}.f()
#}
where {
    f(t) = t.1 + t.2;
}

{# 3, 3, 3, 3.6, 'ab' #}

For example, the .2 selector and ^2 updater types are:

(TupleX['1,'2]['3] -> '2)
(TupleX['1,'2]['3] * 2 -> Tuple['1,'2]['3])

where TupleX means extendable tuple and '3 denotes an optional tuple extension type. This is required to allow the subtypes to work well.

On the other side, each created tuple will have an exact tuple type. For example, the tuple in the example has the type: Tuple[ Int, Int, Int, Float, String ].

6.4 Record Type

Record is a structured data type. It consists of a number of the named values. Record elements may have different types.

6.4.1 Record Literals

Records are written using curly brackets { ... }. Elements are separated by commas or semicolons. Each element has a name and a value. Names and values are separated by colons ‘:’ or equality sign ‘=’.

The syntax is flexible to be compatible with different languages, but it must be strictly followed - it is not allowed to combine different separators in a same record.

In the following example many different records are presented and different combinations of separators are used:

{
    fst: { a=1 }, 
    scd: { i:1, s:'a', trd:{ nme='list'; lst=[1,2,3] }}
}

{ fst: { a: 1 }, scd: { i: 1, s: 'a', trd: { lst: [1, 2, 3], nme: 'list' } } }

6.4.2 Record selectors

Record elements are accessed by record selectors. Record selectors uses names to access the elements. The syntax is similar to tuple selectors, but dot cannot be used here, so ‘$’ is used instead: <record>$<name>, where <name> is a record element name.

A selector .<name> is applicable to any record having an element with a specified name.

{ a:1, b:2, c:3, d:4, e:5 }.f()
where{
    f(t) = {#
        t$a,
        t$a + t$b,
        t$a + t$b + t$c,
        t$a + t$b + t$c + t$d,
        t$a + t$b + t$c + t$d + t$e
    #};
}

{# 1, 3, 6, 10, 15 #}

The selector names and element types are check in type-checking phase, so it is not possible to have an invalid selector usage.

6.4.3 Record Updaters

Record updaters are operators which replace one of the record elements with given value. As with tuple updaters, the record updaters do not modify the given record - they construct a new one with the copied and replaced values instead.

The basic form of record update selector is: <record>^<name>(<value>). A basic update selector ^name(...) is applicable to any record having an element with the specified name.

In an advanced form, a sequence of update selectors can be used. In that case, the syntax: R^a^b^c(x) is semantically equivalent to: R^a( R$a^b( R$a$b^c(x) ) ).

Please note that expressions R^a^b(x) and R$a^b(x) are not semantically equivalent. The first evaluates the record R where value of R$a$b is replaced with x. The second evaluates R$a where value of attribute b is replaced with x.

{#
    { a:1, b:2 }^a(5),
    { a:1, b:{x:2, y:3} }^b^x(5),
    { a:1, b:{x:2, y:3} }$b^x(5)
#}

{# { a: 5, b: 2 }, { a: 1, b: { x: 5, y: 3 } }, { x: 5, y: 3 } #}

6.4.4 Record Type-Checking

Record data type is written as:

Record[<name1>:<type1>, <name2>:<type2>, ..., <namen>:<typen>].

If R1 is a record type, and R2 is a record type with some of R1 elements, and with no other elements, then we say that R1 is subtype of R2.

If a selector (updater) works with R1, then it has to work with R2, too. Then, each function that works with R1 and uses its selectors an updaters will work on R2, too.

In the following example, the function f sums elements a and b of a given record. The function is applicable to subtypes, too. It is only required that the argument is a record with elements a and b of the same value type.

{#
    { a:1, b:2 }.f(),
    { q:1, b:2, a:3 }.f(),
    { a:1, b:2, s:'a string' }.f(),
    { a:1.2, b:2.4, s:'a string' }.f(),
    { a:'a', b:'b', x:1.2, y:2.4, s:'a string' }.f()
#}
where{
    f(t) = t$a + t$b;
}

{# 3, 5, 3, 3.6, 'ab' #}

If a function or any other context allows a record type, or its subtype, the type is usually annotated as: RecordX[name:type]['2], where RecordX means extendable record and '2 represents an optional record extension.

For example. the $name selector and ^name updater types are:

(RecordX[name:'1]['2] -> '1)
(RecordX[name:'1]['2] * '1 -> RecordX[name:'1]['2])

6.4.5 A Record Example

Tuple and record elements can have functional types. The following example uses a collection of named float functions to compute a table of their values.

apply( 
    [
        { name:"Id     "; fn:\x:x },
        { name:"Sine   "; fn:sin },
        { name:"Cosine "; fn:cos },
        { name:"Square "; fn:\x:x*x }
    ],
    [0.0, 0.5, 1.0, 1.5] 
)
where{
    apply( functions, values ) =
        functions
        .map(\fn [values]: fn$name + applyFn(fn$fn,values) )        
        .strJoin( '\n' )
    ;
    applyFn( fn, values ) =
        values
        .map( fn )
        .map( asString )
        .strJoin(' ')
    ;
}

Id     0 0.5 1 1.5
Sine   0 0.4794255386 0.8414709848 0.9974949866
Cosine 1 0.8775825619 0.5403023059 0.07073720167
Square 0 0.25 1 2.25