Introduction to Programming in ATS:
<<< PreviousParametric 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 a library of ATS, where they may be implemented in a significantly more efficient manner due to the use of certain programming features 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_cons (x, xs) => list0_cons (x, list0_append (xs, ys))
  | list0_nil () => ys
// 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_cons (x, xs) =>
      list0_reverse_append (xs, list0_cons (x, ys))
  | list0_nil () => ys
// 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 (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 f of the type T1 -<cloref1> T2 for some type T2, list0_map(xs) returns a list ys of the type list0(T2): 

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

The length of ys equals that of xs and each element y in ys equals f(x), where x is the corresponding element in xs. Clearly, this implementation of list0_map is not tail-recursive.

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) = case+ (xs, ys) of
  | (list0_cons (x, xs),
     list0_cons (y, ys)) => list0_cons ((x, y), list0_zip (xs, ys))
  | (_, _) => list0_nil ()
// end of [list0_zip]

The length of zs is the minimum of the lengths of xs and ys and each element z in zs @(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, f) 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
, f: (a, b) -<cloref1> c
) : list0 c = case+ (xs, ys) of
  | (list0_cons (x, xs), list0_cons (y, ys)) =>
      list0_cons (f (x, y), list0_zipwith (xs, ys, f))
  | (_, _) => list0_nil ()
// 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 f(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 f is replaced with lam (x, y) => @(x, y). This function template is also named list0_map2 for the obvious reason.

<<< PreviousHomeNext >>>
Polymorphic DatatypesUpExample: Mergesort on Lists