An easy way to represent and modify graphs?
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
Pointers. Seriously. In Haskell one could use STRef rather than the cumbersome Foreign.Ptr, though STRef too can be kludgy. I know not whether safe, pure, immutable pointers would be possible in Haskell, but in my experience STRef can work well enough. Cheers, Strake
Yes Pointers. I've forgotten that. I have once dealt with structures, with lots of IORefs. It was smooth and fast. Thank you for reminding me! On the other hand, use of pointers means that our values are not algebraic data type any more. We have to derive operations such as map, fold, serialize by ourselves. I can do that, but am I right? Or is there some systematic way to derive such operations? Best regards, Takayuki
On 21/09/2012, Takayuki Muranushi
Yes Pointers. I've forgotten that. I have once dealt with structures, with lots of IORefs. It was smooth and fast. Thank you for reminding me!
On the other hand, use of pointers means that our values are not algebraic data type any more. We have to derive operations such as map, fold, serialize by ourselves. I can do that, but am I right? Or is there some systematic way to derive such operations?
If you mean that one can't write "deriving (Class, ...)" then yes, to my knowledge, one can't, as it would not know to follow the pointers. I doubt that such a derivation algorithm would be possible in general, since it wouldn't know whether to compare by value, i.e. follow the pointer.
Best regards,
Takayuki
Cheers, Strake
participants (2)
-
Strake -
Takayuki Muranushi