Recursion over the structure of a type

Hi! I am building a system for monadic reference counting in Haskell. A reference is defined as:

class Reference r where
new :: a -> St s (r a)
get :: r a -> St s a
incr :: r a -> St s ()
decr :: r a -> St s ()

The problem is that I would like to automatically inspect the structure of type a, so that incr and decr also increment any references contained in a recursively. Any suggestions?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

This seems like the wrong

This seems like the wrong forum for this -- I'd take it to stackoverflow (with the Haskell tag).

Not really...

...since it is far more about generic programming than it is about Haskell. To be even more precise, I am not even using Haskell: I am just considering how this would be done with its type system.

In fact I was wondering mostly about:
1) converting types to a simpler representation (embedding projection?) for matching against type classes
2) generalized maps/folds

I need some help finding references and pointers!

A Rosetta stone

A Rosetta stone

And multirec, which is one take on the state-of-the-art.

Aren't PolyP, Generic

Aren't PolyP, Generic Haskell and SYBP also attempts at this?


It would seem that McBride's "the Gentle Art of Levitation", which deals with the minimal requirements to build dependent types, offers access to the mechanisms you need to do this.