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
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:
Following 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
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
Lenses, 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,
A 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.
In a previous
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.
I 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