janestreet / base Goto Github PK

View Code? Open in Web Editor NEW

826.0 826.0 116.0 4.58 MB

Standard library for OCaml

License: MIT License

Makefile 0.01% OCaml 99.04% C 0.52% JavaScript 0.32% Standard ML 0.10%

base's People

Contributors

Stargazers

Watchers

Forkers

omerzach stevejb71 chris00 lairez pveber seveneng gamobink louischang bcc32 allsea9 shepard8 paurkedal rleonid andrewray martinklepsch swuecho rizo leviroth brendanlong mbouaziz percontation hhugo kmeht xvilka acatton toots sparverius dra27 martindeegan nikolas mattaudesse stjordanis ahiaao khady rvantonder quartz55 renesugar zenhack geophagus96 octachron gitoleg kit-ty-kate jonludlam rbjorklin samoht dune-universe ytrellu iamminster pirapira bogdan2412 picdc lizxiuan jfeser thelortex michaellee4 sangwoo-joh maxgold sebvera maturanamateo dakotamurphyucf diaozheng999 sai-avula samwgoldman matthew-ho idkjs pewulfman qntskd benjub mbacarella kdwss patricoferris siddharthbharthulwar jonahbeckford eduardorfs greedy gfngfn justinlubin jane-street-immersion-program tov doytsujin corwin-of-amber leifmetcalf owini goodship1 mheiber ngernest pantheralgotrading mbarbin 3rafal lsr614 gj9280 ocaml-wasm allmybasebelongtous alizter ayandarobesaz pantea110 joserele lf32 sama1mansn mehdi2sama

base's Issues

Does not compile with OCaml 4.08.0

Error log:

#=== ERROR while compiling base.v0.11.1 =======================================#
# context     2.0.0 | macos/x86_64 | ocaml-variants.4.08.0 | pinned(git+file:///Users/toots/sources/ocaml/base#master#c8f6acfc)
# path        ~/.opam/4.08.0/.opam-switch/build/base.v0.11.1
# command     ~/.opam/opam-init/hooks/sandbox.sh build dune build -p base -j 4
# exit-code   1
# env-file    ~/.opam/log/base-43030-d0f245.env
# output-file ~/.opam/log/base-43030-d0f245.out
### output ###
# [...]
# File "src/or_error.ml", line 15, characters 13-31:
# 15 |   fun arg -> Result.hash_fold_t _hash_fold_a Error.hash_fold_t hsv arg
#                   ^^^^^^^^^^^^^^^^^^
# Alert deprecated: module Base__.Import.Result
# [2016-09] this element comes from the stdlib distributed with OCaml.
# Referring to the stdlib directly is discouraged by Base. You should either
# use the equivalent functionality offered by Base, or if you really want to
# refer to the stdlib, use Caml.Result instead
# File "src/or_error.ml", line 15, characters 13-31:
# 15 |   fun arg -> Result.hash_fold_t _hash_fold_a Error.hash_fold_t hsv arg
#                   ^^^^^^^^^^^^^^^^^^
# Error: Unbound value Result.hash_fold_t

base does not currently compile under Windows

Due to the use of some gcc-isms:

exn_stubs.c, uses __attribute((unused))
int_math_stubs.c, uses __builtin_popcount.

usability issue with `Continue_or_stop` and `Finished_or_stopped`

