Defining (monoidal) graphs in Elm

[mroman42]

We need to define simple graphs, monoidal graphs (where we substitute the set of vertices for the free monoid over those vertices) and operations on them in Elm.

[mroman42]

First ideas:

• There are some libraries defining graphs in Elm.
• We can use an algebra of graphs, treating them as algebraic types without a canonical form. UnCAL is an algebra of graphs.
• Use a simple solution, like an adjacency lists or matrices. This is a small test of a definition of graphs using an adjacency dictionary.

module Graph
    ( Graph
    , emptyGraph
    , addNodes
    , addEdges
    , neighbors
    , adjacent
    ) where

import Dict exposing (..)
import List

-- Graph as a dictionary
type alias Label   = String
type alias Edge  a = (a,a,Label)
type alias Graph a = Dict a (Dict a Label)

emptyGraph : Graph comparable
emptyGraph = empty

adjacent : Graph comparable -> comparable -> comparable -> Bool
adjacent g x y = case (get x g) of 
                    Just adj -> member y adj
                    Nothing  -> False 

neighbors : Graph comparable -> comparable -> List comparable
neighbors g x = case (get x g) of
                    Just adj -> keys adj
                    Nothing  -> []

addNode : comparable -> Graph comparable -> Graph comparable
addNode x = insert x empty

addNodes : Graph comparable -> List comparable -> Graph comparable
addNodes = List.foldr addNode

addEdge : Edge comparable -> Graph comparable -> Graph comparable 
addEdge (x,y,l) = let adds md = case md of
                                      Just d  -> Just (insert y l d) 
                                      Nothing -> Nothing
                  in  update x adds

addEdges :  Graph comparable -> List (Edge comparable) -> Graph comparable 
addEdges = List.foldr addEdge

-- Test
testgraph = addEdges (addNodes emptyGraph [1,2,3,4]) [(1,2,"a"),(2,3,"b"),(1,3,"c")]

[mroman42]

I have found a problem trying to use dictionaries in Elm. A Dict needs the type of its keys to be comparable, and only a few primitive types are comparable. Because of that, it is not possible to use the core containers (Set, Dict) with user-defined data types. This is an open issue yet:

• elm-lang/elm-compiler#774
• elm-lang/elm-compiler#1008

In particular, that implies that the type of our nodes couldn't be arbitrary. And that would be needed in order to define monoidal graphs, where the nodes should have the structure of a free monoid.

[laughedelic]

Hi @M42! It's great that you are back on track :+1: Unfortunately, we're super-busy this week with some urgent project. I'll hopefully take a look at what you're proposing closer to the end of week.

Also, I think it will be better if you will maintain your experiments code in the repo itself (in a separate branch + pull-request). Create an elm project with managed deps and the code + examples. Then it will be easier to try it and discuss.

[eparejatobes]

@M42 my impression when I skimmed through the Elm std lib was that we will need to build everything from scratch :) I would do everything in terms of extensible records. This is bound to be more verbose, but it has the advantage of being free from the inheritance-like structure of typeclasses.

[eparejatobes]

About monoidal graphs as a presheaf category: take as objects $V, E_{i,j}$ with maps ${s_1, ... , si} : E{i,j} \to V$ and ${t_1, ... , tj} : E{i, j} \to V$. Or the opposite of that, whatever.

Then for a presheaf $G$, $G{i,j} = G(E{i,j})$ is the set of monoidal edges with $i$ inputs and $j$ outputs.

[mroman42]

Ok! I am writing the experimental definitions in the graphs branch.

• A graph definition: 2f4e35c83de649a14d0c20606f03bfae0c2b182c, 95742825d344649c9d525c0995f2213d3a2bf9d3
• A monoidal graph definition: 5d40ecb8a20ea4ba9e25dcc280f19be1cf709eac