Commits

Vadim Shender committed 27165bc

initial commit

Comments (0)

Files changed (20)

+version 0.1:
+  * First public release
+
+		  GNU LESSER GENERAL PUBLIC LICENSE
+		       Version 2.1, February 1999
+
+ Copyright (C) 1991, 1999 Free Software Foundation, Inc.
+ 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+[This is the first released version of the Lesser GPL.  It also counts
+ as the successor of the GNU Library Public License, version 2, hence
+ the version number 2.1.]
+
+			    Preamble
+
+  The licenses for most software are designed to take away your
+freedom to share and change it.  By contrast, the GNU General Public
+Licenses are intended to guarantee your freedom to share and change
+free software--to make sure the software is free for all its users.
+
+  This license, the Lesser General Public License, applies to some
+specially designated software packages--typically libraries--of the
+Free Software Foundation and other authors who decide to use it.  You
+can use it too, but we suggest you first think carefully about whether
+this license or the ordinary General Public License is the better
+strategy to use in any particular case, based on the explanations below.
+
+  When we speak of free software, we are referring to freedom of use,
+not price.  Our General Public Licenses are designed to make sure that
+you have the freedom to distribute copies of free software (and charge
+for this service if you wish); that you receive source code or can get
+it if you want it; that you can change the software and use pieces of
+it in new free programs; and that you are informed that you can do
+these things.
+
+  To protect your rights, we need to make restrictions that forbid
+distributors to deny you these rights or to ask you to surrender these
+rights.  These restrictions translate to certain responsibilities for
+you if you distribute copies of the library or if you modify it.
+
+  For example, if you distribute copies of the library, whether gratis
+or for a fee, you must give the recipients all the rights that we gave
+you.  You must make sure that they, too, receive or can get the source
+code.  If you link other code with the library, you must provide
+complete object files to the recipients, so that they can relink them
+with the library after making changes to the library and recompiling
+it.  And you must show them these terms so they know their rights.
+
+  We protect your rights with a two-step method: (1) we copyright the
+library, and (2) we offer you this license, which gives you legal
+permission to copy, distribute and/or modify the library.
+
+  To protect each distributor, we want to make it very clear that
+there is no warranty for the free library.  Also, if the library is
+modified by someone else and passed on, the recipients should know
+that what they have is not the original version, so that the original
+author's reputation will not be affected by problems that might be
+introduced by others.
+
+  Finally, software patents pose a constant threat to the existence of
+any free program.  We wish to make sure that a company cannot
+effectively restrict the users of a free program by obtaining a
+restrictive license from a patent holder.  Therefore, we insist that
+any patent license obtained for a version of the library must be
+consistent with the full freedom of use specified in this license.
+
+  Most GNU software, including some libraries, is covered by the
+ordinary GNU General Public License.  This license, the GNU Lesser
+General Public License, applies to certain designated libraries, and
+is quite different from the ordinary General Public License.  We use
+this license for certain libraries in order to permit linking those
+libraries into non-free programs.
+
+  When a program is linked with a library, whether statically or using
+a shared library, the combination of the two is legally speaking a
+combined work, a derivative of the original library.  The ordinary
+General Public License therefore permits such linking only if the
+entire combination fits its criteria of freedom.  The Lesser General
+Public License permits more lax criteria for linking other code with
+the library.
+
+  We call this license the "Lesser" General Public License because it
+does Less to protect the user's freedom than the ordinary General
+Public License.  It also provides other free software developers Less
+of an advantage over competing non-free programs.  These disadvantages
+are the reason we use the ordinary General Public License for many
+libraries.  However, the Lesser license provides advantages in certain
+special circumstances.
+
+  For example, on rare occasions, there may be a special need to
+encourage the widest possible use of a certain library, so that it becomes
+a de-facto standard.  To achieve this, non-free programs must be
+allowed to use the library.  A more frequent case is that a free
+library does the same job as widely used non-free libraries.  In this
+case, there is little to gain by limiting the free library to free
+software only, so we use the Lesser General Public License.
+
+  In other cases, permission to use a particular library in non-free
+programs enables a greater number of people to use a large body of
+free software.  For example, permission to use the GNU C Library in
+non-free programs enables many more people to use the whole GNU
+operating system, as well as its variant, the GNU/Linux operating
+system.
+
+  Although the Lesser General Public License is Less protective of the
+users' freedom, it does ensure that the user of a program that is
+linked with the Library has the freedom and the wherewithal to run
+that program using a modified version of the Library.
+
+  The precise terms and conditions for copying, distribution and
+modification follow.  Pay close attention to the difference between a
+"work based on the library" and a "work that uses the library".  The
+former contains code derived from the library, whereas the latter must
+be combined with the library in order to run.
+
+		  GNU LESSER GENERAL PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. This License Agreement applies to any software library or other
+program which contains a notice placed by the copyright holder or
+other authorized party saying it may be distributed under the terms of
+this Lesser General Public License (also called "this License").
+Each licensee is addressed as "you".
+
+  A "library" means a collection of software functions and/or data
+prepared so as to be conveniently linked with application programs
+(which use some of those functions and data) to form executables.
+
+  The "Library", below, refers to any such software library or work
+which has been distributed under these terms.  A "work based on the
+Library" means either the Library or any derivative work under
+copyright law: that is to say, a work containing the Library or a
+portion of it, either verbatim or with modifications and/or translated
+straightforwardly into another language.  (Hereinafter, translation is
+included without limitation in the term "modification".)
+
+  "Source code" for a work means the preferred form of the work for
+making modifications to it.  For a library, complete source code means
+all the source code for all modules it contains, plus any associated
+interface definition files, plus the scripts used to control compilation
+and installation of the library.
+
+  Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope.  The act of
+running a program using the Library is not restricted, and output from
+such a program is covered only if its contents constitute a work based
+on the Library (independent of the use of the Library in a tool for
+writing it).  Whether that is true depends on what the Library does
+and what the program that uses the Library does.
+  
+  1. You may copy and distribute verbatim copies of the Library's
+complete source code as you receive it, in any medium, provided that
+you conspicuously and appropriately publish on each copy an
+appropriate copyright notice and disclaimer of warranty; keep intact
+all the notices that refer to this License and to the absence of any
+warranty; and distribute a copy of this License along with the
+Library.
+
+  You may charge a fee for the physical act of transferring a copy,
+and you may at your option offer warranty protection in exchange for a
+fee.
+
+  2. You may modify your copy or copies of the Library or any portion
+of it, thus forming a work based on the Library, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+    a) The modified work must itself be a software library.
+
+    b) You must cause the files modified to carry prominent notices
+    stating that you changed the files and the date of any change.
+
+    c) You must cause the whole of the work to be licensed at no
+    charge to all third parties under the terms of this License.
+
+    d) If a facility in the modified Library refers to a function or a
+    table of data to be supplied by an application program that uses
+    the facility, other than as an argument passed when the facility
+    is invoked, then you must make a good faith effort to ensure that,
+    in the event an application does not supply such function or
+    table, the facility still operates, and performs whatever part of
+    its purpose remains meaningful.
+
+    (For example, a function in a library to compute square roots has
+    a purpose that is entirely well-defined independent of the
+    application.  Therefore, Subsection 2d requires that any
+    application-supplied function or table used by this function must
+    be optional: if the application does not supply it, the square
+    root function must still compute square roots.)
+
+These requirements apply to the modified work as a whole.  If
+identifiable sections of that work are not derived from the Library,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works.  But when you
+distribute the same sections as part of a whole which is a work based
+on the Library, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote
+it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Library.
+
+In addition, mere aggregation of another work not based on the Library
+with the Library (or with a work based on the Library) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+  3. You may opt to apply the terms of the ordinary GNU General Public
+License instead of this License to a given copy of the Library.  To do
+this, you must alter all the notices that refer to this License, so
+that they refer to the ordinary GNU General Public License, version 2,
+instead of to this License.  (If a newer version than version 2 of the
+ordinary GNU General Public License has appeared, then you can specify
+that version instead if you wish.)  Do not make any other change in
+these notices.
+
+  Once this change is made in a given copy, it is irreversible for
+that copy, so the ordinary GNU General Public License applies to all
+subsequent copies and derivative works made from that copy.
+
+  This option is useful when you wish to copy part of the code of
+the Library into a program that is not a library.
+
+  4. You may copy and distribute the Library (or a portion or
+derivative of it, under Section 2) in object code or executable form
+under the terms of Sections 1 and 2 above provided that you accompany
+it with the complete corresponding machine-readable source code, which
+must be distributed under the terms of Sections 1 and 2 above on a
+medium customarily used for software interchange.
+
+  If distribution of object code is made by offering access to copy
+from a designated place, then offering equivalent access to copy the
+source code from the same place satisfies the requirement to
+distribute the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+  5. A program that contains no derivative of any portion of the
+Library, but is designed to work with the Library by being compiled or
+linked with it, is called a "work that uses the Library".  Such a
+work, in isolation, is not a derivative work of the Library, and
+therefore falls outside the scope of this License.
+
+  However, linking a "work that uses the Library" with the Library
+creates an executable that is a derivative of the Library (because it
+contains portions of the Library), rather than a "work that uses the
+library".  The executable is therefore covered by this License.
+Section 6 states terms for distribution of such executables.
+
+  When a "work that uses the Library" uses material from a header file
+that is part of the Library, the object code for the work may be a
+derivative work of the Library even though the source code is not.
+Whether this is true is especially significant if the work can be
+linked without the Library, or if the work is itself a library.  The
+threshold for this to be true is not precisely defined by law.
+
+  If such an object file uses only numerical parameters, data
+structure layouts and accessors, and small macros and small inline
+functions (ten lines or less in length), then the use of the object
+file is unrestricted, regardless of whether it is legally a derivative
+work.  (Executables containing this object code plus portions of the
+Library will still fall under Section 6.)
+
+  Otherwise, if the work is a derivative of the Library, you may
+distribute the object code for the work under the terms of Section 6.
+Any executables containing that work also fall under Section 6,
+whether or not they are linked directly with the Library itself.
+
+  6. As an exception to the Sections above, you may also combine or
+link a "work that uses the Library" with the Library to produce a
+work containing portions of the Library, and distribute that work
+under terms of your choice, provided that the terms permit
+modification of the work for the customer's own use and reverse
+engineering for debugging such modifications.
+
+  You must give prominent notice with each copy of the work that the
+Library is used in it and that the Library and its use are covered by
+this License.  You must supply a copy of this License.  If the work
+during execution displays copyright notices, you must include the
+copyright notice for the Library among them, as well as a reference
+directing the user to the copy of this License.  Also, you must do one
+of these things:
+
+    a) Accompany the work with the complete corresponding
+    machine-readable source code for the Library including whatever
+    changes were used in the work (which must be distributed under
+    Sections 1 and 2 above); and, if the work is an executable linked
+    with the Library, with the complete machine-readable "work that
+    uses the Library", as object code and/or source code, so that the
+    user can modify the Library and then relink to produce a modified
+    executable containing the modified Library.  (It is understood
+    that the user who changes the contents of definitions files in the
+    Library will not necessarily be able to recompile the application
+    to use the modified definitions.)
+
+    b) Use a suitable shared library mechanism for linking with the
+    Library.  A suitable mechanism is one that (1) uses at run time a
+    copy of the library already present on the user's computer system,
+    rather than copying library functions into the executable, and (2)
+    will operate properly with a modified version of the library, if
+    the user installs one, as long as the modified version is
+    interface-compatible with the version that the work was made with.
+
+    c) Accompany the work with a written offer, valid for at
+    least three years, to give the same user the materials
+    specified in Subsection 6a, above, for a charge no more
+    than the cost of performing this distribution.
+
+    d) If distribution of the work is made by offering access to copy
+    from a designated place, offer equivalent access to copy the above
+    specified materials from the same place.
+
+    e) Verify that the user has already received a copy of these
+    materials or that you have already sent this user a copy.
+
+  For an executable, the required form of the "work that uses the
+Library" must include any data and utility programs needed for
+reproducing the executable from it.  However, as a special exception,
+the materials to be distributed need not include anything that is
+normally distributed (in either source or binary form) with the major
+components (compiler, kernel, and so on) of the operating system on
+which the executable runs, unless that component itself accompanies
+the executable.
+
+  It may happen that this requirement contradicts the license
+restrictions of other proprietary libraries that do not normally
+accompany the operating system.  Such a contradiction means you cannot
+use both them and the Library together in an executable that you
+distribute.
+
+  7. You may place library facilities that are a work based on the
+Library side-by-side in a single library together with other library
+facilities not covered by this License, and distribute such a combined
+library, provided that the separate distribution of the work based on
+the Library and of the other library facilities is otherwise
+permitted, and provided that you do these two things:
+
+    a) Accompany the combined library with a copy of the same work
+    based on the Library, uncombined with any other library
+    facilities.  This must be distributed under the terms of the
+    Sections above.
+
+    b) Give prominent notice with the combined library of the fact
+    that part of it is a work based on the Library, and explaining
+    where to find the accompanying uncombined form of the same work.
+
+  8. You may not copy, modify, sublicense, link with, or distribute
+the Library except as expressly provided under this License.  Any
+attempt otherwise to copy, modify, sublicense, link with, or
+distribute the Library is void, and will automatically terminate your
+rights under this License.  However, parties who have received copies,
+or rights, from you under this License will not have their licenses
+terminated so long as such parties remain in full compliance.
+
+  9. You are not required to accept this License, since you have not
+signed it.  However, nothing else grants you permission to modify or
+distribute the Library or its derivative works.  These actions are
+prohibited by law if you do not accept this License.  Therefore, by
+modifying or distributing the Library (or any work based on the
+Library), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Library or works based on it.
+
+  10. Each time you redistribute the Library (or any work based on the
+Library), the recipient automatically receives a license from the
+original licensor to copy, distribute, link with or modify the Library
+subject to these terms and conditions.  You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties with
+this License.
+
+  11. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License.  If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Library at all.  For example, if a patent
+license would not permit royalty-free redistribution of the Library by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Library.
+
+If any portion of this section is held invalid or unenforceable under any
+particular circumstance, the balance of the section is intended to apply,
+and the section as a whole is intended to apply in other circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system which is
+implemented by public license practices.  Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+  12. If the distribution and/or use of the Library is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Library under this License may add
+an explicit geographical distribution limitation excluding those countries,
+so that distribution is permitted only in or among countries not thus
+excluded.  In such case, this License incorporates the limitation as if
+written in the body of this License.
+
+  13. The Free Software Foundation may publish revised and/or new
+versions of the Lesser General Public License from time to time.
+Such new versions will be similar in spirit to the present version,
+but may differ in detail to address new problems or concerns.
+
+Each version is given a distinguishing version number.  If the Library
+specifies a version number of this License which applies to it and
+"any later version", you have the option of following the terms and
+conditions either of that version or of any later version published by
+the Free Software Foundation.  If the Library does not specify a
+license version number, you may choose any version ever published by
+the Free Software Foundation.
+
+  14. If you wish to incorporate parts of the Library into other free
+programs whose distribution conditions are incompatible with these,
+write to the author to ask for permission.  For software which is
+copyrighted by the Free Software Foundation, write to the Free
+Software Foundation; we sometimes make exceptions for this.  Our
+decision will be guided by the two goals of preserving the free status
+of all derivatives of our free software and of promoting the sharing
+and reuse of software generally.
+
+			    NO WARRANTY
+
+  15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO
+WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW.
+EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR
+OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY
+KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE
+LIBRARY IS WITH YOU.  SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME
+THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
+
+  16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN
+WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY
+AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU
+FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR
+CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE
+LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING
+RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A
+FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF
+SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
+DAMAGES.
+
+		     END OF TERMS AND CONDITIONS
+
+           How to Apply These Terms to Your New Libraries
+
+  If you develop a new library, and you want it to be of the greatest
+possible use to the public, we recommend making it free software that
+everyone can redistribute and change.  You can do so by permitting
+redistribution under these terms (or, alternatively, under the terms of the
+ordinary General Public License).
+
+  To apply these terms, attach the following notices to the library.  It is
+safest to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least the
+"copyright" line and a pointer to where the full notice is found.
+
+    <one line to give the library's name and a brief idea of what it does.>
+    Copyright (C) <year>  <name of author>
+
+    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.
+
+    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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+
+Also add information on how to contact you by electronic and paper mail.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the library, if
+necessary.  Here is a sample; alter the names:
+
+  Yoyodyne, Inc., hereby disclaims all copyright interest in the
+  library `Frob' (a library for tweaking knobs) written by James Random Hacker.
+
+  <signature of Ty Coon>, 1 April 1990
+  Ty Coon, President of Vice
+
+That's all there is to it!
+ALL := lazy_list.cmo lazy_list.cmx pa_llistcomp.cma
+
+CAMLP4DIR := $(shell camlp4 -where)
+LIBDIR    := $(shell dirname `camlp4 -where`)
+
+.PHONY: all doc tests runtests clean
+
+
+all: $(ALL) doc
+
+
+lazy_list.cmo: lazy_list.ml lazy_list.cmi
+	ocamlc -c -pp camlp4o $<
+lazy_list.cmx: lazy_list.ml lazy_list.cmi
+	ocamlopt -c -pp camlp4o $<
+lazy_list.cmi: lazy_list.mli
+	ocamlc -c $<
+
+pa_llistcomp.cma: traverse.cmo patterns.cmo pa_llistcomp.cmo
+	ocamlc -I +camlp4 -a $^ -o $@
+
+pa_llistcomp.cmo: pa_llistcomp.ml patterns.cmo
+	ocamlc -I +camlp4 -pp camlp4orf -I . traverse.cmo patterns.cmo -c $<
+
+patterns.cmo: patterns.ml traverse.cmo
+	ocamlc -I +camlp4 -pp "camlp4of -loc loc" -c $<
+
+traverse.cmo: traverse.ml traverse.cmi
+	ocamlc -I +camlp4 -c $<
+traverse.cmi: traverse.mli
+	ocamlc -I +camlp4 -c $<
+
+
+doc:
+	mkdir -p doc
+	ocamldoc -html -d doc lazy_list.mli
+
+
+tests:
+	@make -C tests
+
+runtests: all tests
+	@make -C tests runtests
+
+
+install:
+	install -m 0644 lazy_list.cm[iox] $(LIBDIR)
+	install -m 0644 pa_llistcomp.cma $(CAMLP4DIR)
+
+uninstall:
+	rm -f $(addprefix $(LIBDIR)/, lazy_list.cm[iox])
+	rm -f $(addprefix $(CAMLP4DIR)/, pa_llistcomp.cma)
+
+
+clean:
+	rm -Rf *~ \#* *.cm[iox] *.o $(ALL)
+	rm -Rf doc
+	@make -C tests clean
+1. Description
+
+This OCaml package provides lazy lists for OCaml. The features are as follows:
+  * lazy lists library
+  * syntax extension with support for
+      - lazy list construction and generation
+      - lazy list comprehension
+      - lazy list pattern matching
+
+Usage examples for original syntax see in examples/llistcons_orig.ml,
+examples/llistcomp_orig.ml; for revised syntax - in examples/llistcons_rev.ml,
+examples/llistcomp_rev.ml.
+
+Documentation for lazy list library see in doc/index.html.
+
+
+2. Installation Instructions
+
+As usual
+  make
+  sudo make install
+
+For compiling and running tests:
+  make tests
+  make runtests
+
+
+3. Usage
+
+Compilation of program test.ml that uses lazy lists:
+  * Original syntax:
+      ocamlc -c -pp "camlp4o pa_llistcomp.cma" test.ml
+  * Revised syntax:
+      ocamlc -c -pp "camlp4r pa_llistcomp.cma" test.ml
+
+And linking:
+  ocamlc lazy_list.cmo test.cmo -o test
+
+Using in toplevel (original syntax):
+
+  #load "camlp4o.cma" ;;
+  #load "pa_llistcomp.cma" ;;
+  #load "lazy_list.cmo" ;;
+
+Using in toplevel (revised syntax):
+
+  #load "camlp4r.cma" ;;
+  #load "pa_llistcomp.cma" ;
+  #load "lazy_list.cmo" ;
+
+
+
+Comments are very welcome.
+
+Vadim Shender
+vadim at shender dot org

examples/llistcomp_orig.ml

+#load "camlp4o.cma"
+#load "pa_llistcomp.cma"
+#load "lazy_list.cmo"
+
+
+open Lazy_list
+
+
+
+(* Examples from "http://www.haskell.org/haskellwiki/List_comprehension". *)
+
+
+(* List comprehension may have multiple generators, separated by semicolons. *)
+let l = [% i, j | i <- [% 1; 2 ]; j <- [% 1 .. 4 ] ]
+in to_list l
+(* - : (int * int) list =
+         [(1, 1); (1, 2); (1, 3); (1, 4); (2, 1); (2, 2); (2, 3); (2, 4)] *)
+
+
+(* Note how each successive generator refines the results of the previous
+   generator. Thus, if the second list is infinite, one will never reach the
+   second element of the first list. *)
+let l = take 10 [% i, j | i <- [% 1; 2 ]; j <- [% 1 .. ] ]
+in to_list l
+(* - : (int * int) list =
+         [(1, 1); (1, 2); (1, 3); (1, 4); (1, 5);
+          (1, 6); (1, 7); (1, 8); (1, 9); (1, 10)] *)
+
+
+(* In such a situation, a nested sequence of list comprehensions may be appropriate.  *)
+let l = take 5 [% to_list [% i, j | i <- [% 1; 2] ] | j <- [% 1 .. ] ]
+in to_list l
+(* - : (int * int) list list =
+         [[(1, 1); (2, 1)]; [(1, 2); (2, 2)]; [(1, 3); (2, 3)];
+          [(1, 4); (2, 4)]; [(1, 5); (2, 5)]] *)
+
+
+(* List comprehension can also provide boolean guards. *)
+let rec gcd a = function
+    0 -> a
+  | b -> gcd b (a mod b)
+in
+let l = take 10 [% i, j | i <- [% 1 .. ]; j <- [% 1 .. i - 1 ]; gcd i j = 1 ]
+in to_list l
+(* - : (int * int) list =
+         [(2, 1); (3, 1); (3, 2); (4, 1); (4, 3);
+          (5, 1); (5, 2); (5, 3); (5, 4); (6, 1)] *)
+
+
+(* Finally, it's possible to make local let declaration. *)
+let l = take 10 [% i, j | i <- [% 1 .. ]; let k = i * i; j <- [% 1 .. k ] ]
+in to_list l
+(* - : (int * int) list =
+         [(1, 1); (2, 1); (2, 2); (2, 3); (2, 4);
+          (3, 1); (3, 2); (3, 3); (3, 4); (3, 5)] *)
+
+
+
+(* Some more examples. *)
+
+let l = [% x, y, z | x <- [% 1 .. 20 ]; y <- [% x .. 20 ];
+                     z <- [% y .. 20 ]; x * x + y * y = z * z]
+in to_list l
+(* - : (int * int * int) list =
+         [(3, 4, 5); (5, 12, 13); (6, 8, 10);
+          (8, 15, 17); (9, 12, 15); (12, 16, 20)] *)
+
+
+let l = [% x | xs <- [% [% 1, 2; 3, 4 ]; [% 5, 4; 3, 2 ] ]; (3, x) <- xs ]
+in to_list l
+(* - : int list = [4; 2] *)
+
+
+let l = take 5 [% i, j, l | i <- [% 1 ..]; let k = i * i; let j = k * k;
+                            i > 2; i < 10; l <- [% 0; 1 ] ]
+in to_list l
+(* - : (int * int * int) list =
+         [(3, 81, 0); (3, 81, 1); (4, 256, 0); (4, 256, 1); (5, 625, 0)] *)
+
+let l = take 5 [% i, j, l | i <- [% 1 ..]; i > 2; i < 10;
+                            let k = i * i; let j = k * k; l <- [% 0; 1 ] ]
+in to_list l
+(* - : (int * int * int) list =
+         [(3, 81, 0); (3, 81, 1); (4, 256, 0); (4, 256, 1); (5, 625, 0)] *)
+
+let l = take 5 [% i, j, l | i <- [% 1 ..]; i > 2; i < 10;
+                            let k = i * i and j = i * i * i * i;
+                            l <- [% 0; 1 ] ]
+in to_list l
+(* Warning Y: unused variable k.
+   - : (int * int * int) list =
+     [(3, 81, 0); (3, 81, 1); (4, 256, 0); (4, 256, 1); (5, 625, 0)] *)
+
+
+let l = take 5 [% i, k | i <- [% 1 ..]; let k = i * i; let j = k * k in i < 10 ]
+in to_list l
+(* Warning Y: unused variable j.
+   - : (int * int) list = [(1, 1); (2, 4); (3, 9); (4, 16); (5, 25)] *)
+
+
+let l = take 5 [% i, l | i <- [% 1 ..]; let (k, l) = i * i, i * i * i;
+                         let z = 1 in k > 1 ]
+in to_list l
+(* Warning Y: unused variable z.
+   - : (int * int) list = [(2, 8); (3, 27); (4, 64); (5, 125); (6, 216)] *)
+
+let l = take 5 [% i, l | i <- [% 1 ..]; let (k, l) = i * i, i * i * i;
+                         l <- [% k .. l ]; let (x, z) = 1, 2 in k > 1 ]
+in to_list l
+(* Warning Y: unused variable z.
+   Warning Y: unused variable x.
+   - : (int * int) list = [(2, 4); (2, 5); (2, 6); (2, 7); (2, 8)] *)
+
+let l = take 5 [% i, l | i <- [% 1 ..]; let (k, l) = i * i, i * i * i;
+                         let (l, k) = 1, 2 in k > 1 ]
+in to_list l
+(* - : (int * int) list = [(1, 1); (2, 8); (3, 27); (4, 64); (5, 125)] *)
+
+let l = take 5 [% i, l | i <- [% 1 ..]; let (k, l) = i * i, i * i * i;
+                         let ([i; l], k) = ([1; 2], 3) in k > 1 ]
+in to_list l
+(* Warning P: this pattern-matching is not exhaustive.
+   Here is an example of a value that is not matched:
+   ([], _)
+   - : (int * int) list = [(1, 1); (2, 8); (3, 27); (4, 64); (5, 125)] *)
+
+
+let primes =
+  let rec sieve = function
+      hd %: tl -> hd %: sieve [% x | x <- tl; x mod hd > 0 ]
+  in 2 %: sieve [% 3; 5 .. ]
+in to_list (take 20 primes)
+(* Warning P: this pattern-matching is not exhaustive.
+   Here is an example of a value that is not matched:
+   Nil
+   - : int list =
+         [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31;
+          37; 41; 43; 47; 53; 59; 61; 67; 71] *)
+
+
+let l = take 5 [% i, fact i | i <- [% 1 .. ];
+                              let rec fact = function 0 -> 1
+                                                    | n -> n * fact (n - 1) ]
+in to_list l
+(* - : (int * int) list = [(1, 1); (2, 2); (3, 6); (4, 24); (5, 120)] *)
+
+let l = take 5 [% i, j | i <- [% 1 .. ];
+                         let rec fact = ( function 0 -> 1 |
+                                                   n -> n * fact (n - 1) );
+                         let j = fact i ]
+in to_list l
+(* - : (int * int) list = [(1, 1); (2, 2); (3, 6); (4, 24); (5, 120)] *)

examples/llistcomp_rev.ml

+#load "camlp4r.cma" ;;
+#load "pa_llistcomp.cma" ;
+#load "lazy_list.cmo" ;
+
+
+open Lazy_list ;
+
+
+
+(* Examples from "http://www.haskell.org/haskellwiki/List_comprehension". *)
+
+
+(* List comprehension may have multiple generators, separated by semicolons. *)
+let l = [% (i, j) | i <- [% 1; 2 ]; j <- [% 1 .. 4 ] ]
+in to_list l ;
+(* - : list (int * int) =
+         [(1, 1); (1, 2); (1, 3); (1, 4); (2, 1); (2, 2); (2, 3); (2, 4)] *)
+
+
+(* Note how each successive generator refines the results of the previous
+   generator. Thus, if the second list is infinite, one will never reach the
+   second element of the first list. *)
+let l = take 10 [% (i, j) | i <- [% 1; 2 ]; j <- [% 1 .. ] ]
+in to_list l ;
+(* - : list (int * int) =
+         [(1, 1); (1, 2); (1, 3); (1, 4); (1, 5);
+          (1, 6); (1, 7); (1, 8); (1, 9); (1, 10)] *)
+
+
+(* In such a situation, a nested sequence of list comprehensions may be appropriate.  *)
+let l = take 5 [% to_list [% (i, j) | i <- [% 1; 2] ] | j <- [% 1 .. ] ]
+in to_list l ;
+(* - : list (list (int * int)) =
+         [[(1, 1); (2, 1)]; [(1, 2); (2, 2)]; [(1, 3); (2, 3)];
+          [(1, 4); (2, 4)]; [(1, 5); (2, 5)]] *)
+
+
+(* List comprehension can also provide boolean guards. *)
+let rec gcd a = fun
+  [ 0 -> a
+  | b -> gcd b (a mod b) ]
+in
+let l = take 10 [% (i, j) | i <- [% 1 .. ]; j <- [% 1 .. i - 1 ]; gcd i j = 1 ]
+in to_list l ;
+(* - : list (int * int) =
+         [(2, 1); (3, 1); (3, 2); (4, 1); (4, 3);
+          (5, 1); (5, 2); (5, 3); (5, 4); (6, 1)] *)
+
+
+(* Finally, it's possible to make local let declaration. *)
+let l = take 10 [% (i, j) | i <- [% 1 .. ]; let k = i * i; j <- [% 1 .. k ] ]
+in to_list l ;
+(* - : list (int * int) =
+         [(1, 1); (2, 1); (2, 2); (2, 3); (2, 4);
+          (3, 1); (3, 2); (3, 3); (3, 4); (3, 5)] *)
+
+
+
+(* Some more examples. *)
+
+let l = [% (x, y, z) | x <- [% 1 .. 20 ]; y <- [% x .. 20 ];
+                       z <- [% y .. 20 ]; x * x + y * y = z * z]
+in to_list l ;
+(* - : list (int * int * int) =
+         [(3, 4, 5); (5, 12, 13); (6, 8, 10);
+          (8, 15, 17); (9, 12, 15); (12, 16, 20)] *)
+
+
+let l = [% x | xs <- [% [% (1, 2); (3, 4) ]; [% (5, 4); (3, 2) ] ];
+               (3, x) <- xs ]
+in to_list l ;
+(* - : list int = [4; 2] *)
+
+
+let l = take 5 [% (i, j, l) | i <- [% 1 ..]; let k = i * i; let j = k * k;
+                              i > 2; i < 10; l <- [% 0; 1 ] ]
+in to_list l ;
+(* - : list (int * int * int) =
+         [(3, 81, 0); (3, 81, 1); (4, 256, 0); (4, 256, 1); (5, 625, 0)] *)
+
+let l = take 5 [% (i, j, l) | i <- [% 1 ..]; i > 2; i < 10;
+                              let k = i * i; let j = k * k; l <- [% 0; 1 ] ]
+in to_list l ;
+(* - : list (int * int * int) =
+         [(3, 81, 0); (3, 81, 1); (4, 256, 0); (4, 256, 1); (5, 625, 0)] *)
+
+let l = take 5 [% (i, j, l) | i <- [% 1 ..]; i > 2; i < 10;
+                              let k = i * i and j = i * i * i * i;
+                              l <- [% 0; 1 ] ]
+in to_list l ;
+(* Warning Y: unused variable k.
+   - : list (int * int * int) =
+     [(3, 81, 0); (3, 81, 1); (4, 256, 0); (4, 256, 1); (5, 625, 0)] *)
+
+
+let l = take 5 [% (i, k) | i <- [% 1 ..];
+                           let k = i * i; let j = k * k in i < 10 ]
+in to_list l ;
+(* Warning Y: unused variable j.
+   - : list (int * int) = [(1, 1); (2, 4); (3, 9); (4, 16); (5, 25)] *)
+
+
+let l = take 5 [% (i, l) | i <- [% 1 ..]; let (k, l) = (i * i, i * i * i);
+                         let z = 1 in k > 1 ]
+in to_list l ;
+(* Warning Y: unused variable z.
+   - : list (int * int) = [(2, 8); (3, 27); (4, 64); (5, 125); (6, 216)] *)
+
+let l = take 5 [% (i, l) | i <- [% 1 ..]; let (k, l) = (i * i, i * i * i);
+                           l <- [% k .. l ]; let (x, z) = (1, 2) in k > 1 ]
+in to_list l ;
+(* Warning Y: unused variable z.
+   Warning Y: unused variable x.
+   - : list (int * int) = [(2, 4); (2, 5); (2, 6); (2, 7); (2, 8)] *)
+
+let l = take 5 [% (i, l) | i <- [% 1 ..]; let (k, l) = (i * i, i * i * i);
+                           let (l, k) = (1, 2) in k > 1 ]
+in to_list l ;
+(* - : list (int * int) = [(1, 1); (2, 8); (3, 27); (4, 64); (5, 125)] *)
+
+
+let primes =
+  let rec sieve = fun
+    [ [% hd :: tl ] -> [% hd :: sieve [% x | x <- tl; x mod hd > 0 ] ] ]
+  in [% 2 :: sieve [% 3; 5 .. ] ]
+in to_list (take 20 primes) ;
+(* Warning P: this pattern-matching is not exhaustive.
+   Here is an example of a value that is not matched:
+   Nil
+   - : list int =
+         [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31;
+          37; 41; 43; 47; 53; 59; 61; 67; 71] *)
+
+
+let l = take 5 [% (i, fact i) | i <- [% 1 .. ];
+                                let rec fact = fun [ 0 -> 1
+                                                   | n -> n * fact (n - 1) ] ]
+in to_list l ;
+(* - : list (int * int) = [(1, 1); (2, 2); (3, 6); (4, 24); (5, 120)] *)
+
+let l = take 5 [% (i, j) | i <- [% 1 .. ];
+                           let rec fact = ( fun [ 0 -> 1
+                                                | n -> n * fact (n - 1) ] );
+                           let j = fact i ]
+in to_list l ;
+(* - : list (int * int) = [(1, 1); (2, 2); (3, 6); (4, 24); (5, 120)] *)

examples/llistcons_orig.ml

+#load "camlp4o.cma"
+#load "pa_llistcomp.cma"
+#load "lazy_list.cmo"
+
+
+open Lazy_list
+
+
+
+let l = [% ]
+in to_list l
+(* - : 'a list = [] *)
+
+let l = [% 1 ]
+in to_list l
+(* - : int list = [1] *)
+
+let l = [% 1; 2; 3; 4; 5 ]
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5] *)
+
+
+let l = [% 1 .. 5 ]
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5] *)
+
+let l = [% 1 .. 5; 7; 9 ]
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5; 7; 9] *)
+
+let l = [% 1 .. 5; 7 .. 9 ]
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5; 7; 8; 9] *)
+
+
+let l = [% 2; 4 .. 9 ]
+in to_list l
+(* - : int list = [2; 4; 6; 8] *)
+
+let l = [% 2; 3; 5 .. 9 ]
+in to_list l
+(* - : int list = [2; 3; 5; 7; 9] *)
+
+let l = [% 3; 5 .. 9; 12 ]
+in to_list l
+(* - : int list = [3; 5; 7; 9; 12] *)
+
+
+let l = [% 2; 3; 5 .. 9; 12 .. 14 ]
+in to_list l
+(* - : int list = [2; 3; 5; 7; 9; 12; 13; 14] *)
+
+let l = [% 2; 3; 5 .. 9; 12; 14 .. 18 ]
+in to_list l
+(* - : int list = [2; 3; 5; 7; 9; 12; 14; 16; 18] *)
+
+
+let l = take 5 [% 1; 3 .. ]
+in to_list l
+(* - : int list = [1; 3; 5; 7; 9] *)
+
+let l = take 5 [% 2; 3; 5 .. ]
+in to_list l
+(* - : int list = [2; 3; 5; 7; 9] *)
+
+let l = take 10 [% 2; 3; 5 .. 9; 11; 14 .. ]
+in to_list l
+(* - : int list = [2; 3; 5; 7; 9; 11; 14; 17; 20; 23] *)
+
+
+let l = 1 %: [% ]
+in to_list l
+(* - : int list = [1] *)
+
+let l = [% ] %: [% ]
+in to_list l
+(* - : 'a Lazy_list.t list = [lazy Nil] *)
+
+let l = 1 %: [% 2; 3; 4; 5 ]
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5] *)
+
+let l = 1 %: 2 %: [% 3; 4; 5 ]
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5] *)
+
+let l = 1 %: 2 %: 3 %: 4 %: [% 5 ]
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5] *)
+
+let l = 1 %: 2 %: [% 3 .. 5 ]
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5] *)
+
+let l = take 5 (1 %: 2 %: [% 3 .. ]) in
+in to_list l
+(* - : int list = [1; 2; 3; 4; 5] *)

examples/llistcons_rev.ml

+#load "camlp4r.cma" ;;
+#load "pa_llistcomp.cma" ;
+#load "lazy_list.cmo" ;
+
+
+open Lazy_list ;
+
+
+
+let l = [% ]
+in to_list l ;
+(* - : list 'a = [] *)
+
+let l = [% 1 ]
+in to_list l ;
+(* - : list int = [1] *)
+
+let l = [% 1; 2; 3; 4; 5 ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+
+
+let l = [% 1 .. 5 ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+
+let l = [% 1 .. 5; 7; 9 ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5; 7; 9] *)
+
+let l = [% 1 .. 5; 7 .. 9 ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5; 7; 8; 9] *)
+
+
+let l = [% 2; 4 .. 9 ]
+in to_list l ;
+(* - : list int = [2; 4; 6; 8] *)
+
+let l = [% 2; 3; 5 .. 9 ]
+in to_list l ;
+(* - : list int = [2; 3; 5; 7; 9] *)
+
+let l = [% 3; 5 .. 9; 12 ]
+in to_list l ;
+(* - : list int = [3; 5; 7; 9; 12] *)
+
+
+let l = [% 2; 3; 5 .. 9; 12 .. 14 ]
+in to_list l ;
+(* - : list int = [2; 3; 5; 7; 9; 12; 13; 14] *)
+
+let l = [% 2; 3; 5 .. 9; 12; 14 .. 18 ]
+in to_list l ;
+(* - : list int = [2; 3; 5; 7; 9; 12; 14; 16; 18] *)
+
+
+let l = take 5 [% 1; 3 .. ]
+in to_list l ;
+(* - : list int = [1; 3; 5; 7; 9] *)
+
+let l = take 5 [% 2; 3; 5 .. ]
+in to_list l ;
+(* - : list int = [2; 3; 5; 7; 9] *)
+
+let l = take 10 [% 2; 3; 5 .. 9; 11; 14 .. ]
+in to_list l ;
+(* - : list int = [2; 3; 5; 7; 9; 11; 14; 17; 20; 23] *)
+
+
+let l = [% 1 :: [% ] ]
+in to_list l ;
+(* - : list int = [1] *)
+
+let l = [% [% ] :: [% ] ]
+in to_list l ;
+(* - : list (Lazy_list.t 'a) = [lazy Nil] *)
+
+let l = [% 1 :: [% 2; 3; 4; 5 ] ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+
+let l = [% 1 :: [% 2 :: [% 3; 4; 5 ] ] ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+
+let l = [% 1; 2 :: [% 3; 4; 5 ] ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+
+let l = [% 1 :: [% 2 :: [% 3 :: [% 4 :: [% 5 ] ] ] ] ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+
+let l = [% 1; 2; 3; 4 :: [% 5 ] ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+
+let l = [% 1; 2 :: [% 3 .. 5 ] ]
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+
+let l = take 5 ([% 1 :: [% 2 :: [% 3 .. ] ] ]) in
+in to_list l ;
+(* - : list int = [1; 2; 3; 4; 5] *)
+(* Lazy list implementation
+ *
+ * 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
+ *)
+
+
+type 'a node_t =
+  Nil
+| Cons of 'a * 'a t
+and  'a t = 'a node_t lazy_t
+
+
+external follow_forward : Obj.t -> 'a = "caml_lazy_follow_forward"
+external make_forward : 'a -> 'a lazy_t = "caml_lazy_make_forward"
+
+
+let lazy_apply f l =
+  lazy (f (Lazy.force l))
+
+
+let fold_left ?limit f init lst =
+  let rec fold_left_inf accu rest =
+    match Lazy.force rest with
+      Nil         -> accu
+    | Cons (h, t) -> fold_left_inf (f accu h) t
+  and     fold_left_fin accu rest = function
+      0 -> accu
+    | n ->
+        match Lazy.force rest with
+          Nil         -> accu
+        | Cons (h, t) -> fold_left_fin (f accu h) t (n - 1)
+
+  in
+  match limit with
+    None   -> fold_left_inf init lst
+  | Some n -> if n >= 0 then fold_left_fin init lst n
+              else           invalid_arg "Lazy_list.fold_left"
+
+let fold_right ?limit f lst init =
+  let rec fold_right_inf rest =
+    match Lazy.force rest with
+      Nil         -> init
+    | Cons (h, t) -> f h (fold_right_inf t)
+  and     fold_right_fin rest = function
+      0 -> init
+    | n ->
+        match Lazy.force rest with
+          Nil         -> init
+        | Cons (h, t) -> f h (fold_right_fin t (n - 1))
+  in
+  match limit with
+    None   -> fold_right_inf lst
+  | Some n -> if n >= 0 then fold_right_fin lst n
+              else           invalid_arg "Lazy_list.fold_right"
+
+
+let empty = lazy Nil
+
+let singleton x = lazy (Cons (x, empty))
+
+
+let cons h t =
+  lazy (Cons (h, t))
+
+
+let init ?limit ?(starti=0) f =
+  let rec init_inf i =
+    lazy (Cons (f i, init_inf (i + 1)) )
+  and     init_fin i n =
+    lazy ( if n = 0 then Nil
+           else          Cons (f i, init_fin (i + 1) (n - 1)) )
+  in
+  match limit with
+    None   -> init_inf starti
+  | Some n -> if n >= 0 then init_fin starti n else invalid_arg "Lazy_list.init"
+
+let make ?limit x =
+  let rec make_inf () =
+    lazy (Cons (x, make_inf ()))
+  and     make_fin n =
+    lazy ( if n = 0 then Nil
+           else          Cons (x, make_fin (n - 1)) )
+  in
+  match limit with
+    None   -> make_inf ()
+  | Some n -> if n >= 0 then make_fin n else invalid_arg "Lazy_list.make"
+
+let interval ?(step=1) a b =
+  let cmp = if step > 0 then ( > ) else ( < ) in
+  let rec interval' a =
+    lazy ( if cmp a b then Nil
+           else       Cons (a, interval' (a + step)) )
+  in interval' a
+
+let rec interval_inf ?(step=1) a =
+  lazy ( Cons (a, interval_inf (a + step) ~step:step) )
+
+
+let length ?limit lst =
+  fold_left ?limit (fun n _ -> n + 1) 0 lst
+
+
+let hd lst =
+  match Lazy.force lst with
+    Nil         -> failwith "Lazy_list.hd"
+  | Cons (h, t) -> h
+
+let tl lst =
+  match Lazy.force lst with
+    Nil         -> failwith "Lazy_list.tl"
+  | Cons (h, t) -> t
+
+let nth lst n =
+  let rec loop rest n =
+    match Lazy.force rest with
+      Nil         -> failwith "Lazy_list.nth"
+    | Cons (h, t) ->
+        if n = 0 then h
+        else          loop t (n - 1)
+  in if n >= 0 then loop lst n else invalid_arg "Lazy_list.nth"
+
+
+let rec append lst1 lst2 =
+  let append' = function
+      Nil         -> Lazy.force lst2
+    | Cons (h, t) -> Cons (h, append t lst2)
+  in lazy_apply append' lst1
+
+let concat lstlst =
+  let rec concat_aux lst1 llrest =
+    let concat' llrest = function
+        Nil         ->
+          ( match Lazy.force llrest with
+              Nil                    -> Nil
+            | Cons (lstnext, llrest) -> Lazy.force (concat_aux lstnext llrest) )
+      | Cons (h, t) -> Cons (h, concat_aux t llrest)
+    in lazy_apply (concat' llrest) lst1
+  in
+  match Lazy.force lstlst with
+    Nil         -> empty
+  | Cons (h, t) -> concat_aux h t
+
+let flatten = concat
+
+
+let iter ?limit f lst =
+  let rec iter_inf lst =
+    match Lazy.force lst with
+      Nil         -> ()
+    | Cons (h, t) -> let () = f h in iter_inf t
+  and     iter_fin lst = function
+      0 -> ()
+    | n ->
+        match Lazy.force lst with
+          Nil         -> ()
+        | Cons (h, t) -> let () = f h in iter_fin t (n - 1)
+  in
+  match limit with
+    None   -> iter_inf lst
+  | Some n -> if n >= 0 then iter_fin lst n else invalid_arg "Lazy_list.iter"
+
+let iteri ?limit ?(starti=0) f lst =
+  let rec iteri_inf lst i =
+    match Lazy.force lst with
+      Nil         -> ()
+    | Cons (h, t) -> let () = f i h in iteri_inf t (i + 1)
+  and     iteri_fin lst i = function
+      0 -> ()
+    | n ->
+        match Lazy.force lst with
+          Nil         -> ()
+        | Cons (h, t) -> let () = f i h in iteri_fin t (i + 1) (n - 1)
+  in
+  match limit with
+    None   -> iteri_inf lst starti
+  | Some n -> if n >= 0 then iteri_fin lst starti n
+              else           invalid_arg "Lazy_list.iteri"
+
+let rec map f lst =
+  let map' = function
+      Nil         -> Nil
+    | Cons (h, t) -> Cons (f h, map f t)
+  in lazy_apply map' lst
+
+let rec mapi ?(starti=0) f lst =
+  let mapi' i = function
+      Nil         -> Nil
+    | Cons (h, t) -> Cons (f i h, mapi ~starti:(i + 1) f t)
+  in lazy_apply (mapi' starti) lst
+
+
+let iter2 ?limit f lst1 lst2 =
+  let rec iter2_inf lst1 lst2 =
+    match Lazy.force lst1, Lazy.force lst2 with
+      Nil, Nil                     -> ()
+    | Cons (h1, t1), Cons (h2, t2) -> let () = f h1 h2 in iter2_inf t1 t2
+    | _                            -> invalid_arg "Lazy_list.iter2"
+  and     iter2_fin lst1 lst2 = function
+      0 -> ()
+    | n ->
+        match Lazy.force lst1, Lazy.force lst2 with
+          Nil, Nil                     -> ()
+        | Cons (h1, t1), Cons (h2, t2) -> let () = f h1 h2 in iter2_fin t1 t2 (n - 1)
+        | _                            -> invalid_arg "Lazy_list.iter2"
+  in
+  match limit with
+    None   -> iter2_inf lst1 lst2
+  | Some n -> if n >= 0 then iter2_fin lst1 lst2 n else invalid_arg "Lazy_list.iter2"
+
+let iteri2 ?limit ?(starti=0) f lst1 lst2 =
+  let rec iteri2_inf lst1 lst2 i =
+    match Lazy.force lst1, Lazy.force lst2 with
+      Nil, Nil                     -> ()
+    | Cons (h1, t1), Cons (h2, t2) -> let () = f i h1 h2 in iteri2_inf t1 t2 (i + 1)
+    | _                            -> invalid_arg "Lazy_list.iteri2"
+  and     iteri2_fin lst1 lst2 i = function
+      0 -> ()
+    | n ->
+        match Lazy.force lst1, Lazy.force lst2 with
+          Nil, Nil                     -> ()
+        | Cons (h1, t1), Cons (h2, t2) -> let () = f i h1 h2 in iteri2_fin t1 t2 (i + 1) (n - 1)
+        | _                            -> invalid_arg "Lazy_list.iteri2"
+  in
+  match limit with
+    None   -> iteri2_inf lst1 lst2 starti
+  | Some n -> if n >= 0 then iteri2_fin lst1 lst2 starti n
+              else           invalid_arg "Lazy_list.iteri2"
+
+let rec map2 f lst1 lst2 =
+  let map2' lst1_unwrapped =
+    match lst1_unwrapped, Lazy.force lst2 with
+      Nil, Nil                     -> Nil
+    | Cons (h1, t1), Cons (h2, t2) -> Cons (f h1 h2, map2 f t1 t2)
+    | _                            -> invalid_arg "Lazy_list.map2"
+  in lazy_apply map2' lst1
+
+let rec mapi2 ?(starti=0) f lst1 lst2 =
+  let mapi2' i lst1_unwrapped =
+    match lst1_unwrapped, Lazy.force lst2 with
+      Nil, Nil                     -> Nil
+    | Cons (h1, t1), Cons (h2, t2) -> Cons (f i h1 h2, mapi2 ~starti:(i + 1) f t1 t2)
+    | _                            -> invalid_arg "Lazy_list.mapi2"
+  in lazy_apply (mapi2' starti) lst1
+
+let fold_left2 ?limit f init lst1 lst2 =
+  let rec fold_left2_inf accu lst1 lst2 =
+    match Lazy.force lst1, Lazy.force lst2 with
+      Nil, Nil                     -> accu
+    | Cons (h1, t1), Cons (h2, t2) -> fold_left2_inf (f accu h1 h2) t1 t2
+    | _                            -> invalid_arg "Lazy_list.fold_left2"
+  and     fold_left2_fin accu lst1 lst2 = function
+      0 -> accu
+    | n ->
+        match Lazy.force lst1, Lazy.force lst2 with
+          Nil, Nil                     -> accu
+        | Cons (h1, t1), Cons (h2, t2) -> fold_left2_fin (f accu h1 h2) t1 t2 (n - 1)
+        | _                            -> invalid_arg "Lazy_list.fold_left2"
+  in
+  match limit with
+    None   -> fold_left2_inf init lst1 lst2
+  | Some n -> if n >= 0 then fold_left2_fin init lst1 lst2 n
+              else           invalid_arg "Lazy_list.fold_left2"
+
+let rec fold_right2 ?limit f lst1 lst2 init =
+  let rec fold_right2_inf lst1 lst2 =
+    match Lazy.force lst1, Lazy.force lst2 with
+      Nil, Nil                     -> init
+    | Cons (h1, t1), Cons (h2, t2) -> f h1 h2 (fold_right2_inf t1 t2)
+    | _                            -> invalid_arg "Lazy_list.fold_right2"
+  and     fold_right2_fin lst1 lst2 = function
+      0 -> init
+    | n ->
+        match Lazy.force lst1, Lazy.force lst2 with
+          Nil, Nil                     -> init
+        | Cons (h1, t1), Cons (h2, t2) -> f h1 h2 (fold_right2_fin t1 t2 (n - 1))
+        | _                            -> invalid_arg "Lazy_list.fold_right2"
+  in
+  match limit with
+    None   -> fold_right2_inf lst1 lst2
+  | Some n -> if n >= 0 then fold_right2_fin lst1 lst2 n
+              else           invalid_arg "Lazy_list.fold_right2"
+
+
+let for_all ?limit p lst =
+  let rec for_all_inf lst =
+    match Lazy.force lst with
+      Nil         -> true
+    | Cons (h, t) -> p h && for_all_inf t
+  and     for_all_fin lst = function
+      0 -> true
+    | n ->
+        match Lazy.force lst with
+          Nil         -> true
+        | Cons (h, t) -> p h && for_all_fin t (n - 1)
+  in
+  match limit with
+    None   -> for_all_inf lst
+  | Some n -> if n >= 0 then for_all_fin lst n else invalid_arg "Lazy_list.for_all"
+
+let exists ?limit p lst =
+  let rec exists_inf lst =
+    match Lazy.force lst with
+      Nil         -> false
+    | Cons (h, t) -> p h || exists_inf t
+  and     exists_fin lst = function
+      0 -> false
+    | n ->
+        match Lazy.force lst with
+          Nil         -> false
+        | Cons (h, t) -> p h || exists_fin t (n - 1)
+  in
+  match limit with
+    None   -> exists_inf lst
+  | Some n -> if n >= 0 then exists_fin lst n else invalid_arg "Lazy_list.exists"
+
+let for_all2 ?limit p lst1 lst2 =
+  let rec for_all2_inf lst1 lst2 =
+    match Lazy.force lst1, Lazy.force lst2 with
+      Nil, Nil                     -> true
+    | Cons (h1, t1), Cons (h2, t2) -> p h1 h2 && for_all2_inf t1 t2
+    | _                            -> invalid_arg "Lazy_list.for_all2"
+  and     for_all2_fin lst1 lst2 = function
+      0 -> true
+    | n ->
+        match Lazy.force lst1, Lazy.force lst2 with
+          Nil, Nil                     -> true
+        | Cons (h1, t1), Cons (h2, t2) -> p h1 h2 && for_all2_fin t1 t2 (n - 1)
+        | _                            -> invalid_arg "Lazy_list.for_all2"
+  in
+  match limit with
+    None   -> for_all2_inf lst1 lst2
+  | Some n -> if n >= 0 then for_all2_fin lst1 lst2 n
+              else           invalid_arg "Lazy_list.for_all2"
+
+let exists2 ?limit p lst1 lst2 =
+  let rec exists2_inf lst1 lst2 =
+    match Lazy.force lst1, Lazy.force lst2 with
+      Nil, Nil                     -> false
+    | Cons (h1, t1), Cons (h2, t2) -> p h1 h2 || exists2_inf t1 t2
+    | _                            -> invalid_arg "Lazy_list.exists2"
+  and     exists2_fin lst1 lst2 = function
+      0 -> false
+    | n ->
+        match Lazy.force lst1, Lazy.force lst2 with
+          Nil, Nil                     -> false
+        | Cons (h1, t1), Cons (h2, t2) -> p h1 h2 || exists2_fin t1 t2 (n - 1)
+        | _                            -> invalid_arg "Lazy_list.exists2"
+  in
+  match limit with
+    None   -> exists2_inf lst1 lst2
+  | Some n -> if n >= 0 then exists2_fin lst1 lst2 n
+              else           invalid_arg "Lazy_list.exists2"
+
+let mem ?limit x lst =
+  try exists ?limit ((=) x) lst with
+    Invalid_argument _ -> invalid_arg "Lazy_list.mem"
+
+let memq ?limit x lst =
+  try exists ?limit ((==) x) lst with
+    Invalid_argument _ -> invalid_arg "Lazy_list.memq"
+
+
+let find ?limit p lst =
+  let rec find_inf lst =
+    match Lazy.force lst with
+      Nil         -> raise Not_found
+    | Cons (h, t) -> if p h then h else find_inf t
+  and     find_fin lst = function
+      0 -> raise Not_found
+    | n ->
+        match Lazy.force lst with
+          Nil         -> raise Not_found
+        | Cons (h, t) -> if p h then h else find_fin t (n - 1)
+  in
+  match limit with
+    None   -> find_inf lst
+  | Some n -> if n >= 0 then find_fin lst n else invalid_arg "Lazy_list.find"
+
+let findi ?limit ?(starti=0) p lst =
+  let rec findi_inf lst i =
+    match Lazy.force lst with
+      Nil         -> raise Not_found
+    | Cons (h, t) -> if p i h then i, h else findi_inf t (i + 1)
+  and     findi_fin lst i = function
+      0 -> raise Not_found
+    | n ->
+        match Lazy.force lst with
+          Nil         -> raise Not_found
+        | Cons (h, t) -> if p i h then i, h else findi_fin t (i + 1) (n - 1)
+  in
+  match limit with
+    None   -> findi_inf lst starti
+  | Some n -> if n >= 0 then findi_fin lst starti n
+              else           invalid_arg "Lazy_list.findi"
+
+let rec find_all p lst =
+  let rec find_all' = function
+      Nil                  -> Nil
+    | Cons (h, t) when p h -> Cons (h, find_all p t)
+    | Cons (_, t)          -> find_all' (Lazy.force t)
+  in lazy_apply find_all' lst
+
+let filter = find_all
+
+let partition p lst =
+  find_all p lst, find_all (fun x -> not (p x)) lst
+
+
+let split lst =
+  let rec fst lst =
+    let fst' = function 
+        Nil              -> Nil
+      | Cons ((h, _), t) -> Cons (h, fst t)
+    in lazy_apply fst' lst
+  and     snd lst =
+    let snd' = function
+        Nil              -> Nil
+      | Cons ((_, h), t) -> Cons (h, snd t)
+    in lazy_apply snd' lst
+  in fst lst, snd lst
+
+let rec combine lst1 lst2 =
+  let combine' lst1_unwrapped =
+    match lst1_unwrapped, Lazy.force lst2 with
+      Nil, Nil                     -> Nil
+    | Cons (h1, t1), Cons (h2, t2) -> Cons ((h1, h2), combine t1 t2)
+    | _                            -> invalid_arg "Lazy_list.combine"
+  in lazy_apply combine' lst1
+            
+        
+let split_nth n lst =
+  let rec take n lst =
+    let take' = function
+        Nil         -> invalid_arg "Lazy_list.split_nth"
+      | Cons (h, t) -> Cons (h, take (n - 1) t)
+    in if n = 0 then empty else lazy_apply take' lst
+  and     drop n lst =
+    let drop' = function
+        Nil         -> invalid_arg "Lazy_list.split_nth"
+      | Cons (_, t) -> Lazy.force (drop (n - 1) t)
+    in if n = 0 then lst else lazy_apply drop' lst
+  in
+  if n >= 0 then take n lst, drop n lst else invalid_arg "Lazy_list.split_nth"
+
+let rec take n lst =
+  let take' = function
+      Nil         -> Nil
+    | Cons (h, t) -> Cons (h, take (n - 1) t)
+  in if n > 0 then lazy_apply take' lst else empty
+
+let rec drop n lst =
+  let drop' = function
+      Nil         -> Nil
+    | Cons (_, t) -> Lazy.force (drop (n - 1) t)
+  in if n > 0 then lazy_apply drop' lst else lst
+
+let rec takewhile p lst =
+  let takewhile' = function
+      Nil         -> Nil
+    | Cons (h, t) -> if p h then Cons (h, takewhile p t) else Nil
+  in lazy_apply takewhile' lst
+
+let rec dropwhile p lst =
+  let dropwhile' = function
+      Nil              -> Nil
+    | Cons (h, t) as c -> if p h then Lazy.force (dropwhile p t) else c
+  in lazy_apply dropwhile' lst
+
+
+let rec of_list lst = 
+  lazy ( match lst with
+           []     -> Nil
+         | h :: t -> Cons (h, of_list t) )
+
+let to_list ?limit lst =
+  try fold_right ?limit (fun x l -> x :: l) lst [] with
+    Invalid_argument "Lazy_list.fold_right" -> invalid_arg "Lazy_list.to_list"
+
+
+let rec of_stream str =
+  lazy ( try let x = Stream.next str in Cons (x, of_stream str) with
+           Stream.Failure -> Nil )
+
+let rec to_stream lst =
+  [< 'hd lst; to_stream (tl lst) >]
+
+
+let rec of_channel ic =
+  lazy ( try let x = input_byte ic in Cons (x, of_channel ic) with
+           End_of_file -> Nil )
+
+let to_channel ?limit lst oc =
+  try iter ?limit (fun x -> output_byte oc x) lst with
+    Invalid_argument "Lazy_list.iter" -> invalid_arg "Lazy_list.to_channel"
+(* 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.
+
+ 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]. *)
+(* Lazy list comprehension syntax extension
+ *
+ * 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
+ *)
+
+
+open Camlp4.PreCast
+open Syntax
+
+
+let fresh_typevar =
+  let cnt = ref 0 in
+  function _loc ->
+    incr cnt ; <:ctyp< '$lid:"llistcomp_typevar_" ^ (string_of_int !cnt)$ >>
+
+
+(* lookahead grammar entries for lazy list comprehension items distinction *)
+
+let rec loop n = function
+    []     -> None
+  | [x, _] -> if n = 1 then Some x else None
+  | _ :: l -> loop (n - 1) l
+
+let stream_peek_nth n strm = loop n (Stream.npeek n strm)
+
+let test_patt_lessminus =
+  Gram.Entry.of_parser "test_patt_lessminus"
+    ( function strm ->
+        let rec skip_patt n =
+          match stream_peek_nth n strm with
+            Some (KEYWORD "<-")         -> n
+          | Some (KEYWORD ("[" | "[<")) ->
+              skip_patt (ignore_upto "]" (n + 1) + 1)
+          | Some (KEYWORD "(")          ->
+              skip_patt (ignore_upto ")" (n + 1) + 1)
+          | Some (KEYWORD "{")          ->
+              skip_patt (ignore_upto "}" (n + 1) + 1)
+          | Some (KEYWORD ("as" | "::" | "," | "_"))
+          | Some (LIDENT _ | UIDENT _)  -> skip_patt (n + 1)
+          | Some _ | None               -> raise Stream.Failure
+        and     ignore_upto end_kwd n =
+          match stream_peek_nth n strm with
+            Some (KEYWORD prm) when prm = end_kwd -> n
+          | Some (KEYWORD ("[" | "[<"))           ->
+              ignore_upto end_kwd (ignore_upto "]" (n + 1) + 1)
+          | Some (KEYWORD "(")                    ->
+              ignore_upto end_kwd (ignore_upto ")" (n + 1) + 1)
+          | Some (KEYWORD "{")                    ->
+              ignore_upto end_kwd (ignore_upto "}" (n + 1) + 1)
+          | Some _                                -> ignore_upto end_kwd (n + 1)
+          | None                                  -> raise Stream.Failure
+        in skip_patt 1 )
+
+let test_patt_let_without_in =
+  Gram.Entry.of_parser "test_patt_let_without_in"
+    ( function strm ->
+        let rec skip_patt n =
+          match stream_peek_nth n strm with
+            Some (KEYWORD "let") ->
+              skip_patt (ignore_upto "in" (n + 1) + 1)
+          | Some (KEYWORD ("[" | "[<")) ->
+              skip_patt (ignore_upto "]" (n + 1) + 1)
+          | Some (KEYWORD "(")          ->
+              skip_patt (ignore_upto ")" (n + 1) + 1)
+          | Some (KEYWORD "{")          ->
+              skip_patt (ignore_upto "}" (n + 1) + 1)
+          | Some (KEYWORD ("in")) -> raise Stream.Failure
+          | Some (KEYWORD ("]" | ";" | "|")) | None -> n
+          | Some _ -> skip_patt (n + 1)
+        and     ignore_upto end_kwd n =
+          match stream_peek_nth n strm with
+            Some (KEYWORD prm) when prm = end_kwd -> n
+          | Some (KEYWORD "let") ->
+              ignore_upto end_kwd (ignore_upto "in" (n + 1) + 1)
+          | Some (KEYWORD ("[" | "[<"))           ->
+              ignore_upto end_kwd (ignore_upto "]" (n + 1) + 1)
+          | Some (KEYWORD "(")                    ->
+              ignore_upto end_kwd (ignore_upto ")" (n + 1) + 1)
+          | Some (KEYWORD "{")                    ->
+              ignore_upto end_kwd (ignore_upto "}" (n + 1) + 1)
+          | Some _                                -> ignore_upto end_kwd (n + 1)
+          | None                                  -> raise Stream.Failure
+        in
+        match stream_peek_nth 1 strm with
+          Some (KEYWORD "let") -> skip_patt 2
+        | _                    -> raise Stream.Failure )
+
+
+(* generation of list comprehension expansion *)
+
+module S = Set.Make (String)
+
+let vars_of_patt =
+  let fold_vars_of_patt =
+    object (self)
+      inherit Ast.fold as super
+
+      val vars = S.empty
+
+      method vars = vars
+      method patt = function
+          <:patt< $lid:s$ >> | <:patt< ~ $lid:s$ >> | <:patt< ? $s$ >> ->
+            {< vars = S.add s vars >}
+        | p -> super#patt p
+    end
+  in function p -> (fold_vars_of_patt#patt p)#vars
+
+let rec binding_vars_of_binding = function
+    <:binding< $p$ = $e$ and $rest$ >> ->
+      S.union (vars_of_patt p) (binding_vars_of_binding rest)
+  | <:binding< $p$ = $e$ >>            ->
+      vars_of_patt p
+  | _                                  ->
+      failwith "[bound_vars_of_let] impossible case"
+
+let free_vars_of_expr =
+  let fold_free_vars_of_expr =
+    object (self)
+      inherit Ast.fold as super
+
+      val env  = S.empty
+      val free = S.empty
+
+      method free = free
+      method set_env env    = {< env = env >}
+      method add_atom s     = {< env = S.add s env >}
+      method add_binding bi = {< env = binding_vars_of_binding bi >}
+      method add_patt p     = {< env = vars_of_patt p >}
+
+      method expr = function
+          <:expr< $lid:s$ >> | <:expr< ~ $s$ >> | <:expr< ? $s$ >> ->
+            if S.mem s env then self else {< free = S.add s free >}
+        | <:expr< let $bi$ in $e$ >> ->
+            ((((self#add_binding bi)#expr e)#set_env env)#binding bi)#set_env env
+        | <:expr< let rec $bi$ in $e$ >> ->
+            (((self#add_binding bi)#expr e)#binding bi)#set_env env
+        | <:expr< for $s$ = $e1$ $to:_$ $e2$ do { $e3$ } >> ->
+            ((((self#expr e1)#expr e2)#add_atom s)#expr e3)#set_env env
+        | e -> super#expr e
+
+      method match_case = function
+          <:match_case< $p$ when $w$ -> $e$ >> ->
+            (((self#add_patt p)#expr w)#expr e)#set_env env
+        | mc -> super#match_case mc
+    end
+  in
+  function e -> (fold_free_vars_of_expr#expr e)#free
+
+let does_binding_bind_free_vars_of_expr bi e =