[Haskell-cafe] An easy way to represent and modify graphs?

[Takayuki Muranushi]

tl;dr: I would like to apply genetic algorithm to directed acyclic
graphs that represents arithmetic operations.

Thank you for hosts, speakers and all participants in ICFP2012. I had
chance to make a lot of questions (c.f. [prize.jpg]) and receive lots of
stimulating ideas.

I have been working on automated parallel code generation and
automated tuning for hydrodynamics
http://iopscience.iop.org/1749-4699/5/1/015003 ; one of my next target
is model acquisition in robotics:
http://creativemachines.cornell.edu/sites/default/files/moriguchi11.pdf
; both deal with computations represented in forms of directed acyclic
graphs c.f. [graph-1.png] [graph-2.png]. We would like to describe
them easily in Haskell, but also to mutate (add random changes) and
crossover (create a new graph by mixing other two graphs.) In my
previous work, I used Monad to generate graphs and used the Functional
Graph Library to explicitly modify the graphs. Now I have learned that
there are more elegant methods to describe the computations with
sharing. But are those method also enables easy editing of the graphs?
That's my question.

In [data-reify.hs] I tried Observed Sharing by Gill09. Apparently,
sharing is lost once we try to modify the graph.

$ runhaskell data-reify.hs
let [(1,GraphMul 2 2),(2,GraphAdd 3 3),(3,GraphMul 4 5),(5,GraphVar
"X"),(4,GraphVal 40)] in 1
let [(1,GraphMul 2 9),(9,GraphAdd 10 13),(13,GraphMul 14
15),(15,GraphVar "X"),...,(5,GraphVar "X"),(4,GraphVal 42)] in 1

In [GenericMain.hs] I tried PHOAS by Oliveria & Cook 2012.

$ runhaskell GenericMain.hs
Mu (
  a => Fork "Add"(Fork "Sub"(b) (Empty)) (c)
  b => Fork "Mul"(c) (c)
  c => Fork "40"(Empty) (Empty)
  d => Fork "X"(Empty) (Empty)
)
Mu (
  a => Fork "Add"(Fork "Sub"(b) (Empty)) (c)
  b => Fork "Mul"(c) (c)
  c => Fork "42"(Empty) (Empty)
  d => Fork "X"(Empty) (Empty)
)

This time, I can modify a node without loosing the sharing. How about
edges? Can you write operations such as "Choose one of the edges that
point to (c) and make it point to (d)" ?

Is there any good methods to describe and modify structures that has
sharing (if it helps, I don't need loops.)? Or, after all is the best way
explicit manipulation of the graph structure? Both information are
helpful to me.

Thanks in advance,
-- 
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graph-1.png
Type: image/png
Size: 62878 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120919/91622c8d/attachment-0002.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graph-2.png
Type: image/png
Size: 22774 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120919/91622c8d/attachment-0003.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: prize.jpeg
Type: image/jpeg
Size: 53015 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120919/91622c8d/attachment-0001.jpeg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: data-reify.hs
Type: application/octet-stream
Size: 1388 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120919/91622c8d/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: GenericMain.hs
Type: application/octet-stream
Size: 7176 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120919/91622c8d/attachment-0003.obj>