## 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`.

`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.