6.3 Lists (original) (raw)

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 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 _i_th element of _Xs_ and Yi the _i_th 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.