A Crash into FP through ATS:
PrevNext

Chapter 11. Functional List-Processing (3)

In this chapter, I intend to present a few more list-processing functions. More importantly, I would like to argue for the practice of actively identifying the need for generic list-processing functions during problem-solving.

There are many useful list-processing functions for handling two lists simultaneously. For instance, the following function list0_zip takes a pair of lists and returns a list of pairs: 

//
extern
fun {
a,b:t@ype
} list0_zip
  (xs: list0(a), ys: list0(b)): list0($tup(a, b))
//
implement
{a,b}
list0_zip(xs, ys) =
(
case xs of
| list0_nil() =>
  list0_nil()
| list0_cons(x, xs) =>
  (
    case+ ys of
    | list0_nil() =>
      list0_nil()
    | list0_cons(y, ys) =>
      list0_cons($tup(x, y), list0_zip<a,b>(xs, ys))
  )
)
//

For instance, given two lists (1, 3, 5) and (2, 4), list0_zip returns the list consisting of $tup(1, 2) and $tup(3,4). Note that $tup is a keyword in ATS (for constructing tuples). For a list-processing function handling one list, there is often a meaningful variant that essentially acts like passing to the list-processing function a list of pairs obtained from applying list0_zip to two given lists. For instance, the following function list0_map2 is such a variant of list0_map: 

//
extern
fun
{a
,b:t@ype}
{c:t@ype}
list0_map2
(xs: list0(a), ys: list0(b), fopr: cfun(a, b, c)): list0(c)
//
implement
{a,b}{c}
list0_map2
(xs, ys, fopr) =
(
case xs of
| list0_nil() =>
  list0_nil()
| list0_cons(x, xs) =>
  (
    case+ ys of
    | list0_nil() =>
      list0_nil()
    | list0_cons(y, ys) =>
      list0_cons(fopr(x, y), list0_map2<a,b><c>(xs, ys, fopr))
  ) (* end of [list0_cons] *)
)
//

For instance, given two lists (1, 3, 5) and (2, 4, 6) and the multiplication function, list0_map2 returns the list (2, 12, 30). Sometimes, list0_map2 is referred to as list0_zipwith.

There are various list-processing functions operating on ordered lists. For instance, the following function list0_merge is for merging two ordered lists into one: 

//
extern
fun
{a:t@ype}
list0_merge
( xs: list0(a)
, ys: list0(a), cmp: cfun(a, a, int)): list0(a)
//
implement
{a}(*tmp*)
list0_merge
(xs0, ys0, cmp) = let
//
fun
auxlst
( xs0: list0(a)
, ys0: list0(a)
) : list0(a) = (
//
case+ xs0 of
| list0_nil() => ys0
| list0_cons
    (x1, xs1) => (
    case+ ys0 of
    | list0_nil() => xs0
    | list0_cons
        (y1, ys1) => let
        val sgn = cmp(x1, y1)
      in
        if (sgn <= 0)
          then list0_cons(x1, auxlst(xs1, ys0))
          else list0_cons(y1, auxlst(xs0, ys1))
        // end of [if]
      end // end of [list0_cons]
  ) (* end of [list0_cons] *)
//
) (* end of [auxlst] *)
//
in
  auxlst(xs0, ys0)
end // end of [list0_merge]
//

With list0_merge, we can readily implement as follows the well-known mergesort algorithm to sort a given list0-value: 

//
extern
fun
{a:t@ype}
list0_mergesort
(xs: list0(a), cmp: cfun(a, a, int)): list0(a)
//
implement
{a}(*tmp*)
list0_mergesort
  (xs, cmp) = let
//
// [msort]:
// It is assumed
// that length(xs) = n
//
fun
msort
(xs: list0(a), n: int): list0(a) =
if
(n >= 2)
then let
  val n1 = n / 2
  val xs1 = list0_take_exn(xs, n1)
  val xs2 = list0_drop_exn(xs, n1)
in
  list0_merge<a>(msort(xs1, n1), msort(xs2, n-n1), cmp)
end // end of [then]
else (xs) // end of [else]
//
in
  msort(xs, list0_length<a>(xs))
end // end of [list0_mergesort]
//

Note that list0_take_exn(xs, n) returns the prefix of xs that is of length n and list0_drop_exn(xs, n) returns the suffix of xs that excludes the first n elements of xs. It is guaranteed that list0_mergesort is log-linear (that is, it is of O(n(log(n)))-time for n being the length of its argument). Also, list0_mergesort is stable in the sense that the order of the elements considered equal in the input is not changed in the output. Clearly, list0_merge is not tail-recursive, potentially running the risk of stack overflow when list0_mergesort is applied to a long list (e.g., one containing 1 million elements). This is a very serious issue with non-tail-recursion in practice, and some approaches to addressing it are to be presented later.

