[Haskell-cafe] zigzag data structure

[Cale Gibbard]

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 <mcqueenorama at gmail.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>