CODEWITHSUNDEEP
haskell
svr
svr

Reputation: 137

Build a graph structure in haskell

I'm modelling the type information of a relational database. I would like to build the following graph:

  1. The vertices are tables.

  2. An edge exists from table A to table B for every column in A which is a foreign key to B.

This is the initial data I have for building the graph.

newtype TableName = TableName T.Text
newtype ColName = ColName T.Text
newtype ColType = ColType T.Text

type DBInfo = H.HashMap TableName TableInfo
type TableInfo = H.HashMap ColName ColInfo
data ColInfo = CISimple ColType
             -- Forms the basis for building the graph
             | CIFKey ColType TableName -- col type, referenced table

getDBInfo :: IO (DBInfo)

These are the types of the graph structure I'm expecting.

data SafeColInfo = SCISimple ColType 
                 -- This captures an edge between two tables
                 | SCIFKey ColType SafeTableInfo
type SafeTableInfo = H.HashMap TableName SafeColInfo
type SafeDBInfo = ..

I would like to write this function :

convDBInfo :: DBInfo -> Either String SafeDBInfo

convDBInfo should build the above graph. The information about t in any foreign key (CIFKey ctype t) can be found by looking up t in DBInfo. If it is not found, the input data is inconsistent and is an error.

This is fairly straightforward in an imperative language with references. However, I can't think of a way to solve this in Haskell. As I understand, this looks like a good fit for the 'Tying the knot' paradigm, but I can't seem to wrap my head around it. How do I write this function?

Upvotes: 4

Views: 185

Answers (1)

András Kovács
András Kovács

Reputation: 30103

We can tie a knot the following way:

convDBInfo :: DBInfo -> SafeDBInfo
convDBInfo dbi = safeDbi where
  safeDbi = H.map (H.map go) dbi
  go (CIFKey colName tblName) = SCIFKey colName $ safeDbi H.! tblName
  go (CISimple colName)       = SCISimple colName

We get safeDbi by mapping over the column entries in the input. The important point is that we look up the tables from safeDbi in the definition of go, so the tables in SCIFKey-s will be from the resulting hashmap.

Example:

foo :: DBInfo
foo = H.fromList [
  ("table1", H.fromList [
       ("col1", CIFKey "a" "table2")
       ]),
  ("table2", H.fromList [
       ("col2", CIFKey "b" "table1")
       ])
  ]

bar = convDBInfo foo
SCIFKey _ tbl2 = (bar H.! "table1") H.! "col1"
SCIFKey name _ = tbl2 H.! "col2"
-- name == "b"

Note though that knotty data structures are often inconvenient to use, because they are indistinguishable from lazy infinite structures, so we have to give it extra thought when we'd like to print, serialize or compare them. Most of the time explicitly keyed graphs are easier to use, and not much worse performance wise.

Upvotes: 3

Related Questions