During problem-solving, it often pays if one actively looks for opptunities to generalize a specific function into one that can be given a meaningful description in a broader context. As an example, if one encounters a need to process all of the pairs formed with elements chosen from a given list, then one may want to implement the following function list0_choose2: 

//
extern
fun
{a:t@ype}
list0_choose2
(xs: list0(a)): list0($tup(a, a))
//
extern
fun
{a:t@ype}
list0_choose2
(xs: list0(a)): list0($tup(a, a))
//
implement
{a}(*tmp*)
list0_choose2
  (xs) = let
//
typedef aa = $tup(a, a)
//
in
//
case+ xs of
| list0_nil() =>
  list0_nil()
| list0_cons(x0, xs) =>
  list0_append<aa>
  (list0_map<a><aa>(xs, lam(x) => $tup(x0, x)), list0_choose2(xs))
//
end // end of [list0_choose2]
//

For instance, given the list (1, 2, 3), list0_choose2 returns the list of 3 pairs: (1, 2), (1, 3), and (2, 3). And list0_choose2 can be further generalized into the following function list0_nchoose for listing all of the tuples of a given length that are formed with elements chosen from a given list: 

//
extern
fun
{a:t@ype}
list0_nchoose
(xs: list0(a), n: int): list0(list0(a))
//
implement
{a}(*tmp*)
list0_nchoose
  (xs, n) =
  auxlst(xs, n) where
{
//
typedef xs = list0(a)
//
fun
auxlst
(
xs: xs, n: int
) : list0(xs) =
(
if
(n <= 0)
then
list0_sing(list0_nil())
else
(
case+ xs of
| list0_nil() =>
  list0_nil()
| list0_cons(x0, xs) =>
  list0_append<xs>(list0_mapcons(x0, auxlst(xs, n-1)), auxlst(xs, n))
) (* end of [else] *)
)
//
} (* end of [list0_nchoose] *)
//

Sometimes, we may need to process tuples consisting of elements chosen from a given list as well as the complements of these tuples. The following function list0_nchoose_rest generalizes list0_nchoose in this regard: 

//
extern
fun
{a:t@ype}
list0_nchoose_rest
(xs: list0(a), n: int): list0($tup(list0(a), list0(a)))
//
implement
{a}(*tmp*)
list0_nchoose_rest
  (xs, n) =
  auxlst(xs, n) where
{
//
typedef xs = list0(a)
typedef xsxs = $tup(xs, xs)
//
fun
auxlst
(
xs: xs, n: int
) : list0(xsxs) =
(
if
(n <= 0)
then
list0_cons
($tup(list0_nil(), xs), list0_nil())
else
(
case+ xs of
| list0_nil() =>
  list0_nil()
| list0_cons(x0, xs) => let
    val res1 =
    list0_map<xsxs><xsxs>
    ( auxlst(xs, n-1)
    , lam($tup(xs1, xs2)) => $tup(list0_cons(x0, xs1), xs2)
    )
    val res2 =
    list0_map<xsxs><xsxs>
    ( auxlst(xs, n-0)
    , lam($tup(xs1, xs2)) => $tup(xs1, list0_cons(x0, xs2))
    )
  in
    list0_append<xsxs>(res1, res2)
  end // end of [list0_cons]
) (* end of [else] *)
)
//
} (* end of [list0_nchoose_rest] *)

For instance, given the list (1, 2, 3) and integer 2, list0_choose_rest returns the list of 3 pairs: $tup((1, 2), (3)), $tup((1, 3), (2)), and $tup((2, 3), (1)).

The problem of enumerating all of the permutations of a given list is often used to test one's ability in constructing recursively defined functions. Let us see a solution to this problem given as follows: 

//
fun
{a:t@ype}
list0_permute
(
xs: list0(a)
) : list0(list0(a)) =
(
case+ xs of
| list0_nil() =>
  list0_cons(nil0(), nil0())
| list0_cons _ => let
    typedef xs = list0(a)
    typedef out = list0(xs)
    typedef inp = $tup(xs, xs)
  in
    list0_concat<xs>
    (
     list0_map<inp><out>
     ( list0_nchoose_rest<a>(xs, 1)
     , lam($tup(ys, zs)) => list0_mapcons<a>(ys[0], list0_permute<a>(zs))
     )
    ) (* list0_concat *)
  end (* end of [list0_cons] *)
)
//

For instance, given the list (1, 2, 3), list0_permute returns a list of length 6 in which each element is a permutation of (1, 2, 3). Note that ys[0] refers to the first element in ys and list0_mapcons prepends its first argument to each element in its second argument (which is a list of lists). A demo of list0_permute can be seen by following this link.

Please find on-line the entirety of the code used in this chapter. The mentioned URL link(s) can be found as follows:

PrevHomeNext
Through ATS to Javascript Example: Game of Twenty-four