5 List Type

List is the most important and most frequently used structured data type in functional programming languages. List is a sequential type, which means that a list can contain many elements in an ordered sequence. In Wafl, a list can consist of elements of any type, but all elements of a list must have the same type.

Due to the importance of the concept of list processing, it is recommended to study this chapter carefully. The functions discussed here are essential for programming in Wafl.

5.1 List Literals

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

A list without elements is called an empty list. An empty list is written as nil or []. These two syntaxes are equivalent.

Non-empty list literals are written as elements enclosed in square brackets and separated by commas.

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

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

In the previous example we have the following lists:

• an empty [];
• an empty nil;
• a list of integers with 3 elements;
• a list of strings with 4 elements and
• a list of list of integers, with 3 elements.

5.2 Basic List Functions

The processing of list elements is often explained using the terms head and tail of the list. The head stands for the first element of the list and the tail stands for all but the first element of the list. Both head and tail only make sense for non-empty lists.

The basic list functions include elementary operations to check the list size, to extract its head, tail or a sub-list, to construct a list and to compare two lists.

List Comparison

Lists can be compared for equality. The operators == and != evaluate the expected results:

{#
    [] = nil,
    [] != nil,
    [] = [1,2,3],
    [] != [1,2,3],
    [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]
#}

{# true, false, false, true, true, false, false, true #}

empty

To check whether a list is empty, we can use the function empty(l) or compare the list with the empty list literal.

{#
    empty( [] ),
    empty( nil ),
    empty( [1,2,3] ),
    [] = nil
#}

{# true, true, false, true #}

size, length and longerThan

The function length(l) computes the length of the list. The function size(l) is a synonym.

{#
    length( [] ),
    length( nil ),
    length( [1,2,3] ),
    size( [1,2,3] )
#}

{# 0, 0, 3, 3 #}

In some cases, it is not efficient to compute the length of a list. For example, if a list is a result of a database query, the length can only be computed once the complete result has been retrieved from the database. In such cases, it is often useful to only check whether the length of the list is greater than a number. The function longerThan(lst,n) checks whether the list lst is longer than n and returns true if it is.

{#
    longerThan( [1,2,3], 0 ),
    longerThan( [1,2,3], 1 ),
    longerThan( [1,2,3], 2 ),
    longerThan( [1,2,3], 3 ),
    longerThan( [1,2,3], 4 ),
    longerThan( [1,2,3], 5 )
#}

{# true, true, true, false, false, false #}

hd, tl and A:B

The function hd(l) returns the first element of the given non-empty list. It is not defined for empty lists.

The function tl(l) computes the tail of the given non-empty list. The list tail is a list suffix consisting of all list elements except the first one. When applied to an empty list, it returns the same empty list.

The binary infix operator h:l constructs a list with head h and tail t. The type of the operator is ('1 * List['1] -> List['1]). It is often referred to as the cons-operator, as many functional programming languages have a function cons (constructs a list) that has the same behavior as this operator.

{#
    hd( [1,2,3] ),
    tl( [1,2,3] ),
    1:[2,3],
    1:2:3:nil,
    [2,3]:nil
#}

{# 1, [2, 3], [1, 2, 3], [1, 2, 3], [[2, 3]] #}

5.3 Basic List Processing

List elements are usually processed using recursion:

• the terminal condition is that the list is empty;
• if the list is not empty:
  • the first element of the list is processed and
  • the computation on the list tail is performed by recursive application of the same function.

We will try to apply this concept in some examples.

A List Sum

Let us sum the elements of an integer list by applying the presented concept:

• the terminal condition is the emptiness of the list;
  • the sum of the empty list is zero;
• if the list is not empty:
  • we add the head to the sum…
  • …of the tail, which is computed by recursive application.

[1,2,3,4,5].sum()
where {
    sum( lst ) = 
        if lst.empty() then 0
        else lst.hd() + lst.tl().sum();
}

15

A List of Squares

Let us compute a list of squares of natural numbers from 1 to 10. We can start from a list [1,2,...,10] and use a recursive function squares:

• the terminal condition is that the list is empty;
  • the squares of the empty list is an empty list;
• if the list is not empty:
  • we square the head and use it as the head of a new list…
  • …and the tail will be the squares of the tail.

[1,2,3,4,5,6,7,8,9,10].squares()
where {
    squares( lst ) = 
        if lst.empty() then []
        else lst.hd() * lst.hd() : lst.tl().squares();
}

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

The same result may be computed based on the same idea, but without explicitly writing a list literal:

squares(1,10)
where {
    squares( from, to ) = 
        if from > to
            then []
            else from * from : squares( from + 1, to );
}

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

An Integer Range

As in the previous example, it is often useful to have a list of integers in a given range. In this example the function mklst(n,m) computes the list of integers from n to m:

mklst(100,110)
where{
    mklst(n,m) =
        if n>m then []
        else n : mklst( n+1,m);
}

[100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110]

5.4 Advanced List Processing

In the examples of the previous section, we can recognize a certain repetitiveness. Let us focus on two topics:

1. how to process the head element and
2. how to combine the result of processing the head with the results for the rest of the list (tail).

It is common to approach these two topics with two different functions. First, we write the function processElements which processes each of the list elements and returns the results in a new list in the same order. Then we write the function combineElements, which combines the elements of the result list as needed.

The function processElements should have two arguments: the list of elements to be processed and the processing function. This function is similar to the squares function previously presented. So let us test it by applying it to the function \x:x*x:

[1,2,3,4,5].processElements( \x: x*x )
where {
    processElements( lst, fun ) = 
        if lst.empty() then []
        else lst.hd().fun() : lst.tl().processElements( fun );
}

[1, 4, 9, 16, 25]

The function combineElements should have three arguments: the list of elements to be combined, the function that describes the operation of combining and the start value. Let us test it on summation - the function is the operator+ and the start value is zero:

[1,2,3,4,5].combineElements( operator+, 0 )
where {
    combineElements( lst, fun, value ) =
        if lst.empty() then value
        else lst.hd().fun( lst.tl().combineElements( fun, value ) );
}

15

Now we can use both functions to sum the squares of the numbers in a given list:

[1,2,3,4,5]
.processElements( \x: x*x )
.combineElements( operator+, 0 )
where {
    processElements( lst, fun ) = 
        if lst.empty() then []
        else lst.hd().fun() : lst.tl().processElements( fun );
    combineElements( lst, fun, value ) =
        if lst.empty() then value
        else lst.hd().fun( lst.tl().combineElements( fun, value ) );
}

55

As we can see, these two functions are very helpful. For this reason, the equivalents of these two functions as well as many other higher order functions are implemented in the Wafl core library. The core library function map is equivalent to processElements, and foldr is equivalent to combineElements.

5.5 More List Functions

Some basic list functions were introduces in the previous section. Here we introduce some more complex list functions before we look at higher order functions in the following sections.

sub, subList

The function subList(l,p,n) returns a sublist of the given list, starting at position p and with n elements.

It has the same semantics as the already introduced sub and subStr for strings. In addition, sub also works for lists.

{#
    sub( [0,1,2,3,4,5,6,7], 0, 3 ),
    sub( [0,1,2,3,4,5,6,7], 2, 3 ),
    sub( [0,1,2,3,4,5,6,7], -2, 5 ),
    sub( [0,1,2,3,4,5,6,7], 5, 10 ),
    sub( [0,1,2,3,4,5,6,7], 5, -2 )
#}

{# [0, 1, 2], [2, 3, 4], [], [5, 6, 7], [] #}

List Index and Slice Operators

The index operator lst[i] and the slice operators lst[:n], lst[:n] and lst[n:m] have the same semantics as for strings, so we will not go into them in detail here.

Note that the indexing operator is not defined for empty lists.

{# 
  lst[-4], lst[-3], lst[-2], lst[-1],
  lst[0], lst[1], lst[2], lst[3], 
  lst[4], lst[6], lst[7], lst[8]
#}
where {
  lst = [0,1,2,3];
}

{# 0, 1, 2, 3, 0, 1, 2, 3, 0, 2, 3, 0 #}

{# 
    lst[:6],
    lst[:-2],
    lst[2:],
    lst[-6:],
    lst[2:6], 
    lst[2:-2], 
    lst[-6:6],
    lst[-6:-2]
#}
where {
  lst = [1,2,3,4,5,6,7,8];
}

{# [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [3, 4, 5, 6, 7, 8], [3, 4, 5, 6, 7, 8], [3, 4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6], [3, 4, 5, 6] #}

append, A ++ B and appendAll

The function append(l,r) returns a list containing all elements of the two lists in the given order. The binary infix operator ‘++’ does the same thing.

{#
    [1,2,3] ++ [4,5,6],
    append( [1,2,3], [4,5,6] )
#}

{# [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6] #}

The function appendAll(l) takes a list of lists and appends them from left to the right, in a same way as l.foldl(append,[]) does. All the functional characteristics of the appendAll are the same as if it would be defined as appendAll = foldl(_,append,[]). Function appendAll takes care of internal lists structure and works more efficient than the foldl based solution. It also works with lists of arrays, arrays of lists and arrays of arrays.

{#
    [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10]].appendAll(),
    [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10]].foldl(append,[])
#}

{# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] #}

A..B, intRange, intRangeBy

The integer range operator n..m computes the list of integers from n to m, including both limits. If n < m, the elements will be in the ascending order, ant if n > m, the elements will be in the descending order:

{#
    0..10,
    -5..5,
    5..-5
#}

{# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5], [5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5] #}

The function intRangeWithLast is a synonym for the operator A..B.

The function intRange(n,m) is similar, but does not include the end of the range m in the list.

The function intRangeBy(n,m,d) creates a list of integers from n to m, but uses a step d instead of 1. As with intRange, its result does not contain the value m.

{#
    5..9,
    intRange(5,9),
    intRangeBy(5,9,2),
    intRangeWithLast(5,9)
#}

{# [5, 6, 7, 8, 9], [5, 6, 7, 8], [5, 7], [5, 6, 7, 8, 9] #}

5.6 Functions map and zip

map

The function map( lst, fun ) is one of the most important higher order functions. It maps the list lst to a new list with the same number of elements. Each element x of the list lst is mapped to the element fun(x) of the new list, in the same order.

This function is equivalent to our function processElements from the previous examples.

In the following example, map is used to compute a list of elements incremented by one:

[1,2,3,4,5,6,7,8,9,10].map( \x: x+1 )

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

The same result:

[1,2,3,4,5,6,7,8,9,10].map( operator+(_,1) )

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

We will use map in many of the following examples.

mapIdx

Sometimes it can be useful to know at which position in the list the processed element is located. We can achieve this by transforming (mapping) a list of values into a list of pairs (index, value) and then mapping this list of pairs where indexes are available. However, it is more efficient to have a function mapIdx(lst,fun) where fun(idx,x) maps the value x at position idx to a new value.

['a','b','c','d','e','f','g','h']
.mapIdx( \i,x: x + i$ )

['a0', 'b1', 'c2', 'd3', 'e4', 'f5', 'g6', 'h7']

zip

The function zip(lst1,lst2) returns a list of tuples, where each tuple contains the corresponding elements of the two given lists lst1 and lst2.

zip( [1,2,3], ['A','B','C'])

[{# 1, 'A' #}, {# 2, 'B' #}, {# 3, 'C' #}]

zipBy

The function zipBy(lst1,lst2,fun) returns a list in which each element is a result of applying fun(x,y) to the corresponding elements of the two given lists lst1 and lst2.

zipBy( ['a','b','c'], ['A','B','C'], operator+ )

['aA', 'bB', 'cC']

zipByIdx

The function zipByIdx(lst1,lst2,fun) returns a list where each element is a result of applying fun(i,x,y) to the corresponding elements of the two given lists lst1 and lst2 and their index (position).

zipByIdx( ['a','b','c'], ['A','B','C'], 
    \i,x,y: i$ + '-' + x + '-' + y 
)

['0-a-A', '1-b-B', '2-c-C']

5.7 Functions foldr, foldl and fold

foldr

Like the map, the function foldr( lst, fun, zero ) is one of the most important higher order functions. It combines the elements of the list lst, using zero as a start value and applying fun(x,res) to combine the element x with the result res of the already completed combination.

This function is equivalent to our combineElements function from the previous examples. So let us use it in a similar example:

[1,2,3,4,5].foldr( operator+, 0 )

15

To better understand what foldr evaluates, consider the following example:

['1','2','3','4','5'].foldr( \x,res: '('+x+','+res+')', '' )

(1,(2,(3,(4,(5,)))))

As we can see, foldr combines elements by combining the head of the list with the already combined list tail. It really starts combining from the end of the list, or from the right side, which is why it has an r at the end of the name.

foldl

If the combining function fun is an associative function (i.e. fun(fun(a,b),c) = fun(a,fun(b,c))), then the order of the combination is not important. But for non-associative functions, as in the previous example, the order is important. For this reason, there is foldl function.

The function foldl combines the list elements from the beginning. It first combines zero and the list head and then the result with the next list element and so on. Look at the following example and compare the result with the previous example where foldr was used with the same arguments:

['1','2','3','4','5'].foldl( \x,res: '('+x+','+res+')', '' )

(((((,1),2),3),4),5)

A Few Examples

If the result of the combining operation has the same type as the list elements, then the combining function has both the arguments and the result of the same type. As we have already emphasized, if the combining function is associative, then foldr and foldl return the same result. Here we can verify this for the addition:

{#
    ['1','2','3','4','5'].foldr( operator+, '' ),
    ['1','2','3','4','5'].foldl( operator+, '' )
#}

{# '12345', '12345' #}

On the other hand, if the function is not associative but has the same argument types, then the result will not be the same:

{#
    lst.foldr( fun, '' ),
    lst.foldl( fun, '' )
#}
where {
    lst = ['1','2','3','4','5'];
    fun(x,y) = '(' + x + ',' + y +')';
}

{# '(1,(2,(3,(4,(5,)))))', '(((((,1),2),3),4),5)' #}

As we can see, foldl combines elements by combining the given initial value with the head of the list, assuming that the result will be passed on to the tail to do the same processing there. So, it really starts combining from the beginning of the list, or from the left side, which is why it has an l at the end of the name.

There are many combination functions that cannot be used with both foldr and foldl. If the result of the combination has a different type than the list elements, then the combining functions have different types of arguments. Such functions cannot be used with both foldr and foldl.

For example, let us write the function append2 that appends two lists (the equivalent of the library function append and the operator ++). We can do this by combining the elements of the first list with the cons-operator, and specifying the second list as zero. Since the cons-operator is not associative (it also has different argument types), we can only use foldr:

[1,2,3].foldr( operator:, [4,5,6])

[1, 2, 3, 4, 5, 6]

We can append many lists together in a similar way:

[[1,2],[3,4],[5,6]].foldr( append, [])

[1, 2, 3, 4, 5, 6]

To use the cons-operator with foldl we need to reverse the arguments. However, the result of the application will be a reversed list:

[1,2,3,4,5,6].foldl( \x,y: y:x, [] )

[6, 5, 4, 3, 2, 1]

The following example shows how to use foldr to compute a list of distinct elements of a sorted list. The combining lambda function assumes that the second argument is the result of the tail processing:

(1..100)
.map( operator%(_,10) )
.sort()
.distinct()
where {
    distinct( lst ) = 
        lst.foldr(
            \x,dist:
                if dist.empty() or x != dist.hd()
                    then x : dist
                    else dist
            , []
        );
}

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

fold

If (1) the combining function fun is an associative function (i.e. fun(fun(a,b),c) = fun(a,fun(b,c))) with arguments of the same type and (2) the given initial value is really a zero (neutral value) for the given combining function fun, then foldl and foldr return the same results.

The function fold is intended for such cases when it is not important in which direction the sequence elements are combined. This function can also be parallelized, which we will discuss later.

5.8 Functions filter, find and filterMap

filter

The function filter(lst,cond) returns the list of lst elements that fulfill the given condition cond(x). The order of the elements is retained.

{#
    [1,2,3,4,5]->filter( operator>(_,1)),   // numbers > 1
    [1,2,3,4,5]->filter( \x : x%2 > 0 ),    // even numbers
    [1,2,3,4,5]->filter( \x : x%2 = 0 )     // odd numbers
#}

{# [2, 3, 4, 5], [1, 3, 5], [2, 4] #}

filterN

The function filterN(lst,cond,n) returns the list of lst elements that fulfill the given condition cond(x), but it selects at most the first n such elements. The order of the elements is retained.

{#
    [1,2,3,4,5]->filterN( operator>(_,1), 2 ), // numbers > 1
    [1,2,3,4,5]->filterN( \x : x%2 > 0, 1 ),   // even numbers
    [1,2,3,4,5]->filterN( \x : x%2 = 0, 1 )    // odd numbers
#}

{# [2, 3], [1], [2] #}

find

The function find(lst,cond) returns the list of zero-based indices of the elements of lst that fulfill the given condition cond(x). The indices are selected in ascending order.

{#
    [1,2,3,4,5]->find( operator>(_,1)),   // numbers > 1
    [1,2,3,4,5]->find( \x : x%2 > 0 ),    // even numbers
    [1,2,3,4,5]->find( \x : x%2 = 0 )     // odd numbers
#}

{# [1, 2, 3, 4], [0, 2, 4], [1, 3] #}

findN

The function findN(lst,cond,n) returns the list of zero-based indices of the elements of lst that fulfill the given condition cond(x), but it selects at most the first n such indices. The indices are selected in ascending order.

{#
    [1,2,3,4,5]->findN( operator>(_,1), 2 ),  // numbers > 1
    [1,2,3,4,5]->findN( \x : x%2 > 0, 1 ),    // even numbers
    [1,2,3,4,5]->findN( \x : x%2 = 0, 1 )     // odd numbers
#}

{# [1, 2], [0], [1] #}

filterMap

The function filter is often used to select some list elements before they are processed by map. Therefore, the filterMap function is included to perform both filtering and processing in one step.

The function filterMap(lst,filtFun,mapFun) is equivalent to the appropriate combination of filter and map. The following example computes a list of squares from odd list elements:

{#
    list.filterMap( odd, square ),
    list.filter(odd).map(square)
#}
where {
    list = 1..20;
    odd( n ) = n % 2 != 0;
    square( n ) = n * n;
}

{# [1, 9, 25, 49, 81, 121, 169, 225, 289, 361], [1, 9, 25, 49, 81, 121, 169, 225, 289, 361] #}

5.9 Functions forall and exists

The function forall(lst,cond) checks whether all list elements fulfill the given condition cond(x). It returns the same result as the combination of the mapping cond and then the folding the result with and:

forall( lst , cond ) 
== 
lst.map(cond).foldl( operator&&, true )

The function exists(lst,cond) checks whether a list element fulfills the given condition cond(x). It is equivalent to mapping the cond and then folding the result with or:

exists( lst , cond ) 
== 
lst.map(cond).foldr( operator||, false )

{#
    [1,2,3,4,5].forall( operator>(_,1) ),
    [1,2,3,4,5].forall( operator>=(_,1) ),
    [1,2,3,4,5].exists( operator<(_,1) ),
    [1,2,3,4,5].exists( operator<=(_,1) )
#}

{# false, true, false, true #}

The functions forall and exists are defined in a lazy way. They process the list elements from the head and can stop processing before the end of the list if the result is already known. The forall function stops after the first negative result and the exists function stops after the first positive result.

5.10 Functions count and countRep

The function count(lst,cond) counts how many list elements fulfill the given condition cond(x).

{#
    [1,2,3,4,5].count( operator>(_,2) ),
    [1,2,3,4,5].count( operator>=(_,2) )
#}

{# 3, 4 #}

The function countRep(lst) counts how often each individual element in the list is repeated. It returns a catalog in which the keys are all unique list elements and the values are the number of occurrences.

Please see Map Type for details.

['a','b','a','a','b','c'].countRep()

[<'a',1>, <'b',1>, <'a',1>, <'a',1>, <'b',1>, <'c',1>]

['a','b','a','a','b','c'].countRep()['b']

1

5.11 Functions sort and sortBy

The function sort(lst) returns a list sorted in ascending order. It works for sequences with elements of primitive types.

The function sortBy(lst,lessThan) returns a list sorted in ascending order using the given comparison function lessThan(x,y). It works for sequences with any element types if a corresponding comparison function is specified.

{#
    [2,1,4,3,5].sort(),
    [2,1,4,3,5].sortBy( operator< ),
    [2,1,4,3,5].sortBy( operator> )
#}

{# [1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1] #}

5.12 Functions in and contains

The function in(x,lst) checks whether the list lst contains x. It is normally used in the form x.in(lst). It works for sequences of any type.

{#
    1 .in([1,2,3]),
    11 .in([1,2,3]),
    {a:5}.in([ {a:4}, {a:5} ]),
    {a:6}.in([ {a:4}, {a:5} ])
#}

{# true, false, true, false #}

The function contains does the same, but with the operands in reverse order: contains(lst,x) is the same as in(x,lst).

{#
    [1,2,3].contains( 1 ),
    [1,2,3].contains( 11 ),
    [ {a:4}, {a:5} ].contains( {a:5} ),
    [ {a:4}, {a:5} ].contains( {a:6} )
#}

{# true, false, true, false #}

5.13 Lazy Lists

Wafl is an eager language, but as in the most languages, there are some lazy elements to avoid unnecessary computation. One such lazy element is retrieving the results of a database query. The query result is a lazy list - only as many rows are retrieved from the database server as are required for the list processing.

However, sometimes we know that we need to process all the rows, but this may take some time and it may make sense to end the communication with the database server as soon as possible. In such cases, we can request the eager evaluation of the query result list with the force function.

The function force(lst) returns the same list, but forces its eager evaluation.