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