Построение структуры графа в haskell

Question

Я моделирую информацию о типе реляционной базы данных. Я хотел бы построить следующий график:

1. Вершины являются таблицами.

2. Ребро существует из таблицы А к таблице Б для каждого столбца в А, который является внешним ключом к В.

Это исходные данные я для построения графика.

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) 

Это типы структуры графика, которую я ожидаю.

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

Я хотел бы написать эту функцию:

convDBInfo :: DBInfo -> Either String SafeDBInfo 

convDBInfo должны строить выше график. Информацию о t по любому иностранному ключу (CIFKey ctype t) можно найти, просмотрев t в DBInfo. Если он не найден, входные данные являются несогласованными и являются ошибкой.

Это довольно прямолинейный язык с обязательными ссылками. Однако я не могу придумать способ решить эту проблему в Haskell. Насколько я понимаю, это похоже на хорошую привязанность к парадигме «Связывание узла», но я не могу обернуться вокруг нее. Как написать эту функцию?

Answer 1

Мы можем связать узел следующим образом:

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 

Мы получаем safeDbi отображением над элементами столбцов во входных данных. Важным моментом является то, что мы смотрим таблицы с safeDbi в определении go, поэтому таблицы из SCIFKey-s будут получены из результирующего hashmap.

Пример:

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" 

Примечание, однако, что структуры узловатые данных зачастую неудобны в использовании, потому что они неотличимы от ленивых бесконечных структур, поэтому мы должны дать ему дополнительную мысль, когда мы хотели бы напечатать, сериализуйте или сравните их. В большинстве случаев графы с явным образом упрощены в использовании и не намного хуже.