Source

ocaml-llists / lazy_list.mli

Full commit
(* Lazy list interface
 *
 * Author: Vadim Shender
 *
 * This library 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 2.1 of the License, or (at your option) any later version,
 * with the special exception on linking described in file LICENSE.
 *
 * This library 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 this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *)


(** Lazy list type and operations. *)


type 'a node_t =
  Nil
| Cons of 'a * 'a t
and  'a t = 'a node_t lazy_t
(** The type of a lazy list. *)


(** {6 Constructors} *)

val empty : 'a t
(** The empty lazy list. *)

val cons : 'a -> 'a t -> 'a t
(** [Lazy_list.cons hd tl] constructs new lazy list from [hd] and lazy list
    [tl]. *)

val init : ?limit:int -> ?starti:int -> (int -> 'a) -> 'a t
(** [Lazy_list.init f] constructs new lazy list with element number [i]
    initialized to the result of [f i]. If [starti] is given then numeration
    begins from it (by default from 0). If [limit] is given then length of new
    lazy list is [limit] (by default lazy list is infinite). Raise
    [Invalid_argument "Lazy_list.init"] if [limit] is negative. *)

val make : ?limit:int -> 'a -> 'a t
(** [Lazy_list.make x] constructs new lazy list initialized with [x]. If [limit]
    is given then length of new lazy list is [limit] (by default list is
    infinite). Raise [Invalid_argument "Lazy_list.make"] if [limit] is
    negative. *)

val interval : ?step:int -> int -> int -> int t
(** [Lazy_list.interval ~step:s a b] constructs new lazy list from elements
    [a], [a+s], [a+2*s], ... up to [b]. Default value for step is 1. *)

val interval_inf : ?step:int -> int -> int t
(** [Lazy_list.interval_inf ~step:s a] constructs new infinite lazy list from
    elements [a], [a+s], [a+2*s], ... . Default value for step is 1. *)


(** {6 Access} *)

val hd : 'a t -> 'a
(** Return the first element of the given lazy list. Raise
    [Failure "Lazy_list.hd"] if the list is empty. *)

val tl : 'a t -> 'a t
(** Return the given lazy list without its first element. Raise
    [Failure "Lazy_list.tl"] if the list is empty. *)

val nth : 'a t -> int -> 'a
(** Return the [n]-th element of the given lazy list. The first element (head
    of the list) is at position 0. Raise [Failure "Lazy_list.nth"] if the list
    is too short. Raise [Invalid_argument "Lazy_list.nth"] if [n] is
    negative. *)


(** {6 Common functions} *)

val length : ?limit:int -> 'a t -> int
(** Return the length (number of elements) of the given lazy list. If [limit] is
    given then counting is only bound by the first [limit] memebers of the lazy
    list [l] (it may be useful for assuring that list has at least [limit]
    elements: [length ~limit:limit l = limit]. Without given [limit] it'll loop
    infinitely on an infinite lazy list. *)


val append : 'a t -> 'a t -> 'a t
(** Return new lazy list which is the catenation of two argument-lists. Same
    function as the infix operator [%@]. *)

val concat : 'a t t -> 'a t
(** Return new lazy list which is the catenation of the list of lists.
    The elements of the argument are all concatenated together (in the same
    order) to give the result. *)

val flatten : 'a t t -> 'a t
(** Same as [Lazy_list.concat] *)


(** {6 Iterators} *)

val iter : ?limit:int -> ('a -> unit) -> 'a t -> unit
(** [Lazy_list.iter f l] applies function [f] in turn to the elements of the
    lazy list [l]. It is equivalent to [begin f a1; f a2; ...; () end]. If
    [limit] is given then applying is only bound by the first [limit] memebers
    of the lazy list [l]. Without given [limit] it'll loop infinitely on an
    infinite lazy list. Raise [Invalid_argument "Lazy_list.iter"] if [limit] is
    negative. *)

val iteri : ?limit:int -> ?starti:int -> (int -> 'a -> unit) -> 'a t -> unit
(** Same as [Lazy_list.iter], but function [f] is applied to serial number of
    lazy list element (starting from 0 by default) together with that element
    itself. [Lazy_list.iteri f [% a1; a2; ...]] is equivalent to
    [begin f 0 a1; f 1 a2; ...; () end]. If [starti] is given then serial
    numbers start from [starti]. As for [iter], if [limit] is given then
    applying is only bound by the first [limit] members of the lazy list [l].
    Without given [limit] it'll loop infinitely on an infinite lazy list. Raise
    [Invalid_argument "Lazy_list.iteri"] if [limit] is negative. *)

val map : ('a -> 'b) -> 'a t -> 'b t
(** [Lazy_list.map f [% a1; a2; ... ]] applies function [f] in turn to the
    elements of the given lazy list, and builds the lazy list
    [[% f a1; f a2; ... ]] with the results returned by [f]. *)

val mapi : ?starti:int -> (int -> 'a -> 'b) -> 'a t -> 'b t
(** Same as [Lazy_list.map], but function [f] is applied to serial number of
    lazy list element (starting from 0 by default) together with that element
    itself. [Lazy_list.mapi f [% a1; a2; ...] ] builds the lazy list
    [[% f 0 a1; f 1 a2; ... ]] with the results returned by [f]. If [starti] is
    given then serial numbers start from [starti]. *)

val fold_left : ?limit:int -> ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
(** [Lazy_list.fold_left f a [% b1; ...; bn ]] is
    [f (... (f (f a b1) b2) ...) bn]. If [limit] is given then folding is
    only bound by the first [limit] members of the lazy list. Without given
    [limit] it'll loop infinitely on an infinite lazy list. Raise
    [Invalid_argument "Lazy_list.fold_left"] if [limit] is negative. *)

val fold_right : ?limit:int -> ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
(** [Lazy_list.fold_right f [% a1; ...; an ] b] is
    [f a1 (f a2 (... (f an b) ...))]. If [limit] is given then folding is
    only bound by the first [limit] members of the lazy list. Without given
    [limit] it'll loop infinitely on an infinite lazy list. Raise
    [Invalid_argument "Lazy_list.fold_right"] if [limit] is negative. Not
    tail-recursive. *)


(** {6 Iterators on two lists} *)

val iter2 : ?limit:int -> ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
(** [Lazy_list.iter2 f [% a1; a2; ... ] [% b1; b2; ... ]] calls in turn
    [f a1 b1; f a2 b2; ...]. If [limit] is given then iteration is bound only
    by the first [limit] members of the lazy lists. Without given [limit] it'll
    loop infinitely if given lazy lists both are infinite. Raise
    [Invalid_argument "Lazy_list.iter2"] if the two lists have different lengths
    or [limit] is negative. *)

val iteri2 : ?limit:int -> ?starti:int ->
             (int -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit
(** Same as [Lazy_list.iter2], but function [f] is applied to serial number of a
    pair of lazy list elements (starting from 0 by default) together with those
    elements itself. [Lazy_list.iteri2 f [% a1; a2; ... ] [% b1; b2; ... ]] is
    equivalent to [begin f 0 a1 b1; f 1 a2 b2; ...; () end]. If [starti] is
    given then serial numbers start from [starti]. As for [iter], if [limit] is
    given then applying is only bound by the first [limit] members of the lazy
    list [l]. Without given [limit] it'll loop infinitely on an infinite lazy
    list. Raise [Invalid_argument "Lazy_list.iteri2"] if the two lists have
    different lengths or [limit] is negative. *)

val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
(** [Lazy_list.map2 f [% a1; a2; ... ] [% b1; b2; ... ]] applies function [f] in
    turn to the elements of the given lazy lists by pairs, and builds the lazy
    list [[% f a1 b1; f a2 b2; ... ]] with the results returned by [f]. Raise
    [Invalid_argument "Lazy_list.map2"] if the two lists have different
    lengths. *)

val mapi2 : ?starti:int -> (int -> 'a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t
(** Same as [Lazy_list.map2], but function [f] is applied to serial number of a
    pair of lazy list elements (starting from 0 by default) together with those
    elements itself. [Lazy_list.mapi2 f [% a1; a2; ...] [% b1; b2; ...]] builds
    the lazy list [[% f 0 a1 b1; f 1 a2 b2; ... ]] with the results returned by
    [f]. If [starti] is given then serial numbers start from [starti]. Raise
    [Invalid_argument "Lazy_list.map2"] if the two lists have different
    lengths. *)

val fold_left2 : ?limit:int ->
                 ('a -> 'b -> 'c -> 'a) -> 'a -> 'b t -> 'c t -> 'a
(** [Lazy_list.fold_left2 f a [% b1; ...; bn ] [% c1; ...; cn ]] is
    [f (... (f (f a b1 c1) b2 c2) ...) bn cn]. If [limit] is given then folding
    is only bound by the first [limit] members of the lazy lists. Without
    given [limit] it'll loop infinitely if given lazy lists both are infinite.
    Raise [Invalid_argument "Lazy_list.fold_left2"] if the two lists have
    different lengths or [limit] is negative. *)

val fold_right2 : ?limit:int ->
                  ('a -> 'b -> 'c -> 'c) -> 'a t -> 'b t -> 'c -> 'c
(** [Lazy_list.fold_right f [% a1; ...; an ] [% b1; ...; bn ] c] is
    [f a1 b1 (f a2 b2 (... (f an bn c) ...))]. If [limit] is given then folding
    is only bound by the first [limit] members of the lazy lists. Without
    given [limit] it'll loop infinitely if given lazy lists both are infinite.
    Raise [Invalid_argument "Lazy_list.fold_right2"] if the two lists have
    different lengths or [limit] is negative. Not tail-recursive. *)


(** {6 List scanning} *)

val for_all : ?limit:int -> ('a -> bool) -> 'a t -> bool
(** [Lazy_list.for_all p [% a1; a2; ... ]] checks if all elements of the lazy
    list satisfy the predicate p. That is, it returns
    [(p a1) && (p a2) && ...]. If [limit] is given then iteration is bound
    by only the first [limit] members of the lazy list. Without given [limit] it
    may loop infinitely on an infinite lazy list. Raise
    [Invalid_argument "Lazy_list.for_all"] if [limit] is negative. *)

val exists : ?limit:int -> ('a -> bool) -> 'a t -> bool
(** [Lazy_list.exists p [% a1; a2; ... ]] checks if at least one element of the
    lazy list satisfies the predicate p. That is, it returns
    [(p a1) || (p a2) || ...]. If [limit] is given then iteration is bound
    by only the first [limit] members of the lazy list. Without given [limit] it
    may loop infinitely on an infinite lazy list. Raise
    [Invalid_argument "Lazy_list.exists"] if [limit] is negative. *)

val for_all2 : ?limit:int -> ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
(** Same as [Lazy_list.for_all], but for a two-argument predicate.
    As for [Lazy_list.for_all], if [limit] is given then iteration is bound
    by only the first [limit] members of the lazy lists. Without given [limit]
    it may loop infinitely if given lazy lists both are infinite. Raise
    [Invalid_argument "Lazy_list.for_all2"] if the two lists have different
    lengths or [limit] is negative. *)

val exists2 : ?limit:int -> ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
(** Same as [Lazy_list.exists], but for a two-argument predicate.
    As for [Lazy_list.exists], if [limit] is given then iteration is bound
    by only the first [limit] members of the lazy lists. Without given [limit]
    it may loop infinitely if given lazy lists both are infinite. Raise
    [Invalid_argument "Lazy_list.exists2"] if the two lists have different
    lengths or [limit] is negative. *)


val mem : ?limit:int -> 'a -> 'a t -> bool
(** [Lazy_list.mem a l] is true if and only if [a] is equal to an element of
    l. *)

val memq : ?limit:int -> 'a -> 'a t -> bool
(** Same as [Lazy_list.mem], but uses physical equality instead of structural
    equality to compare elements. *)


(** {6 List searching} *)

val find : ?limit:int -> ('a -> bool) -> 'a t -> 'a
(** [Lazy_list.find p l] returns the first element of the list [l] that
    satisfies the predicate [p]. If [limit] is given then search is bound by
    only the first [limit] members of the lazy list. Without given [limit] it
    may loop infinitely on an infinite lazy list. Raise [Not_found] if there is
    no value that satisfies [p] in the list [l]. Raise
    [Invalid_argument "Lazy_list.find"] if [limit] is negative. *)

val findi : ?limit:int -> ?starti:int -> (int -> 'a -> bool) -> 'a t -> int * 'a
(** Same as [Lazy_list.find], but predicate [p] is applied to serial number of
    lazy list element (starting from 0 by default) together with that element
    itself. If [starti] is given then serial numbers start from [starti]. As for
    [Lazy_list.find], if [limit] is given then search is only bound by the
    first [limit] members of the lazy list. Without given [limit] it may loop
    infinitely on an infinite lazy list. Raise [Not_found] if there is no value
    that satisfies [p] in the list [l]. Raise
    [Invalid_argument "Lazy_list.find"] if [limit] is negative. *)

val find_all : ('a -> bool) -> 'a t -> 'a t
(** [Lazy_list.find_all p l] returns new lazy list, which contains all elements
    of the lazy list [l] that satisfy the predicate [p]. The order of elements
    in the input lazy list is preserved. *)

val filter : ('a -> bool) -> 'a t -> 'a t
(** [Lazy_list.filter] is another name for [Lazy_list.find_all]. *)

val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
(** [Lazy_list.partition p l] returns a pair of lazy lists [(l1, l2)], where
    [l1] is the lazy list of all the elements of [l] that satisfy the predicate
    [p], and [l2] is the list of all the elements of [l] that do not satisfy
    [p]. The order of the elements in the input lazy list is preserved. *)


(** {6 List combine} *)

val split : ('a * 'b) t -> 'a t * 'b t
(** Transform a lazy list of pairs into a pair of lazy lists:
    [Lazy_list.split [% (a1, b1); (a2, b2); ... ]] is
    [([% a1; a2; ... ], [% b1; b2; ... ])]. *)

val combine : 'a t -> 'b t -> ('a * 'b) t
(** Transform a pair of lazy lists into a list of pairs:
    [Lazy_list.combine [% a1; a2; ... ] [% b1; b2; ... ]] is
    [% (a1, b1); (a2, b2); ... ]. Forcing of elements of resulting lazy lists
    will raise [Invalid_argument "Lazy_list.combine"] if the two lazy lists
    have different lengths. *)


(** {6 Other functions} *)

val split_nth : int -> 'a t -> 'a t * 'a t
(** [Lazy_list.split_nth n l] returns two lists [l1] and [l2], where [l1]
    containing the first [n] elements of [l] and [l2] the others. Raise
    [Invalid_argument "Lazy_list.split_nth"] if [n] is outside of [l] size
    bounds. *)

val take : int -> 'a t -> 'a t
(** [Lazy_list.take n l] returns new lazy list containing up to the [n] first
    elements from the lazy list [l], if available. *)

val drop : int -> 'a t -> 'a t
(** [Lazy_list.drop n l] returns new lazy list containing elements from the
    lazy list [l] without the first [n] elements, or the empty list if [l]
    have less than [n] elements. *)

val takewhile : ('a -> bool) -> 'a t -> 'a t
(** [Lazy_list.takewhile p l] returns new lazy list containing the first
    elements of list [l] which satisfy the predicate [p]. *)

val dropwhile : ('a -> bool) -> 'a t -> 'a t
(** [Lazy_list.dropwhile p l] returns new lazy list containing elements from the
    lazy list [l] without the first elements which satisfy the predicate [p]. *)


(** {6 Type conversion} *)

val of_list : 'a list -> 'a t
(** [Lazy_list.of_list l] builds a lazy list from the ordinary list [l]. *)

val to_list : ?limit:int -> 'a t -> 'a list
(** [Lazy_list.to_list l] builds an ordinary list from the lazy list [l]. If
    [limit] is given then only the first [limit] members of the [l] are used
    for building new list. Without given [limit] it'll loop infinitely on an
    infinite lazy list. Raise [Invalid_argument "Lazy_list.to_list"] if [limit]
    is negative. Not tail-recursive. *)


val of_stream : 'a Stream.t -> 'a t
(** [Lazy_list.of_stream s] builds a lazy list from the stream [s]. *)

val to_stream : 'a t -> 'a Stream.t
(** [Lazy_list.to_stream l] builds a stream from the lazy list [l]. *)


val of_channel : in_channel -> int t
(** [Lazy_list.of_channel ic] builds a lazy_list from bytes readed from input
    channel [ic]. *)

val to_channel : ?limit:int -> int t -> out_channel -> unit
(** [Lazy_list.to_channel l oc] writes bytes which are contained in lazy list
    [l] to output channel [oc]. *)