[Haskell-cafe] Imperative graph algorithm, (tail?) recursion, and speed

[Bob Ippolito]

For the most part you shouldn't worry much about having "copies of the same
data". Since nearly everything in Haskell is immutable, copying is a pretty
rare operation. Even something like updating a Set, it seems like now you
have two distinct Sets but in fact they will share a lot of the same
internal structure.

Here are my go-to intro references for Haskell's evaluation strategy:

*
http://chimera.labs.oreilly.com/books/1230000000929/ch02.html#sec_par-eval-whnf
* https://hackhands.com/lazy-evaluation-works-haskell/

If it did turn out to be one of those situations where the cost of doing
those allocations is just too high, Haskell has mutable data structures
available, and you can hide their usage with ST. I wouldn't start there
though.


On Thu, Mar 5, 2015 at 6:45 PM, Jeffrey Brown <jeffbrown.the at gmail.com>
wrote:

> Suppose I have a general (not a tree) directed graph, and I would like to
> find all the "pure descendents" of a node N -- that is, all nodes M for
> which (1) N is an ancestor of M, and (2) every partial or maximal sequence
> of predecessors starting from M either consists entirely of descendents of
> N, or else includes N itself.
>
> I have an imperative algorithm (below) for doing that. I want to know how
> hard it would be to implement in Haskell. It's complex, but basically it
> sets up a few lists like "members of this list have had all their
> descendents processed", "members of this list have been processed but their
> descendents have not been", "members of this list have not been processed
> at all", etc. Then I iterate through the graph, moving nodes from one
> collection to the other until the "to be processed" list is empty.
>
> I would like a function Graph -> Graph that does that and does not need to
> rely on a monad. The only way I can think of involves a few mutually
> recursive functions, each of which passes not only the original graph of
> interest, but all the lists described in the previous paragraph, around to
> the others. I don't understand Haskell's evaluation strategy well enough to
> anticipate the result, but my vague sense is that a lot of copies of the
> same data would be floating around, ruining the speed of it.
>
> Python code for the algorithm:
>   def descendedOnlyFrom(gset):
>     "All Gnodes n for which every ancestry of n includes a Gnode in gset
> (which can be a set or a list)."
>     # For efficiency improvement ideas and verbose comments,
>       # see treeSearch/all.py/node.descendedOnlyFrom
>     if 1: # variables
>       # "pure" = "descended only from the calling Glist"
>       pe = set(gset) # determined Pure, yet to Explore children of
>       pf = set() # determined Pure, Finished exploring children of
>       pb = set(gset) # determined Pure, Both kinds: pe | pf
>       ud = set() # purity UnDetermined
>         # descended from root, but might have parents outside of pb
>       udp = {} # "Parents of the UnDetermined"
>         # This is a dictionary, from gnodes to sets of gnodes.
>         # The other four variables are sets.
>     while pe:
>       while pe:
>         k = 1
>         i = pe.pop();    pf.add(i)
>         for c in set(i._children()):
>           if c in pb | ud: continue # If already handled, do not repeat.
>           if set(c._parents()) <= pb:
>             pe.add(c);    pb.add(c)
>           else:
>             ud.add(c);    udp[c] = set(c._parents()) - pb
>       for i in ud:
>         ipf = udp[i] & pb # (i)'s (p)arents newly (f)ound in pb
>         if ipf:
>           udp[i] -= ipf
>           if udp[i]==set():
>             ud.remove(i);    del( udp[i] )
>             pe.add(i);       pb.add(i)
>             break
>     return pb
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150306/49e6fb72/attachment.html>