CODEWITHSUNDEEP
ats
user7042412
user7042412

Reputation:

How to merge two lists tail-recursively?

For instance, the following function merge can be called to merge two given integer lists:

fun
merge
{m,n:nat}
(
xs: list(int, m)
,
ys: list(int, n)
) : list(int, m+n) =
(
  case+ xs of
  | list_nil() => ys
  | list_cons(x, xs2) =>
    (
      case+ ys of
      | list_nil() => xs
      | list_cons(y, ys2) =>
          if x <= y
            then list_cons(x, merge(xs2, ys))
            else list_cons(y, merge(xs, ys2))
          // end of [if]
    )
)

Clearly, merge is not tail-recursive. If applied to two very long list, merge is likely to overflow the call stack. Is there a way to implement merge tail-recursively?

Upvotes: 1

Views: 143

Answers (1)

Hongwei Xi
Hongwei Xi

Reputation: 935

Note that stream2list_vt is tail-recusive (and very memory-frugal):

fun
merge
{m,n:nat}
(
xs: list(int, m)
,
ys: list(int, n)
) : List0_vt(int) = stream2list_vt(merge2(xs, ys))

and
merge2
{m,n:nat}
(
xs0: list(int, m)
,
ys0: list(int, n)
) : stream_vt(int) = $ldelay
(
  case+ xs0 of
  | list_nil() =>
    !(streamize_list_elt(ys0))
  | list_cons(x0, xs1) =>
    (
      case+ ys0 of
      | list_nil() =>
        !(streamize_list_elt(xs0))
      | list_cons(y0, ys1) =>
        if x0 <= y0
          then stream_vt_cons(x0, merge2(xs1, ys0))
          else stream_vt_cons(y0, merge2(xs0, ys1))
        // end of [if]
    )
)

There are certainly more efficient ways to implement merge tail-recursively than the one given above. However, this example of using linear streams shows a simple and systematic way to build lists tail-recursively.

Upvotes: 1

Related Questions