How to implement list_last?

Google Group
1

list_last returns the last element in a given list. How should be properly
implemented in ATS?

2

I have put my code plus some testing code in the following file:

3

If you want to implement list_last on lists of unknown sizes, there
are too common approaches.

  1. Using exception

extern
fun{a:t0p} list_last_exn (xs: List (a)): a

implement{a}
list_last_exn
(xs) = let
in
//
case+ xs of
| list_cons _ => list_last (xs)
| list_nil () => $raise ListSubscriptExn()
//
end // end of [list_last_exn]

  1. Using Optional value

extern
fun{a:t0p}
list_last_opt (xs: List (a)): Option_vt(a)

implement{a}
list_last_opt
(xs) = let
in
//
case+ xs of
| list_cons _ =>
Some_vt{a}(list_last (xs))
| list_nil () => None_vt{a}((void))
//
end // end of [list_last_opt]

The problem with using optional values is that such values need to be
stored in heap; that is, dynamic memory allocation is involved.
The following style of implementation avoids this problem:

extern
fun{a:t0p}
list_last_opt2
(xs: List (a), res: &a? >> opt(a, b)): #[b:bool] bool(b)
// end of [list_last_opt2]

implement{a}
list_last_opt2
(xs, res) = let
in
//
case+ xs of
| list_cons _ => let
val () = res := list_last (xs)
prval () = opt_some{a}(res) in true(found)
end // end of [list_cons]
| list_nil () => let
prval () = opt_none{a}(res) in false(notfound)
end // end of [list_nil]
//
end // end of [list_last_opt2]

I often use list_last_opt2 to implement list_last_opt.

4

First and foremost, list_last is only well-defined on non-empty lists.
Here is a type for it:

extern
fun{a:t0p} list_last {n:int | n > 0} (xs: list (a, n)): a

Here is an efficient implementation:

implement{a}
list_last (xs) = let
//
val+list_cons (x, xs1) = xs // no tag-checking
//
in
//
case+ xs1 of
| list_cons _ => list_last (xs1) | _ => x
//
end // end of [list_last]

Note that val+ means the pattern matching following it must succeed. If the
compiler
cannot verify the claim, a type-error message is issued. For instance, if
you remove
’n > 0’ in the type for list_last and typecheck the above code, you can see
an error
message being issued. If the compiler can verify the claim, then it will
generate no
tag-checking code to test whether xs is non-empty: it must be!

5

very valuable hints.

thanks !