shapely-data: a library for structuralizing Haskell data types

This was a quick, on-a-whim sort of project that ended up taking me all week, as I learned my way around template haskell. It felt like trying to make a sandwich with your feet for the first time, and was about as traumatizing.

Anyway the result is my library named shapely-data which you can get with the usual…

cabal install shapely-data

and is up on github here.

The library can be used to convert an algebraic data type into a form that replaces its constructors with a combination of (,), Either and (). See the haddocks for usage information, and implementation details.

This first 0.0 version is very raw. Please let me know if you might find this useful or have any ideas/feature-requests. If there is any interest I will polish this thing sooner rather than later.

Motivation

I wanted to demonstrate that Either and (,) are haskell’s primitive sum and product types, and to show that we can more or less represent any regular type using these in combination with the unit type (standing in for the empty constructor a.la Nothing).

So the type

data Foo a = FooPair a a
           | FooInt Int
           | FooEmpty

can be converted into

newtype ShapelyFoo a = ShapelyFoo { 
    shapelyFoo :: Either (a,a) (Either Int ())
}

The deeper motivation is that there are a lot of neat abstractions (mostly having some relation to category theory) that require some notion of sums and products, and I don’t see any better way of representing this notion in the type system. It seems most straightforward to design abstractions around (,) and Either.

Arrow gets criticized for (among other things) its explicit use of these types, but a class parameterized over the sum or product type (as in A. Megacz' “generalized arrows”) becomes complicated and the abstraction breaks down with no suitable way to talk about products and sums in general AFAICT.

So this gets at the problem from the other direction: we reduce arbitrary types to haskell’s primitive sum and product types, allowing code to be written against these types, and then “flattening” the primitive representation back onto a normal type of the same shape. I’m imagining list processing using the ArrowChoice interface on Either (a, List a) () for instance.

Ultimately maybe this can get us some of the goodness of Structural Typing for certain applications. It’s also a somewhat lighter-weight approach to generic programming, and might be useful for:

generic view functions and lenses
conversions between similarly-structured data, or “canonical representations” of types
incremental Category-level modification of data structures, e.g. with Arrow
serializing data types

…but again, I’m not an expert and this is just scratching a personal itch of mine.

TODOs

Here’s a quick list of things on my mind of things to do and questions to be answered for potential future releases:

lots of misc. polishing like handling record types, derived instances, etc.
handle constructor-less (bottom) types: data Foo
handle recursive types in some intelligent way, so that we can do conversions between e.g. a custom List a and [a]
figure out how to think about ordering of sum types: how can we make Either Int () equivalent to Either () Int during conversions? Should we?
what about “deep” conversions that also look at a constructor’s arguments?