CODEWITHSUNDEEP
haskelldata-structures
talex
talex

Reputation: 20455

Suggestions for graph-like data structure

I need data structure to represent graph like model.

Two operation on performed the most is:

What is best data structure to represent this model?

EDIT

I will use it as part of my compiler. This model represent computation where nodes are computation blocks and links is data passed between them.

I need to build this model from source code. This is why I need combine operation. I will process source code statement-by-statement and adjust model adding new computation steps.

Also I want to "optimize" my computation with various heuristics. This is why I need replace part of this graph by more optimized graph (optimization itself is out of the scope of the question, but I need "replace" operation).

Upvotes: 1

Views: 213

Answers (3)

Jeremy List
Jeremy List

Reputation: 1766

You actually have a lot of freedom to do what you want here: the main issue to work around is that plain ADTs don't give you mutable references. Here are a few examples that you might use to get started. You may even wish to use more than one and convert between them.

-- Here we have a pair of int indexed maps: the first one associates each
-- vertex index with a vertex value and a list of edge indices, and the
-- second one associates each edge index with an edge value and a pair of
-- vertex indices.
data Graph e v = Graph (M.Map Int (v, [Int])) (M.Map Int (e,Int,Int))

-- Here we use mutable references
newtype Graph s e v = Graph (STRef s (v,[(e,Graph s e v)]))

-- Here we use a single map and assume each vertex value is unique
newtype Graph e v = Graph (M.map v [(e,v)])

-- Single map again: but using ints to distinguish the vertices
newtype Graph e v = Graph (M.map Int (v,[(e,Int)]))

Upvotes: 1

trevor cook
trevor cook

Reputation: 1600

Using a combination of Haskells module system and a newtype constructor, define a newtype which wraps a graph but don't export its constructor from the module. Instead of providing the constructor, provide methods to construct and work with your graph-like structure that enforce the required invariants. It would look something like this:

module SpecialGraph 
  ( SpecialGraph --not e.g. SpecialGraph(..)
  , specialGraph) where

import Graph

newtype SpecialGraph = Sg Graph 

specialGraph :: Graph -> Maybe SpecialGraph
specialGraph gr = ...

The underlying Graph library on which you would base your new type could be one of several libraries found in Hackage. I have used fgl, "The Functional Graph Library", and like it.

In your compiler, you would import this module and work with SpecialGraph via the functions it provides.

This is a standard approach to solving problems which don't have an easy ADT-only representation. The general idea here is that we restrict a more general data structure at the term level (normal haskell expressions). The fgl graphs are implemented similarly, being restrictions and utilities on different kinds of Maps, which in turn (i believe) are based on restrictions and utilities on underlying trees.

Upvotes: 0

luqui
luqui

Reputation: 60463

Here's an indirect answer. The vagueness of your question indicates you might be new to Haskell, forgive me if I have assumed wrong.

Graphs are not so nice to work with in pure FP, especially compared to how nice algebraic data types (ADTs) are to work with. ADTs are the usual way to represent abstract syntax, which is in turn what compilers usually manipulate and optimize (until you start generating machine code, where graphs do start to come into play more).

Here is a ADT for a very simple imperative language to whet your appetite:

data Statement
    = Assign String Expr
    | Print Expr
    | If Expr Statement Statement
    | Block [Statement]

data Expr
    = Variable String
    | Add Expr Expr
    | Multiply Expr Expr
    | Constant Integer

The usual way to do a language is to define a type like this corresponding to the capabilities of your language, and organize most of the work around this type. You use a parser to get from real source code to this representation.

I have heard good things about Write Yourself A Scheme in 48 Hours both as an introduction to Haskell and as a simple implementation of a programming language using the standard tools.

Beyond that, Implementing Functional Languages: A Tutorial (by Simon Peyton Jones, the main guy behind GHC, and David Lester) goes into a lot more of the nitty gritty detail about implementing specifically Haskell-like languages. It's from 1992, and the language has evolved a lot, as well as new techniques discovered since then, but the book should still give a lot of guidance.

Good luck!

Upvotes: 0

Related Questions