## 6.3 Lists

The module `List` contains procedures operating on lists.

`IsList`

`{List.is ``+X`` ``?B``}`

tests whether `X` is a list. Diverges if `X` is an infinite list.

`MakeList`

`{List.make ``+I`` ``?Xs``}`

returns a list of length `I`. All elements are fresh variables.

`Append`

`{List.append ``+Xs`` ``Y`` ``?Zs``}`

binds `Zs` to the result of appending `Y` to `Xs`. `Y` needs not be a list. However, `Zs` is only a proper list, if also `Y` is a proper list.

For example,

`{Append [1 2] [3 4]}`

returns the list `[1 2 3 4]`, whereas

`{Append 1|2|nil 3|4}`

returns `1|2|(3|4)` which is not a proper list, since `3|4` is not a proper list.

`Member`

`{List.member ``X`` ``+Ys`` ``?B``}`

tests whether `X` is equal (in the sense of `==`) to some element of `Ys`. Note: all other procedures of the `List` module that operate on a list take it as their first argument. `Member` is the only exception (for historical reasons).

`Length`

`{List.length ``+Xs`` ``?I``}`

returns the length of `Xs`.

`Nth`

`{List.nth ``+Xs`` ``+I`` ``?Y``}`

returns the `I`th element of `Xs` (counting from `1`).

`subtract`

`{List.subtract ``+Xs`` ``Y`` ``?Zs``}`

binds `Zs` to `Xs` without the leftmost occurrence of `Y` if there is one.

`sub`

`{List.sub ``+Xs`` ``+Ys`` ``?B``}`

tests whether `Xs` is a sublist of `Ys`, i. e., whether it contains all elements of `Xs` in the same order as `Xs` but not necessarily in succession.

For example, `[a b]` is a sublist of both `[1 a b 2]` and `[1 a 2 b 3]`, but not of `[b a]`.

`Reverse`

`{List.reverse ``+Xs`` ``?Ys``}`

returns the elements of `Xs` in reverse order.

`Sort`

`{List.sort ``+Xs`` ``+P`` ``?Ys``}`

binds `Ys` to the result of sorting `Xs` using the ordering `P`. `Sort` is implemented using the mergesort algorithm.

For example,

`{Sort [c d b d a] Value.'<'}`

returns the list `[a b c d d]`.

`Merge`

`{List.merge ``+Xs`` ``+Ys`` ``+P`` ``?Zs``}`

binds `Zs` to the result of merging `Xs` and `Ys` using the ordering `P`. The lists `Xs` and `Ys` must be sorted.

`Flatten`

`{List.flatten ``+Xs`` ``?Ys``}`

binds `Ys` to the result of flattening `Xs`, i. e., of concatenating all sublists of `Xs` recursively.

`withTail`

`{List.withTail ``+I`` ``Y`` ``?Xs``}`

returns a list with at least `I` elements whose rest is `Y` (which needs not be a list). The first `I` elements are fresh variables.

For example, `{List.withTail 2 [a b]}` returns `[_ _ a b]`.

`number`

`{List.number ``+FromI`` ``+ToI`` ``+StepI`` ``?Xs``}`

returns a list with elements from `FromI` to `ToI` with step `StepI`.

For example, `{List.number 1 5 2}` returns `[1 3 5]`, `{List.number 5 1 2}` yields the list `nil`, and `{List.number 5 0 -2}` yields the list `[5 3 1]`.

`take`

`{List.take ``+Xs`` ``+I`` ``?Ys``}`

returns the list that contains the first `I` elements of `Xs`, or `Xs` if it is shorter.

`drop`

`{List.drop ``+Xs`` ``+I`` ``?Ys``}`

returns the list `Xs` with the first `I` elements removed, or to `nil` if it is shorter.

`takeDrop`

`{List.takeDrop ``+Xs`` ``+I`` ``?Ys`` ``?Zs``}`

binds `Ys` to `{List.take ``Xs`` ``I``}` and `Zs` to `{List.drop ``Xs`` ``I``}`.

`last`

`{List.last ``+Xs`` ``?Y``}`

returns the last element of `Xs`. Raises an error exception if `Xs` is `nil`.

`toTuple`

`{List.toTuple ``+L`` ``+Xs`` ``?T``}`

binds `T` to a tuple with label `L` that contains the elements of `Xs` as subtrees in the given order.

For example,

`{List.toTuple '#' [a b c]}`

returns `a#b#c`.

`toRecord`

`{List.toRecord ``+L`` ``+Ts`` ``?R``}`

binds `R` to a record with label `L` whose subtrees are given by the property list `Ts`: For every element `L`i`#X`i of `Xs`, `R` has a field `X`i at feature `L`i. The features in the property list must be pairwise distinct, else an error exception is raised.

