Functional Pointers

being anti-pattern the second.

Unlike (or not), I spent some time being an accidental practitioner of functional pointers myself.  For my senior thesis (which is probably quite the source of anti-patterns if I would go back and look at the code) I had developed a small graph library.  This library had predictable types like Vertex and Edge and it also had a type called Graph and there was at this point something of a problem.  See, I would have functions like:

addEdge :: Vertex -> Vertex -> Graph -> Graph

and functions like:

exits :: Vertex -> Graph -> [Vertex]

from which it should be obvious that the actual type of interest to anything ever is Graph.  Where, however, does that leave our friend vertex?  What is a vertex?

In the case of my graph library, that was quite easy to answer:

type Vertex = Integer

That is, a Vertex, by itself, has no meaning; it exists solely as an index into a larger structure.  Upon reflection, I've become vaguely dissatisfied with this approach.  First, it means that all functions take more parameters that would seem ideal (although the use of the state monad hides this).  Second, it introduces the possibility of failure a lot of places that it wouldn't seem natural.  For example, exits (above) can return [] for two reasons: first, that the vertex genuinely has no exits; second, that the vertex does not exist in the graph passed as the second parameter.  A better type signature would have been:

exits :: Vertex -> Graph -> Maybe [Vertex]

or, following the monads-not-maybe structure:

exits :: Monad m => Vertex -> Graph -> m [Vertex]

(Along which lines allow me to indicate that while the reasons for all monads having a fail method makes a certain amount of practical sense, from a semantic sense the constraint I want here is MonadZero, which does not so much exist.)

(Another interesting result of the functional pointers pattern is that the same pointer object can refer to different things in different data structures.  Functional pointers thus more approximate relative addresses than absolute ones.)

(And finally, allow me to note that the solution

type Vertex = (Int,Graph)

which actually occured to me is deeply unsatisfactory.  What is the result of

addEdge (v,g) (v',g')

where g /= g'?)

It's worth mentioning that this problem emerges only in the domain of certain world-views that contain mutable state; if we were content that a vertex refered to a specific graph, then the Vertex data structure could contain the remainder of the graph without problems.  However, this imposes certain restrictions on mutability; in particular, the notion of adding edges becomes somewhat difficult to formulate.

However, if we are committed to have references into a changing data structure, we can at least compare the desirability of the available solutions.  The first is undoubtedly the least desirable; making both vertices and graphs first class citizens leads to obnoxious types and various preventable errors.  Encapsualting all graph access in monadic operations is a step in the right direction; then, at least the computational context in which vertices are meaningful is apparent.  However, this is still not ideal:

f = y v'
   where x   = do v <- newVertex
                  return v
         y v = do u <- newVertex
                  addEdge v u
         v'  = runGraph x

In this case, we construct a vertex in one evaluation context (corresponding to one graph), pass it into an action in a different context (corresponding to a different graph), and then use that vertex (presumably meaningless) in the other graph.  This is somewhat subtle: the important flaw is the existance of a function to extract the value from a monadic computation.  Without the runGraph function we would be fine.  On the other hand, without the runGraph function, it would also be difficult to write useful programs, since the results of graph computations would never be observable.

There is a best solution.  The ST monad, for example, supports using references within monadic computation, but attempting to extract such a reference produces a type error.  The details are complicated.

The original source of this discussion, though, was not graph libraries.  It was a different block of code, which represented one-to-many containment relationships roughly as follows:

data Thing = { thingData     :: ThingData
             , thingChildren :: [Int]
             , thingParent   :: Maybe Int }

data Thing2 = { thing2Data      :: TihngData
              , thing2Examples  :: [Int]
              , thing2Container :: Maybe Int }

data Stuff = { things  :: Map Int Thing
             , thing2s :: Map Int Thing2 }

If it is not apparent to you that the children of a thing are actually thing2s, and the examples of thing2s are in fact things, then perhaps you need a brush up on functional pointers.