How to "insert" a cross reference into a tree structure
Hi Haskellers, since I learned the basics of algebraic data types, I have a question. First I thought I could answer it after getting a little more used to Haskell's type system. But now I prefer to ask here. Given the following example code, how can I "insert" a cross reference from the track "Money for Nothing" to the artist "Sting" who sang the background vocals? I know it must be a new MusicCollection, but I'd like to know the shortest general code to construct it. data MusicCollection = MusicCollection [Artist] deriving (Show) data Artist = Artist String [Album] deriving (Show) data Album = Album String [Track] deriving (Show) data Track = Track String [Artist] -- featured Artists are cross referenced, so Show cannot be derived collection = MusicCollection [direStraits, sting] direStraits = Artist "Dire Straits" [brothersInArms] brothersInArms = Album "Brothers in Arms" [moneyForNothing] moneyForNothing = Track "Money for Nothing" [] Thanks in advance Tim
I missed the definition of sting: sting = Artist "Sting" []
You can do this, but with some caveats; the technique is called tying the knot [1]. However, if you decide to go subsequently change an Artist, any recursive references to it must be updated too, and you will get very slow update.
collection = MusicCollection [direStraits, sting] direStraits = Artist "Dire Straits" [brothersInArms] brothersInArms = Album "Brothers in Arms" [moneyForNothing] moneyForNothing = Track "Money for Nothing" [direStraits]
Is fine, laziness stops the infinite loop. Related to editing values embedded deep in structures, but not related to cross-references, you might find this post interesting: http://conal.net/blog/posts/semantic-editor-combinators/ Cheers, Edward [1] http://www.haskell.org/haskellwiki/Tying_the_Knot
On 19 December 2010 09:54, Edward Z. Yang
Related to editing values embedded deep in structures, but not related to cross-references, you might find this post interesting:
Zippers are another view on editing nested structures, try to find Gerard Huet's original Zipper functional pearl if you can (I think it is probably accessible via Citeseer), although the code is in OCaml its a better eplanation than the haskellwiki page. For the original problem, it may be more appealing to have cross-references outside the syntax tree and put them in a "relational structure" like a finite map (e.g. Data.Map or a variant that is better for one-to-many relations). As information then gets separated into two places, there is perhaps more book-keeping to be done than with tying-the-knot, however the book-keeping itself will be simpler.
Thanks for the answers. It seems this is a point where I can't easily translate an OO program to Haskell. I was afraid this might be the case. In my job, I work with heavy use of EMF (Eclipse Modeling Framework, for Java) which allows editing of models like the MusicCollection with generic support for features like Displaying in lists/trees, Moving, Deleting, Creating new child elements, Undo/Redo, Drag & Drop, lazyness via proxies. I'd really like to have (or even implement) something similar in Haskell, but this seems to be a very difficult task. Regards Tim
Hi Tim Trees - even complex ones like abstract syntax trees for programming languages - are straight-forward to manipulate. Its easy to manipulate simple trees, it isn't too hard to manipulate complex trees - though you might want a "boilerplate removal library" like Uniplate, Scrap-Your-Boilerplate, or even an attribute grammar (UUAG). The difficulty comes when you add links / references between parts of the tree as this turns the tree into a graph. Graph manipulation without pointers is convoluted. The "moral" is to avoid turning trees into graphs if you possibly can. Best wishes Stephen
Thanks for your help. I read the introduction to Uniplate. It looks
very interesting, just like Template Haskell does.
I think I have (again) to forget how I used trees/graphs in Java and
try to learn more about the Haskell way(s), which up to now always
were very charming.
Regards
Tim
2010/12/19 Stephen Tetley
Hi Tim
Trees - even complex ones like abstract syntax trees for programming languages - are straight-forward to manipulate. Its easy to manipulate simple trees, it isn't too hard to manipulate complex trees - though you might want a "boilerplate removal library" like Uniplate, Scrap-Your-Boilerplate, or even an attribute grammar (UUAG).
The difficulty comes when you add links / references between parts of the tree as this turns the tree into a graph. Graph manipulation without pointers is convoluted. The "moral" is to avoid turning trees into graphs if you possibly can.
Best wishes
Stephen
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
participants (3)
-
Edward Z. Yang -
Stephen Tetley -
Tim Baumgartner