This package contains a variety of common functions for creating/freeing and manipulating linear lists.
The type for a singly-linked linear list containing N elements of type T is denoted by list_vt(T, N), where T can be linear. The suffix "vt" in the name list_vt stands for viewtype, which is the formal name for linear type in ATS. Note that the type constructor list_vt is co-variant in its first argument, that is, list_vt(T1, N) is a subtype of list_vt(T2, N) if T1 is a subtype of T2. The low-level representation for list_vt is the same as that for a standard singly-linked list in C, and it is fairly straightforward to implement functions in C that can directly manipulate linear lists in ATS and vice versa.
Please see list_vt.sats and list_vt.dats (plus list_vt_mergesort.dats, list_vt_quicksort.dats) for the SATS file and DATS files in ATSLIB where the functions in this package are declared and implemented.
The full name for the list-type constructor list_vt is list_viewt0ype_int_viewtype, which is given to the linear datatype (dataviewtype) declared as follows:
dataviewtype // viewt@ype+: covariant list_viewt0ype_int_viewtype (a:viewt@ype+, int) = | list_vt_nil (a, 0) of () | {n:int | n >= 0} list_vt_cons (a, n+1) of (a, list_viewt0ype_int_viewtype (a, n)) // end of [list_viewt0ype_int_viewtype]
vtypedef List_vt(a:vt0p) = [n:int] list_vt(a, n)
vtypedef List0_vt(a:vt0p) = [n:int | n >= 0] list_vt(a, n)
vtypedef List1_vt(a:vt0p) = [n:int | n >= 1] list_vt(a, n)
vtypedef listLt_vt (a:vt0p, n:int) = [k:nat | k < n] list_vt(a, k)
vtypedef listLte_vt (a:vt0p, n:int) = [k:nat | k <= n] list_vt(a, k)
vtypedef listGt_vt (a:vt0p, n:int) = [k:int | k > n] list_vt(a, k)
vtypedef listGte_vt (a:vt0p, n:int) = [k:int | k >= n] list_vt(a, k)
vtypedef listBtw_vt (a:vt0p, m:int, n:int) = [k:int | m <= k; k < n] list_vt(a, k)
vtypedef listBtwe_vt (a:vt0p, m:int, n:int) = [k:int | m <= k; k <= n] list_vt(a, k)
prfun
lemma_list_vt_param
{x:vt0p}{n:int}
(xs: !list_vt(INV(x), n)): [n >= 0] void
castfn
list_vt_cast
{x:vt0p}{n:int}
(xs: list_vt(INV(x), n)):<> list_vt(x, n)
fun{x:vt0p}
list_vt_make_sing (x: x):<!wrt> list_vt(x, 1)
fun{x:vt0p}
list_vt_make_pair (x1: x, x2: x):<!wrt> list_vt(x, 2)
fun{x:vt0p}
fprint_list_vt
(out: FILEref, xs: !List_vt(INV(x))): void
fun{} fprint_list_vt$sep (out: FILEref): void
fun{x:vt0p}
list_vt_is_nil
{n:int} (xs: !list_vt(INV(x), n)):<> bool (n==0)
fun{x:vt0p}
list_vt_is_cons
{n:int} (xs: !list_vt(INV(x), n)):<> bool (n > 0)
fun{x:vt0p}
list_vt_is_sing
{n:int} (xs: !list_vt(INV(x), n)):<> bool (n==1)
fun{x:vt0p}
list_vt_is_pair
{n:int} (xs: !list_vt(INV(x), n)):<> bool (n==2)
fun{}
list_vt_unnil{x:vt0p} (xs: list_vt(x, 0)):<> void
fun{x:vt0p}
list_vt_uncons{n:pos}
(xs: &list_vt(INV(x), n) >> list_vt(x, n-1)):<!wrt> x
fun{x:vt0p} fprint_list_vt_sep ( out: FILEref, xs: !List_vt(INV(x)), sep: NSH(string) ) : void // end of [fprint_list_vt_sep]
fun{x:vt0p}
list_vt_length{n:int} (xs: !list_vt(INV(x), n)):<> int n
fun{x:vt0p}
list_vt_getref_at
{n:int}{i:nat | i <= n}
(xs: &list_vt(INV(x), n), i: int i):<> cPtr1 (list_vt(x, n-i))
fun{x:t0p}
list_vt_get_at{n:int}
(xs: !list_vt(INV(x), n), i: natLt n):<> x
fun{x:t0p}
list_vt_set_at{n:int}
(xs: !list_vt(INV(x), n), i: natLt n, x: x):<!wrt> void
fun{x:vt0p}
list_vt_exch_at{n:int}
(xs: !list_vt(INV(x), n), i: natLt n, x: &x >> _):<!wrt> void
fun{x:vt0p} list_vt_insert_at{n:int} ( xs: &list_vt(INV(x), n) >> list_vt(x, n+1), i: natLte n, x: x ) :<!wrt> void // end of [list_vt_insert_at]
fun{x:vt0p}
list_vt_takeout_at{n:int}
(xs: &list_vt(INV(x), n) >> list_vt(x, n-1), i: natLt n):<!wrt> x
fun{x:t0p}
list_vt_copy{n:int}
(xs: !list_vt(INV(x), n)):<!wrt> list_vt(x, n)
fun{x:vt0p}
list_vt_copylin{n:int}
(xs: !list_vt(INV(x), n)):<!wrt> list_vt(x, n)
fun{x:t0p}
list_vt_free(xs: List_vt(INV(x))):<!wrt> void
fun{x:vt0p}
list_vt_freelin
(xs: List_vt(INV(x))):<!wrt> void
fun{x:vt0p}
list_vt_freelin$clear (x: &x >> x?):<!wrt> void
fun{ x:vt0p } list_vt_uninitize {n:int} ( xs: !list_vt(INV(x), n) >> list_vt(x?, n) ) :<!wrt> void // end of [list_vt_uninitize]
fun{ x:vt0p } list_vt_uninitize_fun {n:int}{fe:eff} ( xs: !list_vt(INV(x), n) >> list_vt(x?, n), f: (&x>>x?) -<fe> void ) :<!wrt,fe> void // end of [list_vt_uninitize_fun]
fun{x:vt0p}
list_vt_uninitize$clear (x: &(x) >> x?):<!wrt> void
fun{ a:vt0p } list_vt_append {n1,n2:int} ( xs1: list_vt(INV(a), n1), xs2: list_vt(a, n2) ) :<!wrt> list_vt(a, n1+n2) // endfun
fun{
x:vt0p
} list_vt_extend{n:int}
(xs1: list_vt(INV(x), n), x2: x):<!wrt> list_vt(x, n+1)
macdef list_vt_snoc = list_vt_extend
fun{x:vt0p}
list_vt_reverse{n:int}
(xs: list_vt(INV(x), n)):<!wrt> list_vt(x, n)
fun{a:vt0p}
list_vt_reverse_append{m,n:int}
(list_vt(INV(a), m), list_vt(a, n)):<!wrt> list_vt(a, m+n)
fun{x:vt0p}
list_vt_concat
(xss: List_vt(List_vt(INV(x)))):<!wrt> List0_vt(x)
implement main0 () = () where { // typedef T = int val xs1 = $list_vt{T}(1) val xs2 = $list_vt{T}(2) val xs3 = $list_vt{T}(3) val xss = $list_vt{List_vt(T)}(xs1, xs2, xs3) val xs123 = list_vt_concat (xss) // xs123 = [1, 2, 3] // val out = stdout_ref val () = fprint_list_vt<T> (out, xs123) // printing out 1, 2, 3 val () = fprint_newline (out) // val () = list_vt_free<T> (xs123) // } // end of [main]
fun{x:vt0p}
list_vt_split_at
{n:int}{i:nat | i <= n}
(list_vt(INV(x), n), int i):<!wrt> (list_vt(x, i), list_vt(x, n-i))
fun{x:vt0p}
list_vt_separate{n:int}
(
xs: &list_vt(INV(x), n) >> list_vt(x, n1), n1: &int? >> int(n1)
) : #[n1:nat|n1 <= n] list_vt(x, n-n1)
// staload UN = "prelude/SATS/unsafe.sats" // fun{a:vt0p} list_vt_qsort {n:nat} .<n>. ( xs: list_vt (a, n), cmp: cmpref(a) ) : list_vt (a, n) = let in // case+ xs of | @list_vt_cons (x0, xs1) => let val p_x0 = addr@(x0) // implement list_vt_separate$pred<a> (x) = let val ( pf, fpf | p_x0 ) = $UN.ptr_vtake{a}(p_x0) val ans = cmp (x, !p_x0) <= 0 // ascending order prval ((*void*)) = fpf (pf) in ans end // end of [list_vt_separate$pred] // var xs11 = xs1 // HX: xs11/xs12: <= x0 / > x0 val xs12 = list_vt_separate<a> (xs11) val xs11 = list_vt_qsort<a> (xs11, cmp) val xs12 = list_vt_qsort<a> (xs12, cmp) val () = xs1 := xs12 prval () = fold@ (xs) in list_vt_append (xs11, xs) end // end of [list_vt_cons] | ~list_vt_nil () => list_vt_nil () // end // end of [list_vt_qsort]Note that there is no memory allocation/deallocation involved in this implementation. It is formally verified in the type system of ATS that the list returned by list_vt_qsort is of the same length as its input. On a meta-level, it is evident that the returned list must be a permutation of the input as linear elements cannot be either discarded or duplicated.
fun{x:vt0p}
list_vt_separate$pred(x: &RD(x)): bool
fun{x:t0p}
list_vt_filter{n:int}
(list_vt(INV(x), n)):<!wrt> listLte_vt(x, n)
fun{x:t0p}
list_vt_filter$pred (x: &RD(x)):<> bool
fun{x:vt0p}
list_vt_filterlin{n:int}
(list_vt(INV(x), n)):<!wrt> listLte_vt(x, n)
fun{x:vt0p}
list_vt_filterlin$pred (x: &RD(x)):<> bool
fun{x:vt0p}
list_vt_filterlin$clear (x: &x >> x?):<!wrt> void
fun
{x:vt0p}
list_vt_app
(xs: !List_vt(INV(x))): void
fun{x:vt0p}
list_vt_appfree
(xs: List_vt(INV(x))): void
fun
{x:vt0p}
list_vt_app$fwork (x: &x >> _): void
fun{x:vt0p}
list_vt_appfree$fwork (x: &x >> x?): void
fun{
x:vt0p}{y:vt0p
} list_vt_map{n:int}
(xs: !list_vt(INV(x), n)): list_vt(y, n)
fun{
x:vt0p}{y:vt0p
} list_vt_map$fopr(x: &x >> _): (y)
fun{
x:vt0p}{y:vt0p
} list_vt_mapfree{n:int}
(xs: list_vt(INV(x), n)) : list_vt(y, n)
fun{
x:vt0p}{y:vt0p
} list_vt_mapfree$fopr(x: &(x) >> x?): (y)
fun{
x:vt0p
} list_vt_foreach (xs: !List_vt(INV(x))): void
fun{
x:vt0p}{env:vt0p
} list_vt_foreach_env (xs: !List_vt(INV(x)), env: &(env) >> _): void
fun{
x:vt0p}{env:vt0p
} list_vt_foreach$cont (x: &x, env: &env): bool
fun{
x:vt0p}{env:vt0p
} list_vt_foreach$fwork (x: &x >> _, env: &(env) >> _): void
fun{
x:vt0p
} list_vt_iforeach
{n:int} (xs: !list_vt(INV(x), n)): natLte(n)
fun{
x:vt0p}{env:vt0p
} list_vt_iforeach_env
{n:int} (xs: !list_vt(INV(x), n), env: &(env) >> _): natLte(n)
fun{
x:vt0p}{env:vt0p
} list_vt_iforeach$cont
(i: intGte(0), x: &x, env: &env): bool
fun{
x:vt0p}{env:vt0p
} list_vt_iforeach$fwork
(i: intGte(0), x: &x >> _, env: &(env) >> _): void
fun{
a:vt0p
} list_vt_mergesort
{n:int} (xs: list_vt(INV(a), n)):<!wrt> list_vt(a, n)
implement main () = let // val N = 10 val out = stdout_ref // typedef T = int val xs = $list_vt{T}(0, 9, 2, 7, 4, 5, 6, 3, 8, 1) val () = fprint_list_vt_sep<T> (out, xs, "; ") val () = fprint_newline (out) // implement list_vt_mergesort$cmp<T> (x1, x2) = compare (x1, x2) // val ys = list_vt_mergesort<T> (xs) val () = fprint_list_vt<T> (out, ys) val () = fprint_newline (out) val () = list_vt_free<T> (ys) // in 0(*normal*) end // end of [main]
fun{ a:vt0p } list_vt_mergesort$cmp(x1: &RD(a), x2: &RD(a)):<> int(*sgn*)
implement{a}
list_vt_mergesort$cmp (x, y) = gcompare_ref<a> (x, y)
fun{ a:vt0p } list_vt_mergesort_fun {n:int} ( xs: list_vt(INV(a), n), cmp: cmpref (a) ) :<!wrt> list_vt(a, n) // end of [list_vt_mergesort_fun]
fun{
a:vt0p
} list_vt_quicksort
{n:int} (xs: list_vt(INV(a), n)):<!wrt> list_vt(a, n)
implement main () = let // val N = 10 val out = stdout_ref // typedef T = int val xs = $list_vt{T}(0, 9, 2, 7, 4, 5, 6, 3, 8, 1) val () = fprint_list_vt_sep<T> (out, xs, "; ") val () = fprint_newline (out) // implement list_quicksort$cmp<T> (x1, x2) = compare (x1, x2) // val ys = list_vt_quicksort<T> (xs) val () = fprint_list_vt<T> (out, ys) val () = fprint_newline (out) val () = list_vt_free<T> (ys) // in 0(*normal*) end // end of [main]
fun{ a:vt0p } list_vt_quicksort$cmp(x1: &RD(a), x2: &RD(a)):<> int(*sgn*)
implement{a}
list_vt_quicksort$cmp (x, y) = gcompare_ref<a> (x, y)
fun{ a:vt0p } list_vt_quicksort_fun {n:int} ( xs: list_vt(INV(a), n), cmp: cmpref (a) ) :<!wrt> list_vt(a, n) // end of [list_vt_quicksort_fun]
overload [] with list_vt_get_at
overload [] with list_vt_set_at
overload iseqz with list_vt_is_nil
overload isneqz with list_vt_is_cons
overload length with list_vt_length
overload copy with list_vt_copy
overload free with list_vt_free
overload print with print_list_vt
overload prerr with prerr_list_vt
overload fprint with fprint_list_vt
overload fprint with fprint_list_vt_sep
This page is created with ATS by Hongwei Xi and also maintained by Hongwei Xi. |