For example,

`{List.toRecord f [a#1 b#2 c#3]}`

returns `f(a: 1 b: 2 c: 3)`.

`zip`

`{List.zip ``+Xs`` ``+Ys`` ``+P`` ``?Zs``}`

returns the list of all elements `Z`i computed by applying `{``P`` X`i` Y`i`}`, where `X`i is the ith element of `Xs` and `Y`i the ith element of `Ys`. The two input lists must be of equal length, else an error exception is raised.

For example,

`{List.zip [1 6 3] [4 5 6] Max}`

returns the list `[4 6 6]`.

`isPrefix`

`{List.isPrefix ``+Xs`` ``+Ys`` ``?B``}`

tests whether `Xs` is a prefix of `Ys`. Given that `Xs` has length i, it is a prefix of `Ys` if `Ys` has at least length i and the first i elements of `Ys` are equal to the corresponding elements of `Xs`.

All of the following procedures exist in two versions. The so-called index version passes to the procedures an additional index as first actual argument. The index is an integer giving the position of the list element currently processed (counting from `1`).

`Map`

`{List.map ``+Xs`` ``+P`` ``?Ys``}`

returns the list obtained by applying `P` to each element of `Xs`.

For example,

`{Map [12 13 1] IntToFloat}`

returns `[12.0 13.0 1.0]`.

`mapInd`

`{List.mapInd ``+Xs`` ``+P`` ``?Ys``}`

is similar to `Map`, but the ternary procedure `P` is applied with the index as first actual argument.

For example,

`{List.mapInd [d a e] fun {\$ I A} I#A end}`

yields the list `[1#d 2#a 3#e]` as output.

`FoldL`

`{List.foldL ``+Xs`` ``+P`` ``X`` ``?Y``}`

`FoldR`

`{List.foldR ``+Xs`` ``+P`` ``X`` ``?Y``}`

Used for folding the elements of `Xs` by applying a ternary procedure `P`.

Application of the left folding procedure `{FoldL [``X1`` `...` ``Xn``] ``P`` ``Z`` ``Out``}` reduces to

`{``P`` `...` {``P`` {``P`` ``Z`` ``X1``} ``X2``} `...` ``Xn`` ``Out``}`

The first actual argument of `P` is the accumulator in which the result of the previous application or the start value `Z` is passed. The second actual argument is an element of `Xs`.

Besides the left folding procedure there exists a right folding variant. The application `{FoldR [``X1`` `...` ``Xn``] ``P`` ``Z`` ``Out``}` reduces to

`{``P`` ``X1`` {``P`` ``X2`` `...` {``P`` ``Xn`` ``Z``} `...`} ``Out``}`

The first actual argument of `P` is an element of `Xs`. The second actual argument of `P` is the accumulator in which the result of the previous application or the start value `Z` is passed.

For example,

`{FoldL [b c d] fun {\$ X Y} f(X Y) end a}`

returns `f(f(f(a b) c) d)`, whereas

`{FoldR [b c d] fun {\$ X Y} f(X Y) end a}`

returns `f(b f(c f(d a)))`.

`foldLInd`

`{List.foldLInd ``+Xs`` ``+P`` ``X`` ``?Y``}`

`foldRInd`

`{List.foldRInd ``+Xs`` ``+P`` ``X`` ``?Y``}`

are similar to `FoldL` and `FoldR`, but the `4`-ary procedure `P` is applied with the current index as first actual argument.

`FoldLTail`

`{List.foldLTail ``+Xs`` ``+P`` ``X`` ``?Y``}`

`FoldRTail`

`{List.foldRTail ``+Xs`` ``+P`` ``X`` ``?Y``}`

Used for folding all non-`nil` tails of `Xs` by applying a ternary procedure `P`, i. e., application of the left folding procedure

`{FoldLTail [``X1`` `...` ``Xn``] ``P`` ``Z`` ``Out``}`

reduces to

`{``P`` `...` {``P`` {``P`` ``Z`` [``X1`` `...` ``Xn``]} [``X2`` `...` ``Xn``]} `...` ``Xn``] ``Out``}`

The right folding procedure is analogous.

`foldLTailInd`

`{List.foldLTailInd ``+Xs`` ``+P`` ``X`` ``?Y``}`

`foldRTailInd`

`{List.foldRTailInd ``+Xs`` ``+P`` ``X`` ``?Y``}`

are similar to `FoldLTail` and `FoldRTail`, but the `4`-ary procedure `P` is applied with the current index as first actual argument.

`ForAll`

`{List.forAll ``+Xs`` ``+PO``}`

applies the unary procedure or object `PO` to each element of `Xs`, i. e., the application

