ATSLIB/prelude/list_vt

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.


  • list_vt
  • List_vt
  • List0_vt
  • List1_vt
  • listLt_vt
  • listLte_vt
  • listGt_vt
  • listGte_vt
  • listBtw_vt
  • listBtwe_vt
  • lemma_list_vt_param
  • list_vt_cast
  • list_vt_make_sing
  • list_vt_make_pair
  • fprint_list_vt
  • fprint_list_vt$sep
  • list_vt_is_nil
  • list_vt_is_cons
  • list_vt_is_sing
  • list_vt_is_pair
  • list_vt_unnil
  • list_vt_uncons
  • fprint_list_vt_sep
  • list_vt_length
  • list_vt_getref_at
  • list_vt_get_at
  • list_vt_set_at
  • list_vt_exch_at
  • list_vt_insert_at
  • list_vt_takeout_at
  • list_vt_copy
  • list_vt_copylin
  • list_vt_free
  • list_vt_freelin
  • list_vt_freelin$clear
  • list_vt_uninitize
  • list_vt_uninitize_fun
  • list_vt_uninitize$clear
  • list_vt_append
  • list_vt_extend
  • list_vt_snoc
  • list_vt_reverse
  • list_vt_reverse_append
  • list_vt_concat
  • list_vt_split_at
  • list_vt_separate
  • list_vt_separate$pred
  • list_vt_filter
  • list_vt_filter$pred
  • list_vt_filterlin
  • list_vt_filterlin$pred
  • list_vt_filterlin$clear
  • list_vt_app
  • list_vt_appfree
  • list_vt_app$fwork
  • list_vt_appfree$fwork
  • list_vt_map
  • list_vt_map$fopr
  • list_vt_mapfree
  • list_vt_mapfree$fopr
  • list_vt_foreach
  • list_vt_foreach_env
  • list_vt_foreach$cont
  • list_vt_foreach$fwork
  • list_vt_iforeach
  • list_vt_iforeach_env
  • list_vt_iforeach$cont
  • list_vt_iforeach$fwork
  • list_vt_mergesort
  • list_vt_mergesort$cmp
  • list_vt_mergesort_fun
  • list_vt_quicksort
  • list_vt_quicksort$cmp
  • list_vt_quicksort_fun
  • Overloaded Symbols
  • []
  • iseqz
  • isneqz
  • length
  • copy
  • free
  • print
  • prerr
  • fprint

  • list_vt

    Synopsis

    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]
    

    Description

    There are two data constructors list_vt_nil and list_vt_cons associated with list_vt; the former constructs a list of length 0, that is, an empty list while the latter takes an element x and a list xs of length n to construct a list of length n+1 such that x and xs are the head and tail of the newly constructed list, respectively.

    List_vt

    Synopsis

    vtypedef
    List_vt(a:vt0p) = [n:int] list_vt(a, n)

    Description

    This type is for linear lists of unspecified length.

    List0_vt

    Synopsis

    vtypedef
    List0_vt(a:vt0p) = [n:int | n >= 0] list_vt(a, n)

    Description

    This type is for linear lists of unspecified length that is greater than or equal to 0. Note that List0_vt is essentially equivalent to List_vt since the length of a list can never be negative. The proof function lemma_list_vt_param can be called explicitly to cast from List_vt to List0_vt.

    List1_vt

    Synopsis

    vtypedef
    List1_vt(a:vt0p) = [n:int | n >= 1] list_vt(a, n)

    Description

    This type is for linear lists of unspecified positive length.

    listLt_vt

    Synopsis

    vtypedef listLt_vt
      (a:vt0p, n:int) = [k:nat | k < n] list_vt(a, k)

    listLte_vt

    Synopsis

    vtypedef listLte_vt
      (a:vt0p, n:int) = [k:nat | k <= n] list_vt(a, k)

    listGt_vt

    Synopsis

    vtypedef listGt_vt
      (a:vt0p, n:int) = [k:int | k > n] list_vt(a, k)

    listGte_vt

    Synopsis

    vtypedef listGte_vt
      (a:vt0p, n:int) = [k:int | k >= n] list_vt(a, k)

    listBtw_vt

    Synopsis

    vtypedef listBtw_vt
      (a:vt0p, m:int, n:int) = [k:int | m <= k; k < n] list_vt(a, k)

    listBtwe_vt

    Synopsis

    vtypedef listBtwe_vt
      (a:vt0p, m:int, n:int) = [k:int | m <= k; k <= n] list_vt(a, k)

    lemma_list_vt_param

    Synopsis

    prfun
    lemma_list_vt_param
      {x:vt0p}{n:int}
      (xs: !list_vt(INV(x), n)): [n >= 0] void

    Description

    This proof function establishes that the integer n in any linear list type list_vt(T, n) is a natural number, where T can be a linear type.

    list_vt_cast

    Synopsis

    castfn
    list_vt_cast
      {x:vt0p}{n:int}
      (xs: list_vt(INV(x), n)):<> list_vt(x, n)

    Description

    This function can be employed to explicitly cast a linear list containing elements of type T1 into another linear list containing elements of type T2 whenever T1 is a subtype of T2.

    list_vt_make_sing

    Synopsis

    fun{x:vt0p}
    list_vt_make_sing (x: x):<!wrt> list_vt(x, 1)

    Description

    This function returns a linear list consisting of a given value.

    list_vt_make_pair

    Synopsis

    fun{x:vt0p}
    list_vt_make_pair (x1: x, x2: x):<!wrt> list_vt(x, 2)

    Description

    This function returns a linear list consisting of two given values.

    fprint_list_vt

    Synopsis

    fun{x:vt0p}
    fprint_list_vt
      (out: FILEref, xs: !List_vt(INV(x))): void

    Description

    This function prints the elements in a given linear list to the output channel provided as its first argument, and it calls the function fprint_list_vt$sep before printing an element as long as the element is not the first one. Note that printing each list element is handled by calling the function fprint_ref.

    fprint_list_vt$sep

    Synopsis

    fun{} fprint_list_vt$sep (out: FILEref): void

    list_vt_is_nil

    Synopsis

    fun{x:vt0p}
    list_vt_is_nil
      {n:int} (xs: !list_vt(INV(x), n)):<> bool (n==0)

    Description

    This function returns true if and only if its argument is a linear list of length 0.

    list_vt_is_cons

    Synopsis

    fun{x:vt0p}
    list_vt_is_cons
      {n:int} (xs: !list_vt(INV(x), n)):<> bool (n > 0)

    Description

    This function returns true if and only if its argument is a linear list of some positive length.

    list_vt_is_sing

    Synopsis

    fun{x:vt0p}
    list_vt_is_sing
      {n:int} (xs: !list_vt(INV(x), n)):<> bool (n==1)

    Description

    This function returns true if and only if its argument is a linear list of length 1, that is, a singleton linear list.

    list_vt_is_pair

    Synopsis

    fun{x:vt0p}
    list_vt_is_pair
      {n:int} (xs: !list_vt(INV(x), n)):<> bool (n==2)

    Description

    This function returns true if and only if its argument is a linear list of length 2.

    list_vt_unnil

    Synopsis

    fun{}
    list_vt_unnil{x:vt0p} (xs: list_vt(x, 0)):<> void

    list_vt_uncons

    Synopsis

    fun{x:vt0p}
    list_vt_uncons{n:pos}
      (xs: &list_vt(INV(x), n) >> list_vt(x, n-1)):<!wrt> x

    fprint_list_vt_sep

    Synopsis

    fun{x:vt0p}
    fprint_list_vt_sep
    (
      out: FILEref, xs: !List_vt(INV(x)), sep: NSH(string)
    ) : void // end of [fprint_list_vt_sep]

    Description

    This function prints the elements in a given linear list to the output channel provided as its first argument, interspersing the string sep between the printed list elements. Note that printing each list element is handled by calling the function fprint_ref.

    list_vt_length

    Synopsis

    fun{x:vt0p}
    list_vt_length{n:int} (xs: !list_vt(INV(x), n)):<> int n

    Description

    This function returns the length of a given linear list.

    list_vt_getref_at

    Synopsis

    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))

    Description

    Given a linear list xs of length n and a natural number i <= n, this function returns a pointer that points to the suffix of xs of length n-i. While this function itself is safe, any subsequent use of the returned pointer requires great caution.

    list_vt_get_at

    Synopsis

    fun{x:t0p}
    list_vt_get_at{n:int}
      (xs: !list_vt(INV(x), n), i: natLt n):<> x

    list_vt_set_at

    Synopsis

    fun{x:t0p}
    list_vt_set_at{n:int}
      (xs: !list_vt(INV(x), n), i: natLt n, x: x):<!wrt> void

    list_vt_exch_at

    Synopsis

    fun{x:vt0p}
    list_vt_exch_at{n:int}
      (xs: !list_vt(INV(x), n), i: natLt n, x: &x >> _):<!wrt> void

    list_vt_insert_at

    Synopsis

    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]

    Description

    Given a linear list xs of length n, a natural number i <= n, and an element x, this inserts x into xs immediately after the first i elements so that x becomes element i+1 in the returned list.

    list_vt_takeout_at

    Synopsis

    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

    Description

    Given a linear list xs of length n and a natural number i < n, this function takes out element i from xs.

    list_vt_copy

    Synopsis

    fun{x:t0p}
    list_vt_copy{n:int}
      (xs: !list_vt(INV(x), n)):<!wrt> list_vt(x, n)

    Description

    Given a linear list xs, this function returns a copy of xs. Note that the elements of xs are required to be of a linear type.

    list_vt_copylin

    Synopsis

    fun{x:vt0p}
    list_vt_copylin{n:int}
      (xs: !list_vt(INV(x), n)):<!wrt> list_vt(x, n)

    Description

    Given a linear list xs, this function returns a copy of xs. Note that the elements of xs are copied by callig the function list_vt_copylin$copy.

    list_vt_free

    Synopsis

    fun{x:t0p}
    list_vt_free (xs: List_vt(INV(x))):<!wrt> void

    Description

    This function frees the memory occupied by a given linear list. Note that the elements contained in the list must be nonlinear.

    list_vt_freelin

    Synopsis

    fun{x:vt0p}
    list_vt_freelin
      (xs: List_vt(INV(x))):<!wrt> void

    Description

    This function frees the memory occupied by a given linear list. Note that the elements contained in the list are freed by calling the function list_vt_freelin$clear.

    list_vt_freelin$clear

    Synopsis

    fun{x:vt0p}
    list_vt_freelin$clear (x: &x >> x?):<!wrt> void

    list_vt_uninitize

    Synopsis

    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]

    list_vt_uninitize_fun

    Synopsis

    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]

    Description

    This function frees the elements in a given linear list (but keeps the list itself).

    list_vt_uninitize$clear

    Synopsis

    fun{x:vt0p}
    list_vt_uninitize$clear (x: &(x) >> x?):<!wrt> void

    list_vt_append

    Synopsis

    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

    Description

    This functions appends its first list argument to its second list argument. Note that the two list arguments are consumed in the construction of the resulting list and thus no longer available after the function returns. There is no memory allocation/deallocation involved.

    list_vt_extend

    Synopsis

    fun{
    x:vt0p
    } list_vt_extend{n:int}
      (xs1: list_vt(INV(x), n), x2: x):<!wrt> list_vt(x, n+1)

    Description

    Given a list xs and an element x, this function extends xs with x at the end. Note that the time-complexity of this is function is O(n), where n is the length of xs.

    list_vt_snoc

    Synopsis

    macdef list_vt_snoc = list_vt_extend

    list_vt_reverse

    Synopsis

    fun{x:vt0p}
    list_vt_reverse{n:int}
      (xs: list_vt(INV(x), n)):<!wrt> list_vt(x, n)

    list_vt_reverse_append

    Synopsis

    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)

    list_vt_concat

    Synopsis

    fun{x:vt0p}
    list_vt_concat
      (xss: List_vt(List_vt(INV(x)))):<!wrt> List0_vt(x)

    Description

    Given a linear list xss, this function builds a concatenation of xss[0], xss[1], ..., and xss[n-1], where n is the length of xss and each xss[i] refers to element i in xss. Note that xss is freed and all of its elements are consumed in the construction of the returned list. In particular, there is no memory allocation involved in a call to list_vt_concat.

    Example

    The following code makes a simple use of list_vt_concat:
    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]
    

    list_vt_split_at

    Synopsis

    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))

    Description

    Given a linear list xs of length n and an integer i between 0 and n, inclusive, the function returns a prefix and a suffix of xs of length i and n-i, respectively.

    list_vt_separate

    Synopsis

    fun{x:vt0p}
    list_vt_separate{n:int}
    (
      xs: &list_vt(INV(x), n) >> list_vt(x, n1)
    ) : #[n1:nat|n1 <= n] list_vt(x, n-n1)

    Description

    This function splits a given linear list xs into two according to the predicate implemented by list_vt_separate$pred: the elements left in xs satisfy the predicate while those in the returned list do not.

    Example

    The following code implements the standard quicksort on linear lists:
    //
    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.

    list_vt_separate$pred

    Synopsis

    fun{x:vt0p}
    list_vt_separate$pred (x: &RD(x)): bool

    list_vt_filter

    Synopsis

    fun{x:t0p}
    list_vt_filter{n:int}
      (x: list_vt(INV(x), n)):<!wrt> listLte_vt(x, n)

    list_vt_filter$pred

    Synopsis

    fun{x:t0p}
    list_vt_filter$pred (x: &RD(x)):<> bool

    list_vt_filterlin

    Synopsis

    fun{x:vt0p}
    list_vt_filterlin
      {n:int} (list_vt(INV(x), n)):<!wrt> listLte_vt(x, n)

    list_vt_filterlin$pred

    Synopsis

    fun{x:vt0p}
    list_vt_filterlin$pred (x: &RD(x)):<> bool

    list_vt_filterlin$clear

    Synopsis

    fun{x:vt0p}
    list_vt_filterlin$clear (x: &x >> x?):<!wrt> void

    list_vt_app

    Synopsis

    fun{x:vt0p}
    list_vt_app (xs: !List_vt(INV(x))): void

    list_vt_appfree

    Synopsis

    fun{x:vt0p}
    list_vt_appfree
      (xs: List_vt(INV(x))): void

    Description

    This function is similar to list_vt_app. However, it frees each list node after applying to the node the function implemented by list_vt_appfree$fwork.

    list_vt_app$fwork

    Synopsis

    fun{x:vt0p}
    list_vt_app$fwork (x: &x >> _): void

    list_vt_appfree$fwork

    Synopsis

    fun{x:vt0p}
    list_vt_appfree$fwork (x: &x >> x?): void

    list_vt_map

    Synopsis

    fun{
    x:vt0p}{y:vt0p
    } list_vt_map{n:int}
      (xs: !list_vt(INV(x), n)): list_vt(y, n)

    Description

    Given a linear list xs of length n, this function returns a linear list consisting f(xs[i]), where i ranges from 0 until n-1, xs[i] refers to element i in xs and f is the function implemented by list_map_vt$fopr. Note that the given list xs is kept after the function returns. The implementation of this function in ATSLIB is tail-recursive.

    list_vt_map$fopr

    Synopsis

    fun{
    x:vt0p}{y:vt0p
    } list_vt_map$fopr(x: &x >> _): (y)

    list_vt_mapfree

    Synopsis

    fun{
    x:vt0p}{y:vt0p
    } list_vt_mapfree{n:int}
      (xs: list_vt(INV(x), n)) : list_vt(y, n)

    Description

    This function is similar to list_vt_map. However, it frees each list node after applying to the node the function implemented by list_vt_mapfree$fopr.

    list_vt_mapfree$fopr

    Synopsis

    fun{
    x:vt0p}{y:vt0p
    } list_vt_mapfree$fopr(x: &(x) >> x?): (y)

    list_vt_foreach

    Synopsis

    fun{
    x:vt0p
    } list_vt_foreach (xs: !List_vt(INV(x))): void

    Description

    Given a list xs of length n, this function traverses xs, applying to xs[i] the function implemented by list_vt_foreach$fwork, where i ranges from 0 until n-1, inclusive, and xs[i], treated as a left-value, refers to element i in xs. The traversal stops if the function implemented by list_vt_foreach$cont returns false.

    list_vt_foreach_env

    Synopsis

    fun{
    x:vt0p}{env:vt0p
    } list_vt_foreach_env (xs: !List_vt(INV(x)), env: &(env) >> _): void

    list_vt_foreach$cont

    Synopsis

    fun{
    x:vt0p}{env:vt0p
    } list_vt_foreach$cont (x: &x, env: &env): bool

    Description

    The default implementation of this function always returns true.

    list_vt_foreach$fwork

    Synopsis

    fun{
    x:vt0p}{env:vt0p
    } list_vt_foreach$fwork (x: &x >> _, env: &(env) >> _): void

    list_vt_iforeach

    Synopsis

    fun{
    x:vt0p
    } list_vt_iforeach
      {n:int} (xs: !list_vt(INV(x), n)): natLte(n)

    Description

    Given a linear list xs of length n, this function traverses xs, applying to (i, xs[i]) the function implemented by list_vt_iforeach$fwork, where i ranges from 0 until n-1, inclusive, and xs[i], treated as a left-value, refers to element i in xs. The traversal stops if the function implemented by list_vt_foreach$cont returns false.

    list_vt_iforeach_env

    Synopsis

    fun{
    x:vt0p}{env:vt0p
    } list_vt_iforeach_env
      {n:int} (xs: !list_vt(INV(x), n), env: &(env) >> _): natLte(n)

    list_vt_iforeach$cont

    Synopsis

    fun{
    x:vt0p}{env:vt0p
    } list_vt_iforeach$cont
      (i: intGte(0), x: &x, env: &env): bool

    Description

    The default implementation of this function always returns true.

    list_vt_iforeach$fwork

    Synopsis

    fun{
    x:vt0p}{env:vt0p
    } list_vt_iforeach$fwork
      (i: intGte(0), x: &x >> _, env: &(env) >> _): void

    list_vt_mergesort

    Synopsis

    fun{
    a:vt0p
    } list_vt_mergesort
      {n:int} (xs: list_vt(INV(a), n)):<!wrt> list_vt(a, n)

    Description

    Mergesort is of time-complexity O(n(log(n))), and it is a stable sorting algorithm. This function mergesorts its list argument according to the ordering implemented by list_vt_mergesort$cmp. Note that the list argument is consumed in the construction of the resulting sorted list and thus no longer available after the function returns. There is no memory allocation/deallocation involved in the implementation of list_vt_mergesort.

    Example

    The following code mergesorts a list of integers into a list of ascending integers:
    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]
    

    list_vt_mergesort$cmp

    Synopsis

    fun{
    a:vt0p
    } list_vt_mergesort$cmp (x1: &RD(a), x2: &RD(a)):<> int(*sgn*)

    Description

    This function is called in the implementation of list_vt_mergesort to perform comparison test on list elements, and its default implementation is based on gcompare_ref:
    implement{a}
    list_vt_mergesort$cmp (x, y) = gcompare_ref<a> (x, y)
    

    list_vt_mergesort_fun

    Synopsis

    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]

    Description

    This function does essentially the same as list_vt_mergesort except for allowing the comparison function to be provided as an argument.

    list_vt_quicksort

    Synopsis

    fun{
    a:vt0p
    } list_vt_quicksort
      {n:int} (xs: list_vt(INV(a), n)):<!wrt> list_vt(a, n)

    Description

    Quicksort is of time-complexity O(n(log(n))) on average (but can be O(n^2) in the worse case), and it is not a stable sorting algorithm. This function quicksorts its list argument according to the ordering implemented by list_vt_quicksort$cmp. Note that the list argument is consumed in the construction of the resulting sorted list and thus no longer available after the function returns. An implementation of this function may copy the list into an array, sort the array, copy the array back into the list, and then free the array.

    Example

    The following code quicksorts a list of integers into a list of ascending integers:
    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]
    

    list_vt_quicksort$cmp

    Synopsis

    fun{
    a:vt0p
    } list_vt_quicksort$cmp (x1: &RD(a), x2: &RD(a)):<> int(*sgn*)

    Description

    This function is called in the implementation of list_vt_quicksort to perform comparison test on list elements, and its default implementation is based on gcompare_ref:
    implement{a}
    list_vt_quicksort$cmp (x, y) = gcompare_ref<a> (x, y)
    

    list_vt_quicksort_fun

    Synopsis

    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]

    Description

    This function does essentially the same as list_vt_quicksort except for allowing the comparison function to be provided as an argument.

    Overloaded Symbols


    []

    Synopsis

    overload [] with list_vt_get_at
    overload [] with list_vt_set_at

    iseqz

    Synopsis

    overload iseqz with list_vt_is_nil

    isneqz

    Synopsis

    overload isneqz with list_vt_is_cons

    length

    Synopsis

    overload length with list_vt_length

    copy

    Synopsis

    overload copy with list_vt_free

    free

    Synopsis

    overload free with list_vt_free

    print

    Synopsis

    overload print with print_list_vt

    prerr

    Synopsis

    overload prerr with prerr_list_vt

    fprint

    Synopsis

    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. SourceForge.net Logo