[ANN] `travesty`, monadic traversals, state monads, and suchlike on top of Core's monads

Community
1

EDIT: v0.1.3 is in OPAM, which should fix the bad outer module naming described previously.

My first OPAM package, travesty, is now in the repository :tada:

What is it?

Travesty is (yet another :upside_down_face:) implementation of monadic traversals (similar to Haskell’s Traversable typeclass), state monads and transformers, and several other container and monad extensions. Though it’s nowhere near as comprehensive as, say, BAP’s monads library, it sits on top of Core_kernel's existing Monad and Container infrastructure and tries to use similar conventions where possible.

Travesty specifically includes:

  • a Mappable signature set that captures mapping over arity-0 and arity-1 types (what Haskell would call a functor);
  • a Traversable signature set that describes map_m, a generalisation of map to Core-style monads similar to Haskell’s traverse;
  • an implementation of state transformers over Core monads, and standalone state monads;
  • some functors for deriving Core-style Containers from types with monadic traversals (since map_m over a state monad can derive fold);
  • various helper functions for building map_m over Fieldslib and Variantslib derived operations;
  • a Singleton container, which lifts a single value into a traversable container;
  • miscellaneous extensions for Core containers, and specific extensions for list and option.

Travesty is MIT licenced.

Caveat emptor: Travesty is still in pre-release (v0.1.2 at time of writing). This is because I very much expect to make breaking changes to the API. Now that it’s on OPAM, I’ll try to keep any pre-v1 breaking changes to minor version increments, but nonetheless here be dragons.

Why does this exist?

Travesty is a spin-off from some other work I’ve been doing, where the same monadic concepts kept recurring over and over again, and eventually accumulated in a utils module. I figured that it might be useful for other Core-style projects, so I spun it out.

(To be honest, I didn’t notice BAP’s monads library until after I’d done so :scream: , though I feel like Travesty has a niche for being a more ‘Core-ish’ library.)

Is there documentation?

Autogenerated API documentation is here — for now, I’ve tried to make it comprehensive in terms of describing signatures, but it’s missing examples and usage information. I’m also new to odoc, so I’m learning how to document as I go along :slightly_smiling_face:

What about contributions?

I’m very much open to contributions, be they extensions, documentation improvements, cleanups, and so on—either through issues or direct pull requests. I’m fairly new to all of this (having come from a more Haskell-y world, travesty is mostly the end result of trying to program OCaml like Haskell!), so I greatly appreciate any engagement available.

5 Likes
2

Urk, I’ve just realised that I slightly messed up the dune specification for travesty, causing it to name itself Lib instead of Travesty (note to self: name or public_name, not both). Great start :smile:

I’ll push out a fix on OPAM shortly.

EDIT: hopefully fixed now. I also managed to put this in the wrong category first time around (ecosystem instead of community), go me! :tada:

1 Like
3

This looks like super solid work! :slight_smile:
It would be really great to have some examples to see the library in action.

1 Like
4

FYI, The Monads library is also pretty Core stylish, as not only it implements the Core monad interface (that keeps changing from version to version of the Core library), but it also provides the container interface. Basically, the traversal.

1 Like
5

Tbh, the more I learn about monads, the more I’m kicking myself for not finding it and understanding it before I started work on travesty :slight_smile: Sorry!! (How I managed to skim over a library literally named after the thing I wanted, I’ll never know.)

It looks like it’s a much more faithful implementation of the swathe of category theory that I was trying to go for. (Though, looking at opam, the current shipping version targets slightly older versions of opam and core-kernel than I’m currently using for my own stuff.)

I’ll probably play around with travesty for a while, partly as a learning project (I’ve found a load of things out about OPAM and releasing that I didn’t previously know, mostly the hard way!), partly in case I can find niches that it fits into, and partly in case the particular way it goes about the monad/traversal problem appeals to anyone.

1 Like
6

Can you explain to beginners with monads what was your life before and after you found monads?
I roughly understand that monadic traversals should simplify our life when traversing a tree/structure instead of reinventing the wheel with each new structure (what I feel I’m doing…) but I’ve no experience with them.

Have a you a clear show case?
What would be the must read paper about monads/traversal monads?

7

(This is a bit of a hastily written and not very well written reply, so I’ll probably come back and clean it up later!)

Monads are a bit notorious for accumulating loads of increasingly inscrutable definitions (my favourite joke definition is ‘a monoid in the category of endofunctors’ :smile:)

The general idea, though, is that it’s a recurring (and very general!) pattern throughout functional programming where you have some sort of ‘context’ that:

  • you can put values into (often called ‘return’)
  • you can apply a function to—this function gets its argument outside of the context, but returns values that are inside it (this operation is often called ‘bind’).

In ocaml, this context becomes some type ’a M.t, and the two operations could have the type signatures

return : ‘a -> ‘a M.t
bind : ‘a M.t -> (‘a -> ‘b M.t) -> ‘b M.t

If this sounds nauseatingly general, that’s because it is. If you replace M with Or_error, then return becomes a way of lifting a successful result into the world of possibly failing computations (so, ok), and piping together such computations so that successful values flow through and any failures stop the pipeline.
You could also replace M with Option, giving the same thing but without propagating any errors. It gets even more general—lists are a monad too, for instance (here, bind is basically concat-map).

Another example, that’s probably a bit hard to describe without an example, is when M.t is actually a function (and bind and return are basically constructing functions in a higher order way). This function might take some sort of extra state—what the monad structure is doing for you here is making it easy to ignore that state until and unless you actually need it. If you’ve ever written code like let (state’, x) = f state in let (state’’, y) = g state’ in… then that’s precisely the use case. This is a good use case for the state monad.

So, what’s the big idea in taking all of these really different concepts and sticking a fancy name on them? Well, if you can define operations that work on anything with a monad structure, you can target lots of use cases with the same code—and that’s precisely why travesty (and monads, I suspect!) exist.

The main idea of travesty is that, if you write a function map_m : ‘a C.t -> (‘a -> ‘b M.t) -> ‘b C.t M.t that maps over a data structure while pushing through an arbitrary monad M, then you get:

  • mapping (just by taking ‘a M.t as ‘a—this is a valid monad too!)
  • mapping a partial function, with the ability to return None at any point and cause the whole data structure to turn into None at the end (taking M as Option);
  • mapping a possibly error-causing function, with the resulting being either the data structure on success or the first error reported on failure (taking M as Or_error etc);
  • folding and mapping at the same time (using a state monad).

The latter means that, just by writing a mapping function, you can get fold-mapping, and thus folding, and thus the whole core container definition, all through one fairly abstract but otherwise not too hairy function :slight_smile:

So, basically, the main use case I have for all of this is building data structures where I can run all sorts of possible computations over the values—they might fail, they might need to track state, or they might just not apply to the particular data—but I don’t want to have to write all of those functions from scratch. (You could maybe write a ppx to do it—and there’s fairly nice synergy between this and fieldslib/variantslib)—but this is a fairly lightweight in-language approach.

4 Likes