Extensible records and variants indexed by a type-level Red-Black tree.

red-black-record

What's this?

A library that provides extensible records and variants, both indexed by a type-level red-black tree that maps Symbol keys to value types of any kind. The keys correspond to field names in records, and to branch names in variants. Many record functions have their variant mirror-images and viceversa.

At the term level, value types come wrapped in a type constructor of kind q -> Type, where q is the kind of value types. Typically, the type constructor will be an identity functor, but it can also be Maybe or some other Applicative for parsing, validation and so on.

If we forget about the keys and only keep the values, records are isomorphic to n-ary unlabeled products, and variants are isomorphic to n-ary unlabeled sums. The sop-core library provides such unlabeled types, along with a rich API for manipulating them. red-black-record defines conversion functions to facilitate working in the "unlabeled" world, if needed, and then coming back to records and variants.

There is another world towards which bridges must be built: the everyday Haskell world of conventional records and sums. In fact, one of the motivations of extensible records and variants is to serve as "generalized" versions of vanilla data types. Advanced use cases can rely on these generalized versions, thereby avoiding intrusive changes to the original types. red-black-record provides conversion typeclasses with default implementations by way of GHC.Generic.

For examples on how to use the library, check the haddocks for the Data.RBR.Examples module.

FAQ

What extensions do I need to use this library?

• DataKinds.

• TypeApplications to be able to specify field and branch names.

• TypeFamilies.

• FlexibleContexts.

• DeriveGeneric for interfacing with normal records.

• PartialTypeSignatures for hiding complex tree types.

My type signatures are getting big and scary because of those type-level trees. What to do?

The -XPartialTypeSignatures extension can help with that, in combination with the -Wno-partial-type-signatures GHC flag that disables the warning message emitted when the underscore is encountered in a signature.

The flag can be set globally in the ghc-options section of the .cabal file, and also for particular modules with the OPTIONS_GHC file-header pragma.

The Show instance for record doesn't show any field names.

The field names exist only at the type level. Also, the Show instance uses n-ary products and sums from sop-core, which do not have field labels.

For fancier output, use the "pretty-show" functions instead.

Working with two records, I'm getting errors about incompatible types even as both records have the exact same fields.

Alas, the order of insertion in the type-level tree matters :( Different insertion orders can produce structurally different trees, even as they encode the same symbol-to-type map.

As a workaround, one can use the -Subset functions to convert between equivalent structures.

I can't insert into a record when a field with the same name but different type already exists. Why not simply overwrite it?

That limitation was intentional, because allowing it would make impossible to implement of widen for Variant. One solution is to explicitly delete the field and then insert it again.

The library doesn't use Proxy and relies on type application instead. But what’s the order of the type parameters?

For standalone functions, it’s the order in which the type variables appear in the forall.

What's the deal with all those -I suffixed versions of functions?

This library aims to provide HKD-like functionality by wrapping all the fields of a record in a type constructor.

But sometimes we are working with "pure" records without effects, and we just want to get and set a field's value. In that case, the type constructor that wraps each field will be an identity functor I (from sop-core). The -I suffixed functions wrap and unwrap the field's value on behalf of the user.

What's the deal with all those -Subset suffixed versions of functions?

These functions target multiple fields or branches at the same time. They can be used to build lawful lenses and prisms over fragmenst of a structure.

They can also be used to convert between type-level trees that have the same entries but different structure.

What about compilation times?

Compilation times balloon for large records. In the tests folder there's an example (not run by default in the tests) of the construction of a 50-field record whose fields are afterwards accessed one by one. It takes about 22 seconds to compile in my machine.

Code involving deletion of fields and branches (like using the winnow function for Variants) is currently poorly optimized and will compile slower than that.

The default generics-based implementations of FromRecord and FromVariant use the same type-level machinery as the getters and its use will likely slow down compilation as well.

Inspirations

• The code for the red-black tree has been lifted from Stefan Kahrs's code available here. See also this post.

• Besides depending on sop-core, I have copied and adapted code from it. In particular the KeysValuesAll typeclass is a version of the All typeclass from sop-core.

• Surgery for data types. reddit.

Alternatives

• generics-sop and records-sop. Like red-black-record, both of these libraries build upon sop-core. They are in fact written by the same author of sop-core. generics-sop can provide sum-of-products representations of any datatype with a Generic instance (red-black-record is more limited, it only converts types that fit the named record or variant mold—so no types with anonymous fields for example).

  If you don't need to explicitly target individual fields in the generic representation, you'll be better off using generics-sop instead of red-black-record.

  On top of generics-sop, records-sop provides named field accessors and record subtyping based on a type-level list of fields (unlike the type-level tree used by red-black-record). It doesn't seem to provide variants.

• superrecord. This library provides very efficient field access at runtime because the fields are backed internally by an array. Uses a sorted type-level list of fields, to avoid the problems of multiple orderings of the same fields.

• vinyl. One of the oldest and more fully-featured extensible records libraries. Uses a type level list of fields. The fields' values are wrapped in a type constructor, like in sop-core. The records seem to use an auxiliary sum type that serves as a "code" for the fields. See also vinyl-genercics.

• HTree. Another implementation of extensible records using type-level red-black trees.

• megarecord. Seems to be a proof-of-concept for a future row polymorphism extension for Haskell.

• generic-data-surgery. Lots of useful machinery for manipulating generic representations of dataytpes, without requiring intrusive changes to the original representation.

• Coxswain.

• higgledy. Provides you with HKD versions of normal records.

• Flay Work generically on your datatype without knowing its shape nor its contents.