Haskell-Cafe: I have been working on the following idea, and would appreciate any comments on the novelty or usefulness in your own applications. A scan of the usual Haskell documents turns up lots of clever data structures, but nothing particularly enlightening for graphs. Here is my attempt: Graphs are difficult to represent in functional languages because they express arbitrary undirected connectivity between nodes, whereas functional code naturally expresses directed trees. Most functional algorithms for graphs use an edge-list with global labels. Although effective, this method loses compositionality and does not exploit the type system for enforcing graph invariants such as consistency of the edge list. This note presents a functional method for constructing a local representation for undirected graphs functionally as compositions of other graphs. The resulting data structure does not use unique node labels, but rather allows edge traversal from any node to its neighbor through a lookup function. Graph traversal then emerges as a discussion among static nodes. I have found this method useful for assembling sets of molecules in chemical simulations. It's also an interesting model for framing philosophical questions about the measurement problem in quantum physics. As a disclaimer, although it is useful for constructing graphs, it is not obvious how common operations like graph copying or node deletion could be performed. This note does not discuss how to implement any graph algorithms.
import qualified Prelude import Prelude hiding ((.)) import Data.Semigroup(Semigroup,(<>)) import Data.Tuple(swap)
First, I change the meaning of "." to be element access. I think this is a cleaner way to work with record data, and suggest that there should be a special way to use this syntax without making accessor names into global variables.
infixl 9 . a . b = b a -- switch to member access
Every subgraph has open ends, which we just number sequentially from zero. The lookup function provides the subgraph's window to the outside world. Its inputs reference outgoing connections. A subgraph, built as a composite of two subgraphs, will have the job of providing the correct lookup environment to both children.
type Conn = Int newtype Lookup l = Lookup ( Conn -> (l, Lookup l) )
The tricky part is making the connections between the internal and external worlds. For the internal nodes to be complete, they must have access to complete external nodes. The problem is reversed for the external nodes. A naive idea is to represent a graph using a reader monad parameterized over label and result types (l,r). -- newtype Grph l r = Reader (Int -> (l, Lookup)) r Unfortunately, this breaks down because the outside world also needs to be able to `look inside' the subgraph. The above approach runs into trouble when constructing the lookup function specific to each child. That lookup function needs the outside world, and the outside world can't be completed without the ability to look inside! We capitulate to this symmetry between the graph and its environment by using a representation of a subgraph that provides both a top-down mechanism for using the graph as well as a bottom-up representation of the subgraph to the outside world.
data Grph l r = Grph { runGrph :: Lookup l -> r, self :: Conn -> Lookup l -> (l, Lookup l), nopen :: Int }
The default action of `running' a graph is to run a local action on each node. That local function has access to the complete graph topology via the lookup function. Since we expect this to be a fold, the result type will probably be a monoid, or at least a semigroup. Any sub-graph can be run by specifying what to do with incomplete connections. At the top-level, there should not be `open' connections.
--run g = (g.runGrph) $ Lookup (\ _ -> error "Tried to go out of top-level.") run g = (g.runGrph) $ u where u = Lookup $ \ _ -> ("end", u)
Individual nodes are themselves subgraphs. Nodes must specify how many external connections can be made, as well as an arbitrary label and an action.
node :: Int -> l -> ((l, Lookup l) -> r) -> Grph l r node n l run = Grph (\e -> run (l, e)) (\_ e -> (l, e)) n
Arbitrary graphs are constructed by joining two subgraphs. The key here is the construction of separate lookup environments for the each subgraph. The left subgraph can be connected to the first few openings in the environment or to the right subgraph. The right subgraph can connect to the last few openings of the environment, or to the left subgraph. Each time an edge is traversed, a series of "env" calls are made -- sweeping upward until an internal connection happens. Then a downward sweep of "self" calls are made. This takes at best O(log|nodes|) operations. Connections are specified by (Conn,Conn) pairs, so we need the ability to lookup from the permutation or else to return the re-numbering after subtracting connections used by the permutation.
type Permut = [(Conn, Conn)] find_fst :: Conn -> Permut -> Either Conn Conn find_fst = find1 0 where find1 n a ((a',b):tl) | a == a' = Left b -- internal find1 n a ((a',_):tl) | a' < a = find1 (n+1) a tl find1 n a (_:tl) = find1 n a tl find1 n a [] = Right (a-n) -- external find_snd b p = find_fst b (map swap p)
-- append 2 subgraphs append :: (Semigroup r) => Permut -> Grph l r -> Grph l r -> Grph l r append p x y = Grph { runGrph = \(Lookup env) -> (x.runGrph) (e1 env) <> (y.runGrph) (e2 env), self = down, nopen = (x.nopen) + (y.nopen) - 2*(length p) } where down n (Lookup env) | n < ystart = (x.self) n (e1 env) down n (Lookup env) = (y.self) (n-ystart) (e2 env) e1 env = Lookup $ \n -> case find_fst n p of Right m -> env m Left m -> (y.self) m (e2 env) e2 env = Lookup $ \n -> case find_snd n p of Right m -> env (m+ystart) Left m -> (x.self) m (e1 env) ystart = (x.nopen) - length p -- start of b's env. refs
This is a helper function for defining linear graphs.
instance Semigroup r => Semigroup (Grph l r) where (<>) = append [(1,0)]
A simple action is just to show the node labels and the labels of each immediate neighbor.
show_node (l, Lookup env) = " " ++ show l show_env (l, Lookup env) = show l ++ foldl (++) (":") (map (\u -> show_node(env u)) [0, 1]) ++ "\n"
The following example graphs are a list of 4 single nodes, two incomplete 2-member chains, and a complete 4-member cycle. The key feature here is that that the graphs are all composable.
c6 = [ node 2 ("C"++show n) show_env | n <- [1..4] ] str = c6!!0 <> c6!!1 str' = c6!!2 <> c6!!3 cyc = append [(1,0), (0,1)] str str' -- Tying the knot. main = putStrLn $ run cyc
The connection to the measurement problem in quantum physics comes out because the final output of running any graph is deterministic, but can depend nontrivially on the graph's environment. Like links in the graph, physical systems communicate through their mutual interactions, and from those determine a new state a short time later. In a closed universe, the outcome is deterministic, while for any an open system (subgraph), the outcome is probabilistic. The analogy suggests that understanding how probabilities emerge in the measurement problem requires a two-way communication channel between the system and its environment. ~ David M. Rogers