Introduction to Programming in ATS:
PrevChapter 5. Parametric PolymorphismNext

Example: Function Templates on Lists

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.

Appending: list0_append

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: 

fun
{a:t@ype}
list0_append
(
xs: list0 a, ys: list0 a
) : list0 a =
(
case+ xs of
| list0_nil() => ys
| list0_cons(x, xs) =>
    list0_cons{a}(x, list0_append<a>(xs, ys))
  // end of [list0_cons]
) (* end of [list0_append] *)

Clearly, this implementation of list0_append is not tail-recursive.

Reverse-Appending: list0_reverse_append

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: 

fun
{a:t@ype}
list0_reverse_append
(
xs: list0 a, ys: list0 a
) : list0 a =
(
case+ xs of
| list0_nil() => ys
| list0_cons(x, xs) =>
    list0_reverse_append<a> (xs, list0_cons{a}(x, ys))
  // end of [list0_cons]
) (* end of [list0_reverse_append] *)

Clearly, this implementation of list0_reverse_append is tail-recursive.

Reversing: list0_reverse

Given a list xs, list0_reverse(xs) returns the reverse of xs: 

fun
{a:t@ype}
list0_reverse
  (xs: list0 a): list0 a = list0_reverse_append<a>(xs, list0_nil)
// end of [list0_reverse]

Mapping: list0_map

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): 

fun
{a:t@ype}
{b:t@ype}
list0_map
(
  xs: list0 a, f0: a -<cloref1> b
) : list0 b =
(
case+ xs of
| list0_nil() =>
  list0_nil()
| list0_cons(x, xs) =>
  list0_cons{b}(f0(x), list0_map<a><b>(xs, f0))
) (* end of [list0_map] *)

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.

Left-Folding: list0_foldleft

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: 

fun
{a:t@ype}
{b:t@ype}
list0_foldleft
(
  ini: a
, xs0: list0(b), f0: (a, b) -<cloref> a
) : a =
(
//
case+ xs0 of
| list0_nil() => ini
| list0_cons(x, xs) =>
  list0_foldleft<a><b> (f0(ini, x), xs, f0)
//
) (* end of [list0_foldleft] *)

Right-Folding: list0_foldright

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: 

fun
{a:t@ype}
{b:t@ype}
list0_foldright
(
  xs0: list0(a)
, res: b, f0: (a, b) -<cloref1> b
) : b =
(
//
case+ xs0 of
| list0_nil() => res
| list0_cons(x, xs) =>
  f0(x, list0_foldright<a><b>(xs, res, f0))
//
)

Zipping: list0_zip

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]

The length of zs is the minimum of the lengths of xs and ys and each element z in zs equals @(x, y), where x and y are the corresponding elements in xs and ys, respectively. Clearly, this implementation of list0_zip is not tail-recursive.

Zipping with: list0_zipwith

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] *)

The length of zs is the minimum of the lengths of xs and ys and each element z in zs is f0(x, y), where x and y are the corresponding elements in xs and ys, respectively. Clearly, this implementation of list0_zipwith is not tail-recursive. Note that list0_zipwith behaves exactly like list0_zip if its third argument f0 is replaced with lam (x, y) => @(x, y). This function template is also given the name list0_map2 for the obvious reason.

PrevHomeNext
Polymorphic DatatypesUpExample: Mergesort on Lists