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 Ith 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 Li#Xi of Xs, R has a field Xi at feature Li. 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 Zi computed by applying {P Xi Yi}, where Xi is the ith element of Xs and Yi 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.