In functional programming, lists are ubiquitous. We implement as follows some commonly used function templates on lists. It should be noted that these templates are all available in some library of ATS, where they may be implemented in a significantly more efficient manner due to the use of certain programming features (such as linear datatypes) that have not been covered so far.
Please find the entire code in this section plus some additional code for testing on-line.
Given two lists xs and ys of the type list0(T) for some type T, list0_append(xs, ys) returns a list that is the concatenation of xs and ys:
Clearly, this implementation of list0_append is not tail-recursive.Given two lists xs and ys of the type list0(T) for some type T, list0_reverse_append(xs, ys) returns a list that is the concatenation of the reverse of xs and ys:
Clearly, this implementation of list0_reverse_append is tail-recursive.Given a list xs, list0_reverse(xs) returns the reverse of xs:
Given a list xs of the type list0(T1) for some type T1 and a closure function f0 of the type T1 -<cloref1> T2 for some type T2, list0_map(xs, f0) returns a list ys of the type list0(T2):
The length of ys equals that of xs and each element y in ys equals f0(x), where x is the corresponding element in xs. Clearly, this implementation of list0_map is not tail-recursive.Given xs, ini and f0, list0_foldleft(ini, xs, f0) computes the value of the expression f0(... f0(f0(ini, xs[0]), xs[1]) ..., xs[n-1]), where n is the length of xs and xs[i] refers to element i in xs for each i < n. The following implementation of list0_foldleft is tail-recursive:
Given xs, res and f0, list0_foldright(xs, res, f0) computes the value of the expression f0(xs[0], f0(xs[1], f0(... f0(xs[n-1], res) ...))), where n is the length of xs and xs[i] refers to element i in xs for each i < n. The following implementation of list0_foldright is not tail-recursive:
Given two lists xs and ys of the types list0(T1) and list0(T2) for some types T1 and T2, respectively, list0_zip(xs, ys) returns a list zs of the type list0(@(T1, T2)):
fun{ a,b:t@ype } list0_zip ( xs: list0(a) , ys: list0(b) ) : list0@(a, b) = let // typedef ab = @( a, b ) // in // case+ (xs, ys) of | (list0_cons(x, xs), list0_cons(y, ys) ) => ( list0_cons{ab}((x, y), list0_zip<a,b>(xs, ys)) ) (* (cons,cons) *) | (_, _) => list0_nil((*void*)) // end // end of [list0_zip]
Given two lists xs and ys of the types list0(T1) and list0(T2) for some types T1 and T2, respectively, and a closure function f of the type (T1, T2) -<cloref1> T3 for some type T3, list0_zipwith(xs, ys, f0) returns a list zs of the type list0(T3):
fun {a, b:t@ype} {c:t@ype} list0_zipwith ( xs: list0(a) , ys: list0(b) , f0: (a, b) -<cloref1> c ) : list0(c) = ( case+ (xs, ys) of | (list0_cons(x, xs), list0_cons(y, ys)) => ( list0_cons{c}(f0(x, y), list0_zipwith<a,b><c> (xs, ys, f0)) ) | (_, _) => list0_nil((*void*)) ) (* end of [list0_zipwith] *)