Data constructors defined in these modules are not re-exported anywhere (at least I didn't find it), so any usage requires full-qualification including the Container_intf module, e.g.,

 match f acc a with
   | Container_intf.Continue_or_stop.Stop x -> Container_intf.Finished_or_stopped_early.Stopped_early x

First of all it is too verbose. Second the Container_intf as well as other *_intf modules are usually seen as internal modules in Core libraries, and it is the first time in my life, when I'm forced to reference them directly in the user code. Next, it is expected, that the *_intf module defines types and signatures, not data types. Finally, even without the this Container_intf name, an expression Continue_or_stop.Stop looks weird and still too verbose and doesn't contribute to the code understanding. Something like Action.Step, Search.Stop, Traverse.Stopped_early, or even just Stop or a polymorphic variant would be more readable. (Concerning the polymorphic variant, I don't see any reason for not using it here).

runtime.js is not installed

cc @hhugo
I think the idea is that src/runtime.js should end up in (e.g.) ~/.opam/system/lib/base/runtime.js

Same goes for core_kernel and bin_prot, but I won't open those issues separately for now.

Moving Arg and Doubly_linked from Core_kernel to Base?

To my understanding, Base is the minimal JS-compatible standard library and Core_kernel is the more featureful one. I previously used Base for a project, but just switched to Core_kernel because I specifically needed the doubly linked list.

IMO a lot of the modules in Core_kernel aren't essential, but a doubly-linked list is generally something that a standard library should have. I think that Doubly_linked deserves to be in Base.

Also, I don't see why Arg needs to be in Core_kernel, because since it is in the original standard library, it shouldn't add any code size overhead.

Incorrect docs in Map.find

The docs for Map.find say:

Returns the value bound to the given key, raising Caml.Not_found of Not_found_s if none exists.

However, the docstring for Map.find says:

(** Returns [Some value] bound to the given key, or [None] if none exists. *)

which matches what it looks like the code does, and the natural expression of find.

So it seems that the doc generator is pulling the comment for Map.find_exn instead of Map.find.

Transparency?

I'm definitely willing to entertain the notion of switching to Base for the sake of unity around a common stdlib/build tool. We're wasting precious resources splitting our efforts and bridging over impedance mismatches.

Given your willingness to work on streamlining the requirements and reducing compilation time, are you also going to make development more transparent and be more open to the community, including the decision process concerning community contributions?

Use Array.create instead of Array.init in hashtable resizing

diff --git src/hashtbl.ml src/hashtbl.ml
index 1c18784..b0371c8 100644
--- src/hashtbl.ml
+++ src/hashtbl.ml
@@ -102,7 +102,7 @@ let maybe_resize_table t =
     let new_array_length = Int.min (len * 2) max_table_length in
     if new_array_length > len then begin
       let new_table =
-        Array.init new_array_length ~f:(fun _ -> Avltree.empty)
+        Array.create new_array_length Avltree.empty
       in
       let old_table = t.table in
       t.table <- new_table;

document Identifiable module

Documentation for Identifiable includes only the uninformative comment "a signature for identifier types". I see that the signature combines a handful of useful functions and this signature is included in various other modules. However, the name Identifiable suggests some more specific property that this module provides. What?

Adding a Seq type to Base?

I've just rewritten my compiler to use Base, instead of my own standard library, and the only major missing thing was something equivalent to seq. Would it be at all possible to add something like this to Base? I'd be willing to write up an implementation, I'm just curious if anybody else wants this.

Here's where I would use it.

4.07 support

Currently, on 4.07.0+beta2+flambda:

jbuilder build @install
      ocamlc src/.base.objs/base__Formatter.{cmi,cmti} (exit 2)
(cd _build/default && /media/samsung/opam2/4.07.0+beta2+flambda/bin/ocamlc.opt -w -40 -g -bin-annot -I src/.base.objs -I /media/samsung/opam2/4.07.0+beta2+flambda/lib/sexplib0 -I compiler-stdlib/src/.caml.objs -I shadow-stdlib/src/.shadow_stdlib.objs -no-alias-deps -open Base__ -o src/.base.objs/base__Formatter.cmi -c -intf src/formatter.mli)
File "src/formatter.mli", line 9, characters 9-30:
Error: Unbound module Caml.Format
      ocamlc src/.base.objs/base__Import0.{cmi,cmo,cmt} (exit 2)
(cd _build/default && /media/samsung/opam2/4.07.0+beta2+flambda/bin/ocamlc.opt -w -40 -g -bin-annot -I src/.base.objs -I /media/samsung/opam2/4.07.0+beta2+flambda/lib/sexplib0 -I compiler-stdlib/src/.caml.objs -I shadow-stdlib/src/.shadow_stdlib.objs -no-alias-deps -open Base__ -o src/.base.objs/base__Import0.cmo -c -impl src/import0.ml)
File "src/import0.ml", line 7, characters 6-394:
Error: The signature constrained by `with' has no component named Pervasives

since 0.11.1 won't compile, I tried 0.11.0 which does not compile

Since 0.11.1 won't compile, I tried 0.11.0.

base-0.11.0 # jbuilder build
ocamlc src/.base.objs/base__Formatter.{cmi,cmti} (exit 2)
(cd build/default && /usr/bin/ocamlc.opt -w -40 -safe-string -g -bin-annot -I src/.base.objs -I /usr/lib64/ocaml/site-lib/sexplib0 -I compiler-stdlib/src/.caml.objs -I shadow-stdlib/src/.shadow_stdlib.objs -no-alias-deps -open Base_ -o src/.base.objs/base__Formatter.cmi -c -intf src/formatter.mli)
File "src/formatter.mli", line 9, characters 9-30:
Error: Unbound module Caml.Format
ocamlc src/.base.objs/base__Import0.{cmi,cmo,cmt} (exit 2)
(cd build/default && /usr/bin/ocamlc.opt -w -40 -safe-string -g -bin-annot -I src/.base.objs -I /usr/lib64/ocaml/site-lib/sexplib0 -I compiler-stdlib/src/.caml.objs -I shadow-stdlib/src/.shadow_stdlib.objs -no-alias-deps -open Base_ -o src/.base.objs/base__Import0.cmo -c -impl src/import0.ml)
File "src/import0.ml", line 7, characters 6-394:
Error: The signature constrained by with' has no component named Pervasives base-0.11.0 # dune build ocamlc src/.base.objs/base__Import0.{cmi,cmo,cmt} (exit 2) (cd _build/default && /usr/bin/ocamlc.opt -w @a-4-29-40-41-42-44-45-48-58-59-60-40 -strict-sequence -strict-formats -short-paths -keep-locs -safe-string -g -bin-annot -I src/.base.objs -I /usr/lib64/ocaml/site-lib/sexplib0 -I compiler-stdlib/src/.caml.objs -I shadow-stdlib/src/.shadow_stdlib.objs -no-alias-deps -open Base__ -o src/.base.objs/base__Import0.cmo -c -impl src/import0.ml) File "src/import0.ml", line 7, characters 6-394: Error: The signature constrained by with' has no component named Pervasives
ocamlc src/.base.objs/base__Formatter.{cmi,cmti} (exit 2)
(cd build/default && /usr/bin/ocamlc.opt -w @a-4-29-40-41-42-44-45-48-58-59-60-40 -strict-sequence -strict-formats -short-paths -keep-locs -safe-string -g -bin-annot -I src/.base.objs -I /usr/lib64/ocaml/site-lib/sexplib0 -I compiler-stdlib/src/.caml.objs -I shadow-stdlib/src/.shadow_stdlib.objs -no-alias-deps -open Base_ -o src/.base.objs/base__Formatter.cmi -c -intf src/formatter.mli)
File "src/formatter.mli", line 9, characters 9-30:
Error: Unbound module Caml.Format

Cannot compile with 4.04

# /home/vb/.opam/4.04.0/bin/ocaml build/gen_rules.ml > build/Makefile.rules
# >> Fatal error: OCaml and preprocessor have incompatible versions
# Fatal error: exception Misc.Fatal_error
# make -f build/Makefile.step2

`Sexpable` and Polymorphic Variants

I have a Sexpable module containing a polymorphic variant type.
The signature I define looks like:

module type I =
  sig
    type t = [ `Foo ]

    include Base.Sexpable.S with type t := t
  end

And the implementation is:

module T : I =
  struct
    type t = [ `Foo ] [@@deriving sexp]
  end

But Sexpable does not expose __t_of_sexp__. So, when I try to use T in another module, like:

module M = 
  struct
    type tt = T.t [@@deriving sexp_poly]
    type t = [ tt | `Bar ] [@@deriving sexp]
  end

This fails because it cannot find __t_of_sexp__.
Currently, I am manually exporting __t_of_sexp__ in my signature I, but it would be nice not to have to mess with the signature.

The `@@` operator is not exported

I'm not sure whether it is intentional or not (I hope not), but this operator is not exposed and any usage provokes a warning:

There is not equivalent functionality in Base or Stdio at the moment,
so you need to use [Caml.( @@ )] instead

The @@ operator is a part of OCaml language for quite a few time and hiding it may confuse new users and irritate experienced.

js_of_ocaml and missing runtime with base from opam

Version: v0.9.4 (opam) OCaml 4.05 / 4.06

Hello. When I'm trying to compile something with base by js_of_ocaml, I have such errors:

Missing primitives:
  Base_am_testing
  Base_internalhash_fold_float
  Base_internalhash_fold_int
  Base_internalhash_fold_int64
  Base_internalhash_fold_string
  Base_internalhash_get_hash_value

As I understand, it's because META file doesn't contain
jsoo_runtime = "runtime.js"
so the compiler knows nothing about the implementation of these functions.

If I install base manually, META starts to contain this information and my compilation is successful.

Conflict caused by use of @deprecated for shadow-stdlib

Since MPR#7444, GPR#1138 (included in 4.06), the use of @deprecated by shadow-stdlib is inconvenient / results in warning 3 needing to be disabled. It used to be that one could write:

include module type of (
  Base :
    module type of Base
    with module Format = Caml.Format )

in order to allow access to the standard Format module (for which Base/Core do not provide a more approved variant). Now such constructs trigger warning 3.

Perhaps there is somewhere I have yet to find to attach a [@warning "-3"] attribute to silence them?

To my understanding, the use of @deprecated by the shadow-stdlib does not use the standard semantics of deprecated. In the cases where there are alternatives in Base/Core, the deprecated attribute makes sense, but in the other cases it is not so clear.

module types T, T1, and T2 are not exported

In previous versions of Core these module types were exported to the top level, so that we were able to use them as T, T1, etc after the Core_kernel.Std or Core.Std is opened. Base introduces an extra layer of indirection, e.g., we now write T.T, T.T1, etc. Is it intended? It looks weird to me (very smlish) and also complicates the process of migration from core to base.

Problem installing base in 4.03.0

I wanted to install base, however, I got an error that I should upgrade first my ocaml version

opam install base
[ERROR] base is not available because your system doesn't comply with ocaml-version >= "4.03.0".

So I downloaded and installed ocaml 4.03. However, now I'm getting a new error

sromano@3dcuba:~/ocaml-4.03.0$ opam install base
The following actions will be performed:
  ∗  install conf-m4   1                      [required by ocamlfind]
  ∗  install base-num  base                   [required by num]
  ∗  install ocamlfind 1.7.3                  [required by jbuilder]
  ∗  install num       0                      [required by sexplib]
  ∗  install jbuilder  1.0+beta13             [required by base]
  ∗  install sexplib   v0.9.2                 [required by base]
  ∗  install base      v0.9.3
===== ∗  7 =====
Do you want to continue ? [Y/n] Y

=-=- Gathering sources =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
[jbuilder] Archive in cache
[ocamlfind] Archive in cache
Processing  7/7: [base: from default] [sexplib: from default]
[default] https://opam.ocaml.org/archives/sexplib.v0.9.2+opam.tar.gz downloaded
[default] https://opam.ocaml.org/archives/base.v0.9.3+opam.tar.gz downloaded

=-=- Processing actions -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
∗  installed base-num.base
∗  installed num.0
∗  installed conf-m4.1
∗  installed ocamlfind.1.7.3
∗  installed jbuilder.1.0+beta13
∗  installed sexplib.v0.9.2
[ERROR] The compilation of base failed at "jbuilder build -p base -j 4".

#=== ERROR while installing base.v0.9.3 =======================================#
# opam-version 1.2.2
# os           linux
# command      jbuilder build -p base -j 4
# path         /home/sromano/.opam/system/build/base.v0.9.3
# compiler     system (4.03.0)
# exit-code    1
# env-file     /home/sromano/.opam/system/build/base.v0.9.3/base-2132-0d0df3.env
# stdout-file  /home/sromano/.opam/system/build/base.v0.9.3/base-2132-0d0df3.out
# stderr-file  /home/sromano/.opam/system/build/base.v0.9.3/base-2132-0d0df3.err
### stderr ###
# [...]
# Warning: File pow_overflow_bounds.ml is both generated by a rule and present in the source tree.
# As a result, the rule is currently ignored, however this will become an error in the future.
# To keep the current behavior and get rid of this warning, add a field (fallback) to the rule.
#     ocamllex src/hex_lexer.ml
#        ocaml src/int63_backend.ml
#       ocamlc src/base__.{cmi,cmo,cmt}
#        ocaml src/string_set_primitives.ml
#           sh src/mpopcnt.sexp,src/popcnt_test.c
#     ocamldep compiler-stdlib/gen/gen.depends.ocamldep-output
# File unavailable: /usr/local/lib/ocaml/compiler-libs/ocamlbytecomp.cmxa



=-=- Error report -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
The following actions failed
  ∗  install base v0.9.3
The following changes have been performed
  ∗  install base-num  base
  ∗  install conf-m4   1
  ∗  install jbuilder  1.0+beta13
  ∗  install num       0
  ∗  install ocamlfind 1.7.3
  ∗  install sexplib   v0.9.2

How to run tests?

Hi, I am trying to see how to set up jbuilder for my own project to build tests. How do you run tests in base? I see a jbuild file in the test folder but jbuilder base_test does not work for me. Thanks!

Dependency loop: base depends on sexplib depends on base

I have no idea how either base or sexplib can be built as they mutually depend on each other.

Hashtbl.merge fails

This one fails:

open Base

let pr fmt = Caml.Printf.printf (Caml.(^^) fmt "\n")

let () =
  let h0 = Hashtbl.create (module String) () in
  (* This throws exception in merge *)
  let h1 = Hashtbl.create (module String) () in
  (* This one works: *)
  (* let h1 = Hashtbl.copy h0 in *)
  Hashtbl.add h0 "a" 1 |> ignore;
  Hashtbl.add h1 "a" 1 |> ignore;
  Hashtbl.add h1 "b" 2 |> ignore;
  let h2 = Hashtbl.merge h0 h1 ~f:(
    fun ~key values ->
      match values with
      | `Both (left, right) -> Some right
      | `Left left -> Some left
      | `Right right -> Some right
  )
  in
  pr "Testing base: %d" (Hashtbl.length h2)

I understand that a module String object is each time unique. How I can share it (apart from using copy)? I've tried to create it with let but I couldn't make it compile (what module type should I use?) What if I need to serialize, deserialize, and merge back?

merlin-locate fails with Base and other Jane Street libs

I'm not 100% sure if this is an issue with the installation of Jane Street libraries, or a problem with Merlin, but Merlin-locate seems highly confused. If I write:

open Base

let x = List.map

and then do a merlin-locate on the value List.map, I end up in the stdlib, not in Base. This is true for other JS libraries (e.g., Core, Async), but not other libraries like Cohttp. For things like Async, where there's no stdlib alternative, I get the "not in environment" error.

Note that Merlin does get types right in this context, and this is using jbuilder, so the .merlin file should be set up appropriately.

This is using the latest stable releases of everything on opam, which means the 0.10 version of Base, and merlin 3.0.5.

Unable to install latest base via opam

I couldn't get base to build. Not sure what's going on. I was trying with 4.03.0. THis was on mac os x.

~ $ opam install base
The following actions will be performed:
  ∗  install jbuilder 0.1.alpha1              [required by base]
  ∗  install base     0.1.alpha1
===== ∗  2 =====
Do you want to continue ? [Y/n] y

=-=- Gathering sources =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=  🐫
[jbuilder.0.1.alpha1] https://github.com/janestreet/jbuilder/archive/0.1.alpha1.tar.gz downloaded
[base.0.1.alpha1] https://github.com/janestreet/base/archive/0.1.alpha1.tar.gz downloaded

=-=- Processing actions -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=  🐫
∗  installed jbuilder.0.1.alpha1
[ERROR] The compilation of base failed at "jbuilder build-package base -j 6".

#=== ERROR while installing base.0.1.alpha1 ===================================#
# opam-version 1.2.2
# os           darwin
# command      jbuilder build-package base -j 6
# path         /Users/yminsky/.opam/4.03.0/build/base.0.1.alpha1
# compiler     4.03.0
# exit-code    1
# env-file     /Users/yminsky/.opam/4.03.0/build/base.0.1.alpha1/base-58857-a00279.env
# stdout-file  /Users/yminsky/.opam/4.03.0/build/base.0.1.alpha1/base-58857-a00279.out
# stderr-file  /Users/yminsky/.opam/4.03.0/build/base.0.1.alpha1/base-58857-a00279.err
### stderr ###
# [...]
# Running: (cd _build/default && /Users/yminsky/.opam/4.03.0/bin/ocamlc.opt -w -40 -g -bin-annot -I compiler-stdlib/src -I shadow-stdlib/src -I src -open Base__ -o src/base__Comparable.cmi -c -intf src/comparable.mli)
# Running: (cd _build/default && /Users/yminsky/.opam/4.03.0/bin/ocamlc.opt -w -40 -g -bin-annot -I compiler-stdlib/src -I shadow-stdlib/src -I src -open Base__ -o src/base__Comparable.cmo -c -impl src/comparable.ml)
# Running: (cd _build/default && /Users/yminsky/.opam/4.03.0/bin/ocamlc.opt -w -40 -g -bin-annot -I compiler-stdlib/src -I shadow-stdlib/src -I src -open Base__ -o src/base__Sexp_with_comparable.cmi -c -intf src/sexp_with_comparable.mli)
# Running: (cd _build/default && /Users/yminsky/.opam/4.03.0/bin/ocamlc.opt -w -40 -g -bin-annot -I compiler-stdlib/src -I shadow-stdlib/src -I src -open Base__ -o src/base__Source_code_position.cmi -c -intf src/source_code_position.mli)
# Running: (cd _build/default && /Users/yminsky/.opam/4.03.0/bin/ocamlc.opt -w -40 -g -bin-annot -I compiler-stdlib/src -I shadow-stdlib/src -I src -open Base__ -o src/base__Bool.cmi -c -intf src/bool.mli)
# Running: (cd _build/default && /Users/yminsky/.opam/4.03.0/bin/ocamlc.opt -w -40 -g -bin-annot -I compiler-stdlib/src -I shadow-stdlib/src -I src -open Base__ -o src/base__Identifiable.cmi -c -intf src/identifiable.mli)
# File "src/identifiable.mli", line 1:
# Error: Corrupted compiled interface
# src/base__Import0.cmi
# Command exited with code 2: (cd _build/default && /Users/yminsky/.opam/4.03.0/bin/ocamlc.opt -w -40 -g -bin-annot -I compiler-stdlib/src -I shadow-stdlib/src -I src -open Base__ -o src/base__Identifiable.cmi -c -intf src/identifiable.mli)

Windows compatibility

Trying to compile base under windows I get:

File "_build/default/src/mpopcnt.sexp", line 1, characters 1-11:                                          
12:411 | '(-mpopcnt)'
     ^^^^^^^^^^
Error: too many s-expressions found in input

After the following

--- a/src/dune
+++ b/src/dune
@@ -16,7 +16,7 @@
 
 (library (name base) (public_name base)
  (libraries caml sexplib0 shadow_stdlib) (install_c_headers internalhash)
- (c_flags :standard -D_LARGEFILE64_SOURCE (:include mpopcnt.sexp))
+ (c_flags :standard -D_LARGEFILE64_SOURCE)
  (c_names exn_stubs int_math_stubs internalhash_stubs hash_stubs am_testing)
  (preprocess no_preprocessing)
   (lint

base builds OK, but I expect -mpopcnt option should be excluded automatically if not supported by C compiler (MSVC in my case)?

Unfortunate backtrace clearing by `with_return`

The use of With_return.with_return in e.g. Container.fold_result leads to a call to Exn.raise_without_backtrace, which calls clear_backtrace. Perhaps in other contexts it makes sense for Exn.raise_without_backtrace to clear the backtrace, but it makes debugging any code using with_return rather harder.

Broken link to paper about quicksort

One of the papers linked to in a comment about the array sorting algorithm is broken:

base/src/array.ml

Lines 38 to 43 in 48886c9

  See the following for more information: 

  - "Dual-Pivot Quicksort" by Vladimir Yaroslavskiy. 

  Available at http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf 

  - "Quicksort is Optimal" by Sedgewick and Bentley. 

  Slides at http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf 

  - http://www.sorting-algorithms.com/quick-sort-3-way *)

http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf is not available, although it can be accessed at https://web.archive.org/web/20150228054537/iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf.

Missing documentation for Base.Monad and Base Applicative

Basically zero information on these modules:

https://ocaml.janestreet.com/ocaml-core/latest/doc/base/Base/Monad/index.html

https://ocaml.janestreet.com/ocaml-core/latest/doc/base/Base/Applicative/index.html

Problem installing base v0.9.3( 4.06 support )

#=== ERROR while compiling base.v0.9.3 ========================================#
# context      2.0.0~beta4 | linux/x86_64 | ocaml-variants.4.06.0+trunk+fp+flambda | https://opam.ocaml.org/2.0#2017-10-29 02:04
# path         ~/.opam/4.06.0+trunk+fp+flambda/.opam-switch/build/base.v0.9.3
# command      jbuilder build -p base -j 3
# exit-code    1
# env-file     ~/.opam/log/base-9566-ffb3fd.env
# output-file  ~/.opam/log/base-9566-ffb3fd.out
### output ###
# Error: Signature mismatch:
# [...]
# (cd _build/default && /home/pe200012/.opam/4.06.0+trunk+fp+flambda/bin/ocamlc.opt -w -40 -g -bin-annot -I /home/pe200012/.opam/4.06.0+trunk+fp+flambda/lib/sexplib/0 -I compiler-stdlib/src -I shadow-stdlib/src -no-alias-deps -I src -open Base__ -o src/base__String.cmo -c -impl src/string.ml)
# File "src/string.ml", line 110, characters 5-140:
# Error: Signature mismatch:
#        ...
#        Values do not match:
#          val create : len:int -> bytes
#        is not included in
#          val create : len:int -> t
#        File "src/blit_intf.ml", line 77, characters 2-27:
#          Expected declaration
#        File "src/string.ml", line 112, characters 10-16: Actual declaration

What does it mean? How can I fix it?

bytes does not compile

dune build @install
ocamlc src/.base.objs/base__Bytes0.{cmi,cmo,cmt} (exit 2)
(cd build/default && /usr/bin/ocamlc.opt -w @a-4-29-40-41-42-44-45-48-58-59-60-40 -strict-sequence -strict-formats -short-paths -keep-locs -safe-string -g -bin-annot -I src/.base.objs -I /usr/lib64/ocaml/site-lib/sexplib0 -I compiler-stdlib/src/.caml.objs -I shadow-stdlib/src/.shadow_stdlib.objs -no-alias-deps -open Base_ -o src/.base.objs/base__Bytes0.cmo -c -impl src/bytes0.ml)
File "src/bytes0.ml", line 57, characters 29-50:
Error (warning 6): labels pos, len were omitted in the application of this function.
base-v0.11.1 # dune install
The following .install are missing:

_build/default/base.install
You need to run: dune build @install

Map.add is a terrible idea

In the light of recent events, I feel obliged to open an issue about Map.add. The current semantics is that it adds a new entry to the map and silently overwrites existing entries, should one for the same key already be present.

I would be curious to hear the rational behind this unsafe semantics (I suppose there are historical reasons?). But whatever the reasons may be, I don't think they justify a bad interface.

I think that the Jane Street libraries in general do a great job of following the principle of least surprise (really, no surprise) and making things as explicit as possible, both by using self-explanatory names and by using the type system to great effect. This is a notable exception.
It can lead to subtle bugs that are very hard to locate, and in particular cannot be found by starring at the code because the code is not explicit about it! Ironically, the fact that the Jane Street libraries usually have such a great, explicit interfaces makes this semantics of Map.add even more dangerous.

Just for sake of comparison, here is the interface of Hashtbl:

val add : ('a, 'b) t ‑> key:'a key ‑> data:'b ‑> [ `Ok | `Duplicate ]
val add_or_error : ('a, 'b) t ‑> key:'a key ‑> data:'b ‑> unit Or_error.t
val add_exn : ('a, 'b) t ‑> key:'a key ‑> data:'b ‑> unit

This is a great interface! And I hope it doesn't take much convincing to believe that it is a bad idea to give such different semantics to Map.add and Hastbl.add.

I seem to remember that Map.add was actually deprecated in previous releases of the library in favor of Map.set, which is a much better name for a function with this semantics. This seems like the right move. I'm certain the current interface has wasted lots of peoples precious time. (I have strong empirical evidence to believe so....)

v0.10.0 conflicts with merlin

It's weird that after upgrading base from v0.9.4 to v0.10.0, merlin doesn't show types, complete for external PKGs which is listed in the .merlin file.
If base is installed explicitly by opam install base.v0.9.4, merlin just works well.

Bytes.map, Bytes.iter and Bytes.fold support

Now with the clear separation of bytes and strings since OCaml 4.06 it make sense to provide such an interface to bytes too.

Compilation failure (cannot find dynamic lib)

I get a linking error when trying to compile a program using base. Here is a minimal example to reproduce the problem:

opam switch test-base -A 4.03.0
eval `opam config env`
opam install -y ocamlfind
opam install -y base
echo 'let () = print_endline (Base__String.concat [ "j" ; "l"]);;' > rien.ml
ocamlfind ocamlc -verbose -package base -linkpkg -o rien rien.ml

The last command returns the following error:

Effective set of compiler predicates: pkg_base.caml,pkg_base.shadow_stdlib,pkg_base,autolink,byte
+ ocamlc.opt -verbose -o rien -I /home/pveber/.opam/test-base/lib/base /home/pveber/.opam/test-base/lib/base/caml.cma /home/pveber/.opam/test-base/lib/base/shadow_stdlib.cma /home/pveber/.opam/test-base/lib/base/base.cma rien.ml
File "rien.ml", line 1:
Error: Error on dynamically loaded library: base_stubs.so: base_stubs.so: cannot open shared object file: No such file or directory
ocamlc.opt returned with exit code 2

However, everything seems to be in its place:

$echo $CAML_LD_LIBRARY_PATH 
/home/pveber/.opam/test-base/lib/stublibs
$ls $CAML_LD_LIBRARY_PATH/dllbase*
/home/pveber/.opam/test-base/lib/stublibs/dllbase_stubs.so

Not really sure what I'm doing wrong here...

Incorrect version in opam file for v0.11.1

It looks like the version in the opam file needs to be bumped here.

base/base.opam

Line 2 in 704d38b

version: "v0.11.0"

Would this cause v0.11.1 to be unavailable via opam?

$ opam update; opam info base

<><> Updating package repositories ><><><><><><><><><><><><><><><><><><><><>  🐫
[default] no changes from https://opam.ocaml.org/2.0

<><> base: information on all versions ><><><><><><><><><><><><><><><><><><>  🐫
name         base
all-versions v0.9.0  v0.9.1  v0.9.2  v0.9.3  v0.9.4  v0.10.0  v0.11.0

<><> Version-specific details <><><><><><><><><><><><><><><><><><><><><><><>  🐫
version       v0.11.0
repository    default
url.src:      "https://ocaml.janestreet.com/ocaml-core/v0.11/files/base-v0.11.0.tar.gz"
url.checksum: "md5=787aaa04b25eca106ebb9380a32bad66"
homepage:     "https://github.com/janestreet/base"
bug-reports:  "https://github.com/janestreet/base/issues"
dev-repo:     "git+https://github.com/janestreet/base.git"
authors:      "Jane Street Group, LLC <[email protected]>"
maintainer:   "[email protected]"
license:      "Apache-2.0"
depends:      "ocaml" {>= "4.04.1" & < "4.07.0"}
              "sexplib0" {>= "v0.11" & < "v0.12"}
              "jbuilder" {build & >= "1.0+beta18.1"}
depopts:      "base-native-int63"
synopsis      Full standard library replacement for OCaml
description   Full standard library replacement for OCaml
              Base is a complete and portable alternative to the OCaml standard
              library. It provides all standard functionalities one would expect
              from a language standard library. It uses consistent conventions
              across all of its module.
              Base aims to be usable in any context. As a result system dependent
              features such as I/O are not offered by Base. They are instead
              provided by companion libraries such as stdio:
                https://github.com/janestreet/stdio

List.findi_exn is missing

I found myself writing

let find_index v l =
  match List.findi l ~f:(fun _ c -> c = v) with
  | None -> raise Not_found
  | Some (i, _) -> i

instead of

let find_index v l =
  List.findi_exn l ~f:(fun _ c -> c = v) |> fst

as there is no findi_exn function in the List module. As most functions here have a _exn variant, I see no reason why findi would not have its own?

Bizzare type signatures in utop

This may be a utop issue, I have no idea.

Here's an example of Base functions that showup with weird sexp type signatures in utop

─( 13:54:27 )─< command 0 >─────────────────────────────────────────────────────────────────────────────────────────────────────────────{ counter: 0 }─
utop # List.map;;
- : 'a sexp_list -> f:('a -> 'b) -> 'b sexp_list = <fun>
─( 13:54:34 )─< command 1 >─────────────────────────────────────────────────────────────────────────────────────────────────────────────{ counter: 0 }─
utop # String.split_on_chars;;
- : Base.string -> on:char sexp_list -> Base.string sexp_list = <fun>
─( 13:55:42 )─< command 2 >─────────────────────────────────────────────────────────────────────────────────────────────────────────────{ counter: 0 }─
utop # Hashtbl.of_alist_exn;;
- : ('a, 'b, ('a * 'b) sexp_list -> ('a, 'b) Hashtbl.t)
    Hashtbl_intf.create_options_with_first_class_module
= <fun>

~/.ocamlinit:

#use "topfind";;
#thread;;
#camlp4o;;
#require "core.top";;

(* Added by OPAM. *)
let () =
  try Topdirs.dir_directory (Sys.getenv "OCAML_TOPLEVEL_PATH")
  with Not_found -> ()
;;

open Base

lewis@1711:~/code/nw2018$ opam list

Installed packages for 4.05.0:

base v0.10.0 Full standard library replacement for OCaml
base-bigarray base Bigarray library distributed with the OCaml compiler
base-bytes base Bytes library distributed with the OCaml compiler
base-num base Num library distributed with the OCaml compiler
base-threads base Threads library distributed with the OCaml compiler
base-unix base Unix library distributed with the OCaml compiler
bin_prot v0.10.0 A binary protocol generator
biniou 1.2.0 Binary data format designed for speed, safety, ease of use and backward compatibility as protocols evolve
camomile 0.8.7 A comprehensive Unicode library
cmdliner 1.0.2 Declarative definition of command line interfaces for OCaml
conf-m4 1 Virtual package relying on m4
conf-which 1 Virtual package relying on which
configurator v0.10.0 Helper library for gathering system configuration
core v0.10.0 Industrial strength alternative to OCaml's standard library
core_kernel v0.10.0 Industrial strength alternative to OCaml's standard library
cppo 1.6.4 Equivalent of the C preprocessor for OCaml programs
easy-format 1.3.1 High-level and functional interface to the Format module of the OCaml standard library
fieldslib v0.10.0 Syntax extension to define first class values representing record fields, to get and set record fields, iterate and fold over all fields of a r
jane-street-headers v0.10.0 Jane Street C header files
jbuilder 1.0+beta18 Fast, portable and opinionated build system
lambda-term 1.12.0 Terminal manipulation library for OCaml
lwt 3.2.1 Promises, concurrency, and parallelized I/O
lwt_react 1.1.0 Helpers for using React with Lwt
merlin 3.0.5 Editor helper, provides completion, typing and source browsing in Vim and Emacs
num 0 The Num library for arbitrary-precision integer and rational arithmetic
ocaml-compiler-libs v0.10.0 OCaml compiler libraries repackaged
ocaml-migrate-parsetree 1.0.7 Convert OCaml parsetrees between different versions
ocamlbuild 0.12.0 OCamlbuild is a build system with builtin rules to easily build most OCaml projects.
ocamlfind 1.7.3-1 A library manager for OCaml
ocp-build 1.99.20-beta Project builder for OCaml
ocp-indent 1.6.1 A simple tool to indent OCaml programs
octavius 1.2.0 Ocamldoc comment syntax parser
ppx_assert v0.10.0 Assert-like extension nodes that raise useful errors on failure
ppx_ast v0.10.0 OCaml AST used by Jane Street ppx rewriters
ppx_base v0.10.0 Base set of ppx rewriters
ppx_bench v0.10.0 Syntax extension for writing in-line benchmarks in ocaml code
ppx_bin_prot v0.10.0 Generation of bin_prot readers and writers from types
ppx_compare v0.10.0 Generation of comparison functions from types
ppx_core v0.10.0 Standard library for ppx rewriters
ppx_custom_printf v0.10.0 Printf-style format-strings for user-defined string conversion
ppx_derivers 1.0 Shared [@@deriving] plugin registry
ppx_driver v0.10.2 Feature-full driver for OCaml AST transformers
ppx_enumerate v0.10.0 Generate a list containing all values of a finite type
ppx_expect v0.10.0 Cram like framework for OCaml
ppx_fail v0.10.0 Add location to calls to failwiths
ppx_fields_conv v0.10.0 Generation of accessor and iteration functions for ocaml records
ppx_hash v0.10.0 A ppx rewriter that generates hash functions from type expressions and definitions
ppx_here v0.10.0 Expands [%here] into its location
ppx_inline_test v0.10.0 Syntax extension for writing in-line tests in ocaml code
ppx_jane v0.10.0 Standard Jane Street ppx rewriters
ppx_js_style v0.10.0 Code style checker for Jane Street Packages
ppx_let v0.10.0 Monadic let-bindings
ppx_metaquot v0.10.0 Write OCaml AST fragment using OCaml syntax
ppx_optcomp v0.10.0 Optional compilation for OCaml
ppx_optional v0.10.0 Pattern matching on flat options
ppx_pipebang v0.10.0 A ppx rewriter that inlines reverse application operators |> and |!
ppx_sexp_conv v0.10.0 Generation of S-expression conversion functions from type definitions
ppx_sexp_message v0.10.0 A ppx rewriter for easy construction of s-expressions
ppx_sexp_value v0.10.0 A ppx rewriter that simplifies building s-expressions from ocaml values
ppx_tools 5.0+4.05.0 Tools for authors of ppx rewriters and other syntactic tools
ppx_tools_versioned 5.1 A variant of ppx_tools based on ocaml-migrate-parsetree
ppx_traverse v0.10.0 Automatic generation of open-recursion classes
ppx_traverse_builtins v0.10.0 Builtins for Ppx_traverse
ppx_type_conv v0.10.0 Support Library for type-driven code generators
ppx_typerep_conv v0.10.0 Generation of runtime types from type declarations
ppx_variants_conv v0.10.0 Generation of accessor and iteration functions for ocaml variant types
re 1.7.1 RE is a regular expression library for OCaml
react 1.2.1 Declarative events and signals for OCaml
result 1.3 Compatibility Result module
sexplib v0.10.0 Library for serializing OCaml values to and from S-expressions
spawn v0.10.1 Spawning sub-processes
stdio v0.10.0 Standard IO library for OCaml
topkg 0.9.1 The transitory OCaml software packager
typerep v0.10.0 typerep is a library for runtime types.
utop 2.1.0 Universal toplevel for OCaml
variantslib v0.10.0 Part of Jane Street's Core library
yojson 1.4.1 Yojson is an optimized parsing and printing library for the JSON format
zed 1.6 Abstract engine for text edition in OCaml

Add Map.insert_with

This is a function from Haskell (insertWith) with signature 'a t -> key:key -> data:'a -> f:('a -> 'a -> 'a) -> 'a t that I often miss when programming in OCaml. For example, it's useful for implementing incr and similar functions: Map.insert_with m ~key ~data:incr_count ~f:(+).

The closest function that base currently has is update : 'a t -> key -> f:('a option -> 'a) -> 'a t.

If accepted, I'll gladly contribute a pull request.

114.34+110 doesn't build

arch-vm[1085]:~% opam install base
The following actions will be performed:
  ∗  install base 114.34+110

=-=- Gathering sources =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
[base] git://github.com/janestreet/base#8bf48b42935fe5b10b23c9d246d40fd7e5b8caf1 already up-to-date

=-=- Processing actions -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
[ERROR] The compilation of base failed at "jbuilder build --only-packages base --root . -j 4".

#=== ERROR while installing base.114.34+110 ===================================#
# opam-version 1.2.2
# os           linux
# command      jbuilder build --only-packages base --root . -j 4
# path         /home/mdl/.opam/4.04.0+flambda/build/base.114.34+110
# compiler     4.04.0+flambda
# exit-code    1
# env-file     /home/mdl/.opam/4.04.0+flambda/build/base.114.34+110/base-16056-1872ec.env
# stdout-file  /home/mdl/.opam/4.04.0+flambda/build/base.114.34+110/base-16056-1872ec.out
# stderr-file  /home/mdl/.opam/4.04.0+flambda/build/base.114.34+110/base-16056-1872ec.err
### stderr ###
# jbuilder: required argument TARGET is missing
# Usage: jbuilder build [OPTION]... TARGET...
# Try `jbuilder build --help' or `jbuilder --help' for more information.



=-=- Error report -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
The following actions failed
  ∗  install base 114.34+110
No changes have been performed

jbuilder version:

arch-vm[1086]:~% opam info jbuilder
             package: jbuilder
             version: 114.34+110
          repository: janestreet
        upstream-url: git://github.com/janestreet/jbuilder#4fa0844e42b91b9355c1875d131d99bc58d6a9ee
       upstream-kind: git
            homepage: https://github.com/janestreet/jbuilder
         bug-reports: https://github.com/janestreet/jbuilder/issues
            dev-repo: https://github.com/janestreet/jbuilder.git
              author: Jane Street Group, LLC <[email protected]>
             license: Apache-2.0
   installed-version: 114.34+110 [4.04.0+flambda]

I think maybe base.opam should have this instead, judging from the Makefile:

build: [
  ["jbuilder" "build" "--only-packages" "base" "--root" "." "-j" jobs "@install"]
]

Base sets Printexc.record_backtrace by default

The module initialization code of base calls Backtrace.initialize_module, which (unless OCAMLRUNPARAM is set) calls Printexc.record_backtrace true.

This is a significant performance foot-gun, and as far as I can see, not documented anywhere outside the code.

Aside: It's not clear to me that libraries have any business setting global state like this, but presumably there was an argument for this being the right default.

The Sequence module is missing fold_until in the documentation

The Sequence.fold_until function is missing from this page. Also it would be really nice with a simple example of how to use this function.

Base does not compile under ARMv7

I got the following compilation error when attempting to install Base via OPAM on a Raspberry Pi 3 running Stretch (with gcc 6.3.0):

/home/pi/.opam/ocaml-base-compiler.4.04.0/bin/ocamlc.opt -g -ccopt -g -ccopt -D_LARGEFILE64_SOURCE -ccopt -mpopcnt -o am_testing.o am_testing.c
gcc: error: unrecognized command line option ‘-mpopcnt’

I suspect -mpopcnt may be x86 specific.

Hashtbl.iter and Hashtbl.iteri

Hashtbl.iter doesn't pass in hashtbl key to ~f. Is this by design? Additionally, Hashtbl.iteri doesnt' pass in the index int value to ~f:. Again is this by design?

The documentation from ocp-browser seems to suggest both the key and data are to be expected in ~f.

 [Hashtbl.iter f tbl] applies [f] to all bindings in table [tbl].                                     
    [f] receives the key as first argument, and the associated value                                     
    as second argument. Each binding is presented exactly once to [f].                                   
                                                                                                         
    The order in which the bindings are passed to [f] is unspecified.                                    
    However, if the table contains several bindings for the same key,                                    
    they are passed to [f] in reverse order of introduction, that is,                                    
    the most recent binding is passed first.                                                             
                                                                                                         
    If the hash table was created in non-randomized mode, the order                                      
    in which the bindings are enumerated is reproducible between                                         
    successive runs of the program, and even between minor versions                                      
    of OCaml.  For randomized hash tables, the order of enumeration                                      
    is entirely random.                                                                                  
                                                                                                         
    The behavior is not defined if the hash table is modified                                            
    by [f] during the iteration.

Documentation: no "__"

The documentation should not contain any double underscore (you are probably well away of it, this is just meant to track the issue in the open).

Example:

_BitScanForward64 intrinsic is not available on x86

This function

base/src/int_math_stubs.c

Line 25 in aee79da

_BitScanForward64(&r, x);

is not supported by 32-bit MSVC (see https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64). So I get a link error.

Documentation: no duplicate "type t"

When including a module with type t := t, the documentation (when unfolding) should maybe gray out (or hide in some way) the type t in the included module: it is distracting and does not bring any information.

I know it may be controversial because the type t is indeed part of the included module but I think this should be discussed. Maybe one can provide a way to go to the module sig (new page) and put inline a foldable "Coming from module ..." where only values and new types are present (in case of type t := u a type renaming could take place so the documentation reads in terms of the module one is looking at).

Fails to build

[ERROR] The compilation of base failed at "jbuilder build -p base -j 3".

#=== ERROR while compiling base.v0.9.3 ========================================#
# command      jbuilder build -p base -j 3
# path         /home/rgrinberg/.opam/publish/.opam-switch/build/base.v0.9.3
# exit-code    1
# env-file     /home/rgrinberg/.opam/log/base-14709-f53971.env
# output-file  /home/rgrinberg/.opam/log/base-14709-f53971.out
### output ###
#     ocamllex src/hex_lexer.ml
#        ocaml src/int63_backend.ml (exit 2)
# (cd _build/default/src && /home/rgrinberg/.opam/publish/bin/ocaml select-int63-backend/select.ml -native-int63 ${lib-available:base-native-int63} -arch-sixtyfour true -o int63_backend.ml)
# Exception: Failure "bad command line arguments".

Documentation: second level include are not visible

When an included interface includes a second level one, the latter is not visible enough when it is open.

Moving the second level brace to the right will also prevent the first level one to be thinner in front of a closed second level include.

[v0.12.0] Int63 and js_of_ocaml

I installed the janestreet stuff from ocaml/opam-repository#13452 for my incr_dom app and triggered an assertion in Int63:

base/src/int63.ml

Line 36 in 8c9bc16

let () = assert (Int.(=) num_bits 63)

This does happen on Firefox when opening the below index.html file. Chromium reports an uncaught exception in bigarray.ml

int63.ml

open Base
let () = Stdio.print_endline Int63.(zero |> to_int_exn |> Int.to_string)

index.html

<html>
  <head>
    <meta charset="utf-8">
    <title>Int63</title>
  </head>
  <body>
    <script src='int63.bc.js'></script>
  </body>
</html>

dune

(executable
 (name int63)
 (libraries base stdio))

opam switch (sorry for the noise)

compiler: [
  "base-bigarray.base"
  "base-threads.base"
  "base-unix.base"
  "ocaml.4.07.1"
  "ocaml-base-compiler.4.07.1"
  "ocaml-config.1"
]
roots: [
  "base.v0.12.0"
  "base64.3.1.0"
  "csv.2.2"
  "gen_js_api.1.0.5"
  "incr_dom.v0.12.0"
  "incr_dom_widgets.v0.12.0"
  "merlin.3.2.2"
  "ocaml-base-compiler.4.07.1"
  "odig.0.0.3"
  "odoc.1.3.0"
  "ppx_deriving_yojson.3.3"
]
installed: [
  "asetmap.0.8.1"
  "astring.0.8.3"
  "async_js.v0.12.0"
  "async_kernel.v0.12.0"
  "async_rpc_kernel.v0.12.0"
  "base.v0.12.0"
  "base-bigarray.base"
  "base-bytes.base"
  "base-threads.base"
  "base-unix.base"
  "base64.3.1.0"
  "base_bigstring.v0.12.0"
  "base_quickcheck.v0.12.0"
  "bin_prot.v0.12.0"
  "biniou.1.2.0"
  "bos.0.2.0"
  "cmdliner.1.0.3"
  "conf-m4.1"
  "conf-which.1"
  "core_kernel.v0.12.0"
  "cppo.1.6.5"
  "cppo_ocamlbuild.1.6.0"
  "csv.2.2"
  "dune.1.7.2"
  "easy-format.1.3.1"
  "fieldslib.v0.12.0"
  "fmt.0.8.5"
  "fpath.0.7.2"
  "gen_js_api.1.0.5"
  "incr_dom.v0.12.0"
  "incr_dom_widgets.v0.12.0"
  "incr_map.v0.12.0"
  "incr_select.v0.12.0"
  "incremental.v0.12.0"
  "jane-street-headers.v0.12.0"
  "jbuilder.transition"
  "js_of_ocaml.3.3.0"
  "js_of_ocaml-compiler.3.3.0"
  "js_of_ocaml-ppx.3.3.0"
  "jst-config.v0.12.0"
  "logs.0.6.2"
  "merlin.3.2.2"
  "mtime.1.1.0"
  "num.1.1"
  "ocaml.4.07.1"
  "ocaml-base-compiler.4.07.1"
  "ocaml-compiler-libs.v0.11.0"
  "ocaml-config.1"
  "ocaml-migrate-parsetree.1.2.0"
  "ocamlbuild.0.12.0"
  "ocamlfind.1.8.0"
  "ocamlgraph.1.8.8"
  "octavius.1.2.0"
  "odig.0.0.3"
  "odoc.1.3.0"
  "opam-core.2.0.3"
  "opam-file-format.2.0.0"
  "opam-format.2.0.3"
  "parsexp.v0.12.0"
  "ppx_assert.v0.12.0"
  "ppx_base.v0.12.0"
  "ppx_bench.v0.12.0"
  "ppx_bin_prot.v0.12.0"
  "ppx_compare.v0.12.0"
  "ppx_custom_printf.v0.12.0"
  "ppx_derivers.1.0"
  "ppx_deriving.4.2.1"
  "ppx_deriving_yojson.3.3"
  "ppx_enumerate.v0.12.0"
  "ppx_expect.v0.12.0"
  "ppx_fail.v0.12.0"
  "ppx_fields_conv.v0.12.0"
  "ppx_hash.v0.12.0"
  "ppx_here.v0.12.0"
  "ppx_inline_test.v0.12.0"
  "ppx_jane.v0.12.0"
  "ppx_js_style.v0.12.0"
  "ppx_let.v0.12.0"
  "ppx_module_timer.v0.12.0"
  "ppx_optcomp.v0.12.0"
  "ppx_optional.v0.12.0"
  "ppx_pipebang.v0.12.0"
  "ppx_sexp_conv.v0.12.0"
  "ppx_sexp_message.v0.12.0"
  "ppx_sexp_value.v0.12.0"
  "ppx_stable.v0.12.0"
  "ppx_tools.5.1+4.06.0"
  "ppx_tools_versioned.5.2.1"
  "ppx_typerep_conv.v0.12.0"
  "ppx_variants_conv.v0.12.0"
  "ppxfind.1.2"
  "ppxlib.0.5.0"
  "protocol_version_header.v0.12.0"
  "re.1.8.0"
  "record_builder.v0.12.0"
  "result.1.3"
  "rresult.0.6.0"
  "seq.base"
  "sexplib.v0.12.0"
  "sexplib0.v0.12.0"
  "splay_tree.v0.12.0"
  "splittable_random.v0.12.0"
  "stdio.v0.12.0"
  "stringext.1.5.0"
  "time_now.v0.12.0"
  "topkg.1.0.0"
  "typerep.v0.12.0"
  "tyxml.4.3.0"
  "uchar.0.0.2"
  "uri.2.2.0"
  "uutf.1.0.2"
  "variantslib.v0.12.0"
  "virtual_dom.v0.12.0"
  "webbrowser.0.6.1"
  "yojson.1.5.0"
]

Monad.Make() generates non-tail-recursive `all` and `all_unit`

We have a custom logging-ish monad and just ran into an issue on OS X where we ran out of stack space calling Our_monad.all on a list with ~100,000 elements.

I noticed that Monad.Make generates this:

https://github.com/janestreet/base/blob/master/src/monad.ml#L59

It's structured in basically the way you'd write a tail-recursive loop, but the >>= prevents it from being tail-recursive.

It's not entirely clear to me if it's possible to make this tail recursive but it's worth thinking about.

(Our workaround was adding custom all and all_unit functions)

	See the following for more information:
	- "Dual-Pivot Quicksort" by Vladimir Yaroslavskiy.
	Available at http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
	- "Quicksort is Optimal" by Sedgewick and Bentley.
	Slides at http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
	- http://www.sorting-algorithms.com/quick-sort-3-way *)