Requiring that a function must be a retraction in Haskell?

Question

I'm envisioning an implementation of a monadic graph. I'll do my best to explain how it is to be constructed here.

The Graph type should be isomorphic to the following:

data Graph e v = Graph{ vertices :: [v], edges :: [(e, (v, v))] }

Where e is the edge type, and v is the vertex type, we include a list of vertices and a list of edges along with the vertices they connect.

What I'm envisioning is a monad instance of this type as follows:

instance Monad (Graph e) where
  return v = Graph v [] -- | Empty graph with one vertex
  m >>= f  = {- see below -}

I have an idea of how to implement >>= which basically takes each vertex, maps it to a new graph, and then re-connects the vertex which built each graph correspondingly based on how the original graph was connected.

For example, consider a function f which takes a vertex and produces the complete graph on two vertices (K_2) from it. Then if we bound K_2 itself to f, we'd get something like:

A----B
|    |
C    D

where the graph A----B was the original, and the graphs A----C and B----D were produced from A and B respectively. In the end, A and B need to be connected since they were connected in the original graph. Note that A and B need not be exactly the same, but they need to directly map to something in the new graph. I'm leaving out some information for simplicity (what are the edges of the graph, etc), but the main point I've noticed is that for this to actually work as a Monad instance, A needs to be directly mapped to a vertex in f A, and the same goes for B. In general, each vertex in the original graph needs to be mapped directly to a graph in the graph resulting from f.

If I'm understanding correctly, this means that f must be a retraction for some other morphism g. If it is, we can clearly join the graph by connecting each morphed vertex in its resulting graph to the morphed vertices in the others, producing a new graph of the type we want.

Mostly this is just an idea I had, but I really wanted to if there is any way to, in Haskell, require that f be a retraction? Is there a way to state this within the confines of the language in order to supply an appropriate instance of Monad for a graph, or to do this, must I say "this is really only a monad if the function you're binding to is a retraction?" I suspect the latter, but I just wanted to check.

Alternatively, I may be understanding everything wrong! Feel free to correct me or give me some thoughts of your own.

Answer 1

Like the comments say, you could use a pointed graph:

module PointedGraph where
import Control.Arrow (second)

data PointedGraph e v = PointedGraph { hops :: [(e, PointedGraph e v)], center :: v }
  deriving (Eq, Show)

instance Monad (PointedGraph e) where
  return = PointedGraph []
  PointedGraph hs c >>= f = PointedGraph (hs' ++ map (second (>>= f)) hs) c'
    where PointedGraph hs' c' = f c

connect :: PointedGraph e v -> e -> PointedGraph e v -> PointedGraph e v
connect g e g' = g { hops = (e,g') : hops g }

k2, ex :: PointedGraph String Int

k2 = connect (return 0) "original" (return 2)

ex = do
  n <- k2
  connect (return n) "derived" (return $ n + 1)

So this makes:

k2: 0 -original-> 2

ex: 0 -original-> 2
    |             |
    derived       derived
    |             |
    v             v
    1             3

Note that we have no checking for uniqueness of the vertex labels (that'd require an Eq constraint or the like) so we could easily have something like

k2 >>= const k2:

    0 -original-> 0
    |             |
    original      original
    |             |
    v             v
    2             2