How to implement list_copy?

Google Group
1

The function list_copy makes a copy of a given list. So its type
can be given as follows:

extern
fun{a:t0p}
list_copy {n:int} (xs: list (a, n)): list (a, n)

which means that the function returns a list of length n when called
on a list of the same length.

How can it be implemented? Before I present my answer, I would like to
see if anyone else wants to give it a try :slight_smile:

Please don’t be afraid of getting it wrong because getting-it-wrong is
ususally
the start of learning something new.

Cheers!

2

that’s right the tail recursive ways involves one more reverse step…
That’s why people concerned with performance could have a look to the more
advanced solution :wink:

3

Here is a one-traversal implementation of list_copy in ATS2:

extern
fun{a:t0p}
list_copy3
{n:int} (xs: list (a, n)): list_vt (a, n)
// end of [list_copy3]

implement{a}
list_copy3 (xs) = let
//
fun loop{n:int}
(
xs: list (a, n), res: &ptr? >> list_vt (a, n)
) : void = let
in
case xs of
| list_cons (x, xs1) =>
{
val () =
res := list_vt_cons{a}{0}(x, )
val+list_vt_cons (, res1) = res
val () = loop (xs1, res1)
prval () = fold@ (res)
}
| list_nil ((void)) => res := list_vt_nil ()
end // end of [list_copy3]
//
var res: ptr
val () = loop (xs, res)
//
in
res
end // end of [list_copy3]

The syntax for this in ATS2 is slightly different from ATS. For comparing
several different implementations
of list_copy, please follow the link below:

4

That is right. However, this approach is a bit too involved. Only good for
experts :slight_smile:

Usually, one implements list_copy as follows:

implement{a}
list_copy (xs) =
(
case+ xs of
| list_cons
(x, xs) => list_cons (x, list_copy (xs))
| list_nil () => list_nil ()
)

This is a non-tail-recursive version. If one only uses it to copy short
lists, then it is fine.
When handling a long list (say, containing 1 million elements), this
function is likely to
overflow the call stack.

Suppose list_rcopy copies a list in the reverse order; that is, the return
result is the reverse
of the given list. Often, list_rcopy is called list-reverse function, which
can be readily implemented
tail-recursively:

implement{a}
list_rcopy (xs) = let
//
fun loop{n1,n2:int}
(
xs: list (a, n1), res: list (a, n2)
) : list (a, n1+n2) =
case xs of
| list_cons
(x, xs) => loop (xs, list_cons (x, res))
| list_nil () => res
//
in
loop (xs, list_nil)
end // end of [list_rcopy]

Now, we can implement list_copy as follows

implement{a}
list_copy (xs) = list_rcopy (list_rcopy (xs))

This is a tail-recursive implementation of list_copy. However, one may
dislike it because it does two list-traversals.
Actually, the list-merge function (for implementing merge-sort) in ocaml’s
library is done this way so as to make sure
that list-merge is defined tail-recursively.

5

hello,
sorry I don’t have much time to work on this but I suppose it would be
similar to that single pass list filter illustrated here :

http://bluishcoder.co.nz/2011/12/16/pattern-matching-against-linear-objects-in-ats.html#single_pass_tail_recursive_filtering

:wink: