Previous week Up Next week


Here is the latest Caml Weekly News, for the week of January 06 to 13, 2009.

  1. Parsing simple type expressions
  2. Jane Street is hiring...
  3. OCaml meeting 2009 -- 2 weeks before end of subscription
  4. Heap implementations: Fibonacci, Brodal and relaxed

Parsing simple type expressions


Paolo Donadeo asked:
For a serializer I'm writing I need to parse simple OCaml type
expressions composed by OCaml basic types, tuples, options and lists.
Given a string like "(int * string option) list" and this type:

type types =
 | Int
 | String
 | Float
 | Char
 | Bool
 | Option of types
 | List of types
 | Tuple of types list

the function I need should return something like List (Tuple ([Int;

Before starting with low level sscanf functions I looked at the Genlex
module, but it wasn't so inspiring. Then I tried with Camlp4 but the
documentation doesn't really shine :-)

So is there a simple way to write this function using some standard module?
Jake Donham suggested:
This is pretty easy with Camlp4, although as you say there isn't much in the
docs to point the way. You might take a look at how orpc does it--see the
parse_type function in

(I'm going to cover using Camlp4 in this way on the blog I posted yesterday,
but not for another week or two.)

You might also look at some other Camlp4-based serialization tools, like
bin-prot/type-conv at
David Allsopp said and Martin Jambon added:
> ocamlyacc - you can get most of it for free out of parsing/parser.mly in the
> OCaml sources... the section on type expressions starts at line 1144 for 
> OCaml 3.11.0.

Our json-wheel library is a complete example:
Paolo Donadeo finally said:
Thanks, Matthieu and Jake, this is exactly what I had in mind. 

At the end, Camlp4 was the right solution to my simple problem, as I 
suspected from the beginning. Camlp4 is an extremely powerful tool and 
it's a pity it couldn't be used by everyone for lack of documentation. 
What is really needed, in my opinion, is a description of *what* one 
can do with Camlp4 without being an expert. For example a list of all 
syntax extension available out of the box might spread the use of 
Camlp4 among common programmers. 

Searching in the source code I can see things named: 
Camlp4ExceptionTracer, Camlp4FoldGenerator, Camlp4MetaGenerator, and 
so on. The names sounds great but... what is it? The source code is 
cryptic to every "regular" OCaml programmer like me. The same 
considerations apply to all the (many!) libraries available and 
related to Camlp4. 

What is needed to spread the use of this tool are some... recipes, 
like those available for ocamlbuild in its wiki pages.

Jane Street is hiring...


Yaron Minsky announced:
Greetings all.  I just wanted to remind people that Jane Street is
still hiring.  Despite the problems besetting much of the financial
industry, we have grown strongly in the last few years in our people,
our technology, the scope of our business and its profitability.  We
now have over 30 OCaml developers, and we are actively looking to hire
more in Tokyo, London and New York.

For someone who cares about functional programming, Jane Street is an
interesting place to consider.  Jane Street has invested deeply in
OCaml, to the point where we now have the largest team of OCaml
programmers in any industrial setting, and probably the world's
largest OCaml codebase--almost a million lines.  We really believe
in functional programming, and use OCaml for everything from research
to systems adminstration to trading systems.

The atmosphere is informal and intellectual, with a focus on learning.
The work itself is deeply challenging, and you get to see the
practical impact of your efforts in quick and dramatic terms.  Jane
Street is also a small enough place that people have the freedom to
get involved in many different areas of the business.

Unlike many financial firms, software and technology are considered a
core part of what we do, not some segmented-off cost center that the
people who run the business don't think about.  Jane Street is a place
where people really care about the quality of the software, to the
point that several of the most senior members of the firm, who do not
have technology backgrounds, nonetheless review critical
portions of the codebase before they can go into production.

If you'd like to learn more, here are some links.  First, here's a
paper I wrote for the Monad Reader:

We also have a technically-oriented blog:

For a (recruiting-oriented) overview of Jane Street, here's the firm

If you're interested, send me a resume and cover letter.

OCaml meeting 2009 -- 2 weeks before end of subscription


Sylvain Le Gall announced:
OCaml Meeting 2009 will take place in Grenoble on 4th February 2009.

A subscription form can be found on the wiki page and a fee of 32€ will
be used for the lunch. Subscription is mandatory for participants to
this year meeting. 

As last year, participants are invited to give a talk on what they are
doing with OCaml.

The list of possible talks is actually:
- news and projects
- OCaml Batteries Included
- Cameleon/Chamo 
- Delimited overloading
- OCaml as fast as C!

Further information (list of talks, hostels and other details): 

For people who need further information, you can contact either me or
Alan Schmitt (see for contact details).

Heap implementations: Fibonacci, Brodal and relaxed


Hugo Ferreira asked:
I would like to now if anyone has or knows of 
functional implementations of priority (aka Min, 
aka Max) heaps. Specifically I am looking for: 

Fibonacci, Brodal and relaxed heaps [1] 

with fast insert and deletes. 

Any literature or implementation in Haskell 
or F# are also welcome. 

I also would appreciate any additional comments on 
implementation issues and experience with heaps 
that may help me. 

Hugo Ferreira. 

blue storm suggested and Hugo Ferreira said:
> First of all, do you know about Okasaki leftist heaps (I suppose you 
> do as you're asking for even more advanced data structure) ? They're 
> simple O(log n) heap, nice to implement (~ 20 lines). 

Actually I didn't (although I know of these). But the thesis has a 
better performing binomial heap. 

> There was a page from Markus Mottl with translated OCaml code from the 
> book, but he removed it for some obscure reason. 

Still available (Chapter 6.):
Markus Mottl then added:
Yes, the OCaml translation of Okasaki's purely functional 
datastructures is still available online.  The version control 
repository, where you can also look at individual files without 
downloading the archive, is here: 

Note that leftist heaps are in chapter 3:

Using folding to read the cwn in vim 6+

Here is a quick trick to help you read this CWN if you are viewing it using vim (version 6 or greater).

:set foldmethod=expr
:set foldexpr=getline(v:lnum)=~'^=\\{78}$'?'<1':1

If you know of a better way, please let me know.

Old cwn

If you happen to miss a CWN, you can send me a message and I'll mail it to you, or go take a look at the archive or the RSS feed of the archives.

If you also wish to receive it every week by mail, you may subscribe online.

Alan Schmitt