`{ForAll [``X1`` `...` ``Xn``] ``P``}`

reduces to the sequence of statements

`{``P`` ``X1``} `...` {``P`` ``Xn``}`

For example,

`{ForAll [O1 O2 O3] proc {\$ O} {O do()} end}`

sends the message `do()` to the objects `O1`, `O2`, and `O3`.

`forAllInd`

`{List.forAllInd ``+Xs`` ``+P``}`

is similar to `ForAll`, but the binary procedure `P` is applied with the current index as first actual argument.

For example, assuming `O1`, `O2`, and `O3` are objects, the following statement sends the message `do(1)` to the object `O1`, the message `do(2)` to `O2`, and the message `do(3)` to `O3`:

`{List.forAllInd [O1 O2 O3] proc {\$ I O} {O do(I)} end}`

`ForAllTail`

`{List.forAllTail ``+Xs`` ``+PO``}`

applies the unary procedure or object `PO` to each non-`nil` tail of `Xs`, i. e., the application

`{ForAllTail [``X1`` `...` ``Xn``] ``P``}`

reduces to the sequence of statements

`{``P`` [``X1`` `...` ``Xn``]} {``P`` [``X2`` `...` ``Xn``]} `...` {``P`` [``Xn``]}`

`forAllTailInd`

`{List.forAllTailInd ``+Xs`` ``+P``}`

is similar to `ForAllTail`, but the binary procedure `P` is applied with the current index as first actual argument.

`All`

`{List.all ``+Xs`` ``+P`` ``?B``}`

`Some`

`{List.some ``+Xs`` ``+P`` ``?B``}`

tests whether the unary boolean function `P` yields `true` when applied to all elements resp. some element of `Xs`. Stops at the first element for which `P` yields `false` resp. `true`.

`allInd`

`{List.allInd ``+Xs`` ``+P`` ``?B``}`

`someInd`

`{List.someInd ``+Xs`` ``+P`` ``?B``}`

are similar to `All` and `Some`, but the binary boolean function `P` is applied with the current index as first actual argument.

`Filter`

`{List.filter ``+Xs`` ``+P`` ``?Ys``}`

`partition`

`{List.partition ``+Xs`` ``+P`` ``?Ys`` ``?Zs``}`

`Filter` returns a list of the elements of `Xs` for which the application of the unary boolean function `P` yields `true`, where the ordering is preserved. `List.partition` works similarly, but additionally returns in `Zs` a list of all remaining elements of `Xs`, where the ordering is preserved as well.

For example, the application

`{List.partition [1 4 2 3 6 5] IsOdd Ys Zs}`

returns `[1 3 5]` in `Ys` and `[4 2 6]` in `Zs`.

`filterInd`

`{List.filterInd ``+Xs`` ``+P`` ``?Ys``}`

`partitionInd`

`{List.partitionInd ``+Xs`` ``+P`` ``?Ys`` ``?Zs``}`

are similar to `Filter` and `List.partition`, but the binary boolean function `P` is applied with the current index as first actual argument.

`takeWhile`

`{List.takeWhile ``+Xs`` ``+P`` ``?Ys``}`

`dropWhile`

`{List.dropWhile ``+Xs`` ``+P`` ``?Ys``}`

`takeDropWhile`

`{List.takeDropWhile ``+Xs`` ``+P`` ``?Ys`` ``?Zs``}`

While `Filter` selects all elements of a list which satisfy a certain condition, the procedure `List.takeWhile` selects only the starting sequence of elements which fulfill this condition. The procedure `List.dropWhile` is dual: It returns the remainder of the list. For convenience, `List.takeDropWhile` combines the functionality from both `List.takeWhile` and `List.dropWhile`.

For example, the application

`{List.takeWhile [1 4 2 3 6 5] IsOdd Ys}`

returns `[1]` in `Ys`, whereas

`{List.dropWhile [1 4 2 3 6 5] IsOdd Zs}`

returns `[4 2 3 6 5]` in `Ys`.

`{List.takeDropWhile [1 4 2 3 6 5] IsOdd Ys Zs}`

combines both.

`takeWhileInd`

`{List.takeWhileInd ``+Xs`` ``+P`` ``?Ys``}`

`dropWhileInd`

`{List.dropWhileInd ``+Xs`` ``+P`` ``?Ys``}`

`takeDropWhileInd`

`{List.takeDropWhileInd ``+Xs`` ``+P`` ``?Ys`` ``?Zs``}`

are similar to `List.takeWhile`, `List.dropWhile` and `List.takeDropWhile` but the binary boolean function `P` is applied with the current index as first actual argument.

Denys Duchier, Leif Kornstaedt and Christian Schulte
Version 1.4.0 (20080702)