VSL - The data.list Structure

# Copyright 2011  Petter Urkedal
#
# This file is part of the Viz Standard Library <http://www.vizlang.org/>.
#
# The Viz Standard Library (VSL) is free software: you can redistribute it
# and/or modify it under the terms of the GNU Lesser General Public License as
# published by the Free Software Foundation, either version 3 of the License,
# or (at your option) any later version.
#
# The VSL is distributed in the hope that it will be useful, but WITHOUT ANY
# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
# FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
# more details.
#
# You should have received a copy of the GNU Lesser General Public License
# along with the VSL.  If not, see <http://www.gnu.org/licenses/>.

open prelude.ubiquitous

val init : int  (int  α)  list α

val head : t α  α
 ## Given a non-empty list (xs), (head xs) is the first element.

val tail : t α  t α
 ## Given a non-empty list (xs), (tail xs) is the list following the first
 ## element.

val nth : int  t α  option α

val rev : t α  t α
 ## Reverse the order of elements of a list.

val fold : (α  β  β)  t α  β  β
 ## (fold f xs) composes the functions (f x) where (x) runs over (xs)::
 ##   fold f [x_1, ..., x_n] ≡ f x_n ∘ ... ∘ f x_1
 ## or in equation form::
 ##   fold f [] ≡ ident
 ##   fold f [x; xs] ≡ fold f xs ∘ f x

val foldr : (α  β  β)  t α  β  β
 ## (fold f xs ≡ fold f (rev xs)).

val fold2 : (α0 × α1  β  β)  t α0 × t α1  β  β

val iter : (α  effect ψ unit)  t α  effect ψ unit
 ## (iter f xs ≡ f x1 >> ... >> f xN) forms an effect-monad which iterates (f)
 ## over the elements of (xs)

val for_all : (α  bool)  t α  bool
 ## (for_all f xs) is true iff (f x) holds for all elements (x) of (xs).

val for_some : (α  bool)  t α  bool
 ## (for_some f xs) is true iff (f x) holds for at least one element (x) of
 ## (xs).

val count : (α  bool)  t α  int
 ## (count f xs) is the number of elements at which (f) returns true.

val length : t α  int
 ## (length xs ≡ count (_ ↦ true) xs) is the number of elements is (xs).

val find : (α  bool)  t α  option α
 ## (find f xs) returns the first element (x) of (xs) such that (f x), or
 ## (none) if no element is found.

val filter : (α  bool)  t α  t α
 ## (filter f xs) is the result of removing elements of (xs) at which (f) is
 ## false.

val bifilter : (α  bool)  t α  t α × t α
 ## (bifilter f zs) returns the pair ((xs, ys)) amounting to a partition of
 ## (zs) where (xs) are the elements at which (f) is true and (ys) are the
 ## remaining elements, both in the order they occur in (zs).

val take_while : (α  bool)  t α  t α

val drop_while : (α  bool)  t α  t α

val map : (α  β)  t α  t β
 ## (map f) is the lifting of (f) to element-wise function on a list
 ## determined by the equations::
 ##   map f [] ≡ []
 ##   map f [x; xs] ≡ [f x; map f xs]

val mapr : (α  β)  t α  t β
 ## (mapr f xs ≡ map f (rev xs))

val mapi : (int  α  β)  list α  list β

val cat : t α  t α  t α
 ## Concatenate two lists.

val catr : t α  t α  t α
 ## (catr xs ys ≡ cat (rev xs) ys)

val flatten : t (t α)  t α
 ## (flatten xss ≡ fold cat xss []) is the result of concatenating the
 ## elements of a list of lists.

val zip : t α × t β  t (α × β)
 ## Given two lists (xs) and (ys) of the same length, (zip xs ys) is the list
 ## of pairs taken from (xs) and (ys) in order.

val zip_trunc : t α × t β  t (α × β)
 ## (zip_trunc xs ys) is the list of pairs taken from (xs) and (ys) in order,
 ## truncating to the length of the shortest list.

val unzip : t (α × β)  t α × t β
 ## (unzip xs ≡ (map fst xs, map snd xs)) turns a list of pairs into two lists
 ## of the respective components.

include prelude.list