Abstracting algorithms (graph depth first search)

[andrew cooke]

ps (sorry, last post on this off-topic subject) the "deep" thing about it
(which might be obvious) was that it works by providing a data structre
that fits well with existing algorithms, rather than an implementation of
the algorithms themselves.  that's not the way i normally think of a
library working (it's kind of backwards), but it really does work well...

andrew cooke said:
> 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
>
> --
> http://mail.python.org/mailman/listinfo/python-list
>
>


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