Abstracting algorithms (graph depth first search)

[andrew cooke]

Paul Moore said:

> "andrew cooke" <andrew at acooke.org> writes:
>
>> for a "completely different" way of looking at graphs, check out martin
>> erwig's functional graph library.  it's very elegant (worth learning
>> haskell for): http://cs.oregonstate.edu/~erwig/fgl/haskell/  - even if
>> you
>> don't want to use the library, read the paper to find a new way of
>> thinking about graphs.
>
> I love Haskell, in theory, but I've never seen any "serious" Haskell
> code which hasn't made my brain explode :-) This is no exception...
>
> I'll keep the link, as one of these days I hope to understand it :-)

i don't think i understood it at all until i used it and then it was like
"oh, it's *that* simple"...

if i remember correctly it lets you view a graph as a set of points
(hidden away behind some interface) and you get to choose what point you
want to pull out of the set.  you get to specify which node in a variety
of ways that fit nicely into the "pattern matching" syntax and - magically
- you get the node, plus its connections, and the set of remaining points.
 so if you want to do depth first search you ask for whatever node you
want to start at.  what's left in the set is all the rest, plus the node
you asked for and it's connected edges.  so all you do is ask for whatever
is at the end of the first edge.  you get it and repeat...

describing it now, it doesn't sound so exciting, but it makes it very easy
to write functions that recurse over graphs (so you can define maps and
folds and all the rest of the stuff that functional programmers do).  and
despite the apparent arbitrariness of it all, and the fact that you get
persistent data structures, it's amazingly (like as good as or close to
any imperative scheme from a "big O" pov) efficient.

incidentally, there's also an ml version available somewhere on that site
(which has a more normal syntax, i guess).

andrew

-- 
http://www.acooke.org/andrew