That sounds like a special case of what is called a graph in mathematics and computer science. See: http://en.wikipedia.org/wiki/Graph_%28mathematics%29 and http://en.wikipedia.org/wiki/Graph_%28data_structure%29 Essentially, the structure that they define on that site is a graph with arcs labelled in such a way that any vertex has at most one outgoing arc with that label (and hence at most one incoming arc with that label as well). There are a number of graph libraries for Haskell, including two which come with GHC. The relevant modules are Data.Graph and Data.Graph.Inductive(.*), the latter of which is quite extensive (though many of the identifiers it exports are unfortunately poorly named). Data declarations in Haskell allow you to define recursive data structures, but graphs are not quite so directly represented from that perspective. Normally, one thinks of a graph as a set of vertices, together with a set of edges. A number of tactics for storing these sets can be considered -- from using balanced binary trees, to arrays, to an inductive trace of the graph structure, building it up, one vertex, together with a collection of adjacent edges at a time. For a better explanation of that last view, which by no coincidence at all happens to be the one that Data.Graph.Inductive uses, see: Inductive Graphs and Functional Graph Algorithms http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01 For set and finite map types, see Data.Set and Data.Map, which are very well designed libraries for those purposes. There are also arrays, both immutable and mutable, see Data.Array.IArray and Data.Array.MArray respectively for the abstract interfaces to these, and the surrounding modules for implementations with a wide variety of characteristics. The documentation for the hierarchical libraries included with GHC is at: http://www.haskell.org/ghc/docs/latest/html/libraries/index.html As for enforcing your particular invariants on the graph, you'll probably want to create special functions for manipulating the graph structure that ensure that these invariants are maintained -- use a newtype or data declaration to create the data type they will act on, and don't export the data constructors, only the functions used to create structures of that type. This way, the user has no way to create values of your type that are inconsistent with your invariants (in this case, you want to enforce the constraint that each vertex has at most one outward arc with a given label) hope this helps - Cale On 22/12/05, Brian McQueen wrote:

I'm curious what this user community would come up with in order to implement the curious zigzag data structure. If you haven't heard anything about it, its a simple but peculiar idea, by the guy who dreamed up the Xanadu project: http://xanadu.com/zigzag/. Conceptually it is "cells" with some sort of value, where each cell has any number of connections to any other cell, but the connections are conceptually labeled/grouped as though they were dimensions. So a cell with the value "Brian McQueen" would have a link to "dorky guy" in the Description dimension, and a link to "519 S. Frances" in the Street Address dimension. Obviously most people would have links in those same dimensions passing through their own name's cell. My cell might have a pointer to "Hector" in the Hero dimension while a conceited man might have a link right back to itself in that same Hero direction. So the structure is very flexible. There are interesting examples on the web site of a Day Planner type of an app where each day has a time line and each time has appointments and the appointments have attendees and they all have personal contact information ... But its all logically linked.

I imagine it would be something like this in C-like code:

struct cell { value; ptr_to_links }; struct link { { dimension; ptr_to_destination; ptr_to_link; }; struct dimension { name; id; } ;

As I write this I realise that I don't remember much, if any, discussion in this group about data structures. I may be starting with a non-functional way of thinking.

BTW I'm mostly still at the reading Haskell and fiddling with ghci phase.

Brian McQueen _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Brian McQueen wrote:

I'm curious what this user community would come up with in order to implement the curious zigzag data structure.

My attempt is attached. I have not tested it beyond checking that it typechecks. However, the data structure in itself is not very interesting; what made ZigZag an attractive idea was that it was a platform: the ZZstructure was combined with a user interface based on novel ideas in visualization. Please note that ZigZag is trademarked and patented.

I imagine it would be something like this in C-like code:

struct cell { value; ptr_to_links }; struct link { { dimension; ptr_to_destination; ptr_to_link; }; struct dimension { name; id; } ;

You might want to look at how GZigZag (later called Gzz) implemented it, if you want a C-ish idea, It's in Java, but the ideas are not Java specific. Disclaimer: I was one of the Gzz developers. Later, the project was killed by the patent; the people still involved with it then switched to RDF and is now known as Fenfire.