Parser combinators are
sets of functions for building parsers in a composable fashion. Haskell’s
Parsec library and OCaml’s
Angstrom are two examples.
Both of these libraries expose *monadic* interfaces for
describing context-sensitive grammars. This post looks at implementing a more
restricted parsing library, structured around applicative
functors rather
than monads.

The next major release of the OCaml compiler, version 4.08, will be equipped
with a new syntax extension for
*monadic* and *applicative* composition. Practically it means that it will be
a bit more convenient to work with APIs structured around these
patterns. The design draws inspiration from
ppx_let but offers lighter syntax,
and removes the need of running the code through a ppx preprocessor.

Memoization is a strategy for preventing values to be computed multiple times. The sledgehammer approach in OCaml is a function with the signature:

Continue readingFollowing is a continuation of the topic of *modular implicits* , introduced in
the previous post on implicit
functors. This time
we’ll look at how the extension can help simplifying *lenses*. I covered
lenses in OCaml lenses via
modules, where a
rather verbose definition of a (van Laarhoven) lens was given in the form of a
module signature `LENS`

:

Modular implicits is an experimental feature of OCaml that has yet to land on the master branch. In this and upcomings posts I’m going to give a few examples of what it brings to the table. For an introduction to the topic it’s best to read the original paper.

Continue readingLenses, often described as first class getters and setters, can help simplify code for manipulating nested data structures. In this post I’m going to look at how to map the most popular Haskell representation, van Laarhoven lenses, to OCaml.

Continue readingA few weeks ago I came across a logic puzzle handed out as a *holiday challenge*.
I didn’t solve it by hand but instead turned to *Haskell* for some help. As it proved to be a fun
exercise I decided to pass it on and invited some friends to
contribute with solutions in a language of their choice. I here present
the given puzzle along with the set of submissions received.

The following is a write-up on an implementation of the Knuth-Morris-Pratt (or KMP) text search algorithm in OCaml. The algorithm itself is rather straight forward but implementing it in a functional style serves as a good example of how lazy data structures may be used as an optimization technique.

Continue readingIn a previous post I gave an example of how to represent algebraic data types using church encoding. In this post I’ll pick up the thread and show how this technique can be used to mimic any type.

Continue readingI have more than once found myself in need of a function for pretty-printing
some recursive data type; Be it a *prefix search tree*, an
*abstract syntax tree* for a *domain specific language*, XML or something else.
Getting tired of having to implement the same type of logic over and again I
decided to generalize the pattern. In the following sections I discuss the
design of a tiny library for addressing this problem. It’s not a particularly
challenging task but provides a good opportunity to touch on a few different
concepts in functional programming. Examples include *deep* and *shallow
embeddings*, monoids and *equational reasoning*. The implementation is given
in F#.