I spent four hours investigating this problem! Thank you very much for the excellent brainfood, and challenging Haskell's claim to be rawkin' at parallelism. I think, though it took much experimentation, that I have confirmed that it is :-)<br>
<br>On Sun, Feb 1, 2009 at 9:26 PM, John D. Ramsdell <<a href="mailto:ramsdell0@gmail.com">ramsdell0@gmail.com</a>> wrote:<br>><br>> I have a reduction system in which a rule takes a term and returns a<br>> set of terms.<br>
> The reduction system creates a tree that originates at a starting<br>> value called the root.<br>> For most problems, the reduction system terminates, but a step count<br>> limit protects<br>> from non-termination.<br>
<br>That's typically a bad idea. Instead, use laziness to protect from nontermination. For example, in this case, we can output a collection of items lazily, and then take a finite amount of the output (or check whether the output is longer than some length), without having to evaluate all of it.<br>
<br>Here's my writeup of my solution, in literate Haskell. It doesn't output the exact same structure as yours, but hopefully you can see how to tweak it to do so.<br><br><pre><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Blue">{-# LANGUAGE RankNTypes #-}</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> <br></font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> </font><font size="4" color="Green"><u>qualified</u></font><font size="4"> Data</font><font size="4" color="Cyan">.</font><font size="4">MemoCombinators </font><font size="4" color="Green"><u>as</u></font><font size="4"> Memo<br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> </font><font size="4" color="Green"><u>qualified</u></font><font size="4"> Data</font><font size="4" color="Cyan">.</font><font size="4">Set </font><font size="4" color="Green"><u>as</u></font><font size="4"> Set<br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> Control</font><font size="4" color="Cyan">.</font><font size="4">Parallel </font><font size="4" color="Cyan">(</font><font size="4">par</font><font size="4" color="Cyan">)</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> </font><font size="4" color="Green"><u>qualified</u></font><font size="4"> Control</font><font size="4" color="Cyan">.</font><font size="4">Parallel</font><font size="4" color="Cyan">.</font><font size="4">Strategies </font><font size="4" color="Green"><u>as</u></font><font size="4"> Par<br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> Data</font><font size="4" color="Cyan">.</font><font size="4">Monoid </font><font size="4" color="Cyan">(</font><font size="4">Monoid</font><font size="4" color="Cyan">(</font><font size="4" color="Red">..</font><font size="4" color="Cyan">)</font><font size="4" color="Cyan">)</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> Control</font><font size="4" color="Cyan">.</font><font size="4">Monad</font><font size="4" color="Cyan">.</font><font size="4">State<br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> </font><font size="4" color="Green"><u>qualified</u></font><font size="4"> Data</font><font size="4" color="Cyan">.</font><font size="4">DList </font><font size="4" color="Green"><u>as</u></font><font size="4"> DList<br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> Debug</font><font size="4" color="Cyan">.</font><font size="4">Trace<br></font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>import</u></font><font size="4"> Control</font><font size="4" color="Cyan">.</font><font size="4">Concurrent</font><br>
</pre>
First, I want to capture the idea of a generative set like you're doing.
GenSet is like a set, with the constructor "genset x xs" which says
"if x is in the set, then so are xs".
I'll represent it as a stateful computation of the list of things we've
seen so far, returning the list of things we've seen so far. It's
redundant information, but sets can't be consumed lazily, thus the
list (the set will follow along lazily :-).
Remember that State s a is just the function (s -> (s,a)). So we're
taking the set of things we've seen so far, and returning the new
elements added and the set unioned with those elements.
<pre><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>newtype</u></font><font size="4"> GenSet a <br></font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Red">=</font><font size="4"> GenSet </font><font size="4" color="Cyan">(</font><font size="4">State </font><font size="4" color="Cyan">(</font><font size="4">Set</font><font size="4" color="Cyan">.</font><font size="4">Set a</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Cyan">(</font><font size="4">DList</font><font size="4" color="Cyan">.</font><font size="4">DList a</font><font size="4" color="Cyan">)</font><font size="4" color="Cyan">)</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> <br></font><font size="4" color="Cyan">></font><font size="4"> genset </font><font size="4" color="Red">::</font><font size="4"> </font><font size="4" color="Cyan">(</font><font size="4">Ord a</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Red">=></font><font size="4"> a </font><font size="4" color="Red">-></font><font size="4"> GenSet a </font><font size="4" color="Red">-></font><font size="4"> GenSet a<br>
</font><font size="4" color="Cyan">></font><font size="4"> genset x </font><font size="4" color="Cyan">(</font><font size="4">GenSet f</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Red">=</font><font size="4"> GenSet </font><font size="4" color="Cyan">$</font><font size="4"> </font><font size="4" color="Green"><u>do</u></font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> seen </font><font size="4" color="Red"><-</font><font size="4"> gets </font><font size="4" color="Cyan">(</font><font size="4">x </font><font size="4" color="Cyan">`</font><font size="4">Set</font><font size="4" color="Cyan">.</font><font size="4">member</font><font size="4" color="Cyan">`</font><font size="4" color="Cyan">)</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>if</u></font><font size="4"> seen<br></font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>then</u></font><font size="4"> return mempty<br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>else</u></font><font size="4"> fmap </font><font size="4" color="Cyan">(</font><font size="4">DList</font><font size="4" color="Cyan">.</font><font size="4">cons x</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Cyan">$</font><font size="4"> <br>
</font><font size="4" color="Cyan">></font><font size="4"> modify </font><font size="4" color="Cyan">(</font><font size="4">Set</font><font size="4" color="Cyan">.</font><font size="4">insert x</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Cyan">>></font><font size="4"> f<br>
</font><font size="4" color="Cyan">></font><font size="4"> <br></font><font size="4" color="Cyan">></font><font size="4"> toList </font><font size="4" color="Red">::</font><font size="4"> GenSet a </font><font size="4" color="Red">-></font><font size="4"> </font><font size="4" color="Red">[</font><font size="4">a</font><font size="4" color="Red">]</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> toList </font><font size="4" color="Cyan">(</font><font size="4">GenSet f</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Red">=</font><font size="4"> DList</font><font size="4" color="Cyan">.</font><font size="4">toList </font><font size="4" color="Cyan">$</font><font size="4"> evalState f Set</font><font size="4" color="Cyan">.</font><font size="4">empty</font><br>
</pre>
GenSet is a monoid, where mappend is just union.
<pre><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>instance</u></font><font size="4"> </font><font size="4" color="Cyan">(</font><font size="4">Ord a</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Red">=></font><font size="4"> Monoid </font><font size="4" color="Cyan">(</font><font size="4">GenSet a</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Green"><u>where</u></font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> mempty </font><font size="4" color="Red">=</font><font size="4"> GenSet </font><font size="4" color="Cyan">(</font><font size="4">return mempty</font><font size="4" color="Cyan">)</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> mappend </font><font size="4" color="Cyan">(</font><font size="4">GenSet a</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Cyan">(</font><font size="4">GenSet b</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Red">=</font><font size="4"> <br>
</font><font size="4" color="Cyan">></font><font size="4"> GenSet </font><font size="4" color="Cyan">(</font><font size="4">liftM2 mappend a b</font><font size="4" color="Cyan">)</font><br></pre>
Okay, so that's how we avoid exponential behavior when traversing
the tree. We can now just toss around GenSets like they're sets
and everything will be peachy.
Here's the heart of the algorithm: the reduce function. To avoid
recomputation of rules, we could just memoize the rule function.
But we'll do something a little more clever. The function we'll
memoize ("parf") first sparks a thread computing its *last* child.
Because the search is depth-first, it will typically be a while
until we get to the last one, so we benefit from the spark
(you don't want to spark a thread computing something you're
about to compute anyway).
<pre><font size="4" color="Cyan">></font><font size="4"> reduce </font><font size="4" color="Red">::</font><font size="4"> </font><font size="4" color="Cyan">(</font><font size="4">Ord a</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Red">=></font><font size="4"> Memo</font><font size="4" color="Cyan">.</font><font size="4">Memo a </font><font size="4" color="Red">-></font><font size="4"> </font><font size="4" color="Cyan">(</font><font size="4">a </font><font size="4" color="Red">-></font><font size="4"> </font><font size="4" color="Red">[</font><font size="4">a</font><font size="4" color="Red">]</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Red">-></font><font size="4"> a </font><font size="4" color="Red">-></font><font size="4"> </font><font size="4" color="Red">[</font><font size="4">a</font><font size="4" color="Red">]</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> reduce memo f x </font><font size="4" color="Red">=</font><font size="4"> toList </font><font size="4" color="Cyan">(</font><font size="4">makeSet x</font><font size="4" color="Cyan">)</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>where</u></font><font size="4"><br></font><font size="4" color="Cyan">></font><font size="4"> makeSet x </font><font size="4" color="Red">=</font><font size="4"> genset x </font><font size="4" color="Cyan">.</font><font size="4"> mconcat </font><font size="4" color="Cyan">.</font><font size="4"> map makeSet </font><font size="4" color="Cyan">.</font><font size="4"> f' </font><font size="4" color="Cyan">$</font><font size="4"> x<br>
</font><font size="4" color="Cyan">></font><font size="4"> f' </font><font size="4" color="Red">=</font><font size="4"> memo parf<br></font><font size="4" color="Cyan">></font><font size="4"> parf a </font><font size="4" color="Red">=</font><font size="4"> </font><font size="4" color="Green"><u>let</u></font><font size="4"> ch </font><font size="4" color="Red">=</font><font size="4"> f a </font><font size="4" color="Green"><u>in</u></font><font size="4"> <br>
</font><font size="4" color="Cyan">></font><font size="4"> ch </font><font size="4" color="Cyan">`seq`</font><font size="4"> </font><font size="4" color="Cyan">(</font><font size="4">f' </font><font size="4" color="Cyan">(</font><font size="4">last ch</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Cyan">`par`</font><font size="4"> ch</font><font size="4" color="Cyan">)</font><br>
</pre>
The ch `seq` is there so that the evaluation of ch and last ch
aren't competing with each other.
Your example had a few problems. You said the rule was supposed
to be expensive, but yours was cheap. Also, [x-1,x-2,x-3] are
all very near each other, so it's hard to go do unrelated stuff.
I made a fake expensive function before computing the neighbors,
and tossed around some prime numbers to scatter the space more.
<pre><font size="4" color="Cyan">></font><font size="4"> rule </font><font size="4" color="Red">::</font><font size="4"> Int </font><font size="4" color="Red">-></font><font size="4"> </font><font size="4" color="Red">[</font><font size="4">Int</font><font size="4" color="Red">]</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> rule n </font><font size="4" color="Red">=</font><font size="4"> expensive </font><font size="4" color="Cyan">`seq`</font><font size="4"> <br></font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Red">[</font><font size="4">next </font><font size="4" color="Magenta">311</font><font size="4"> </font><font size="4" color="Magenta">4</font><font size="4" color="Cyan">,</font><font size="4"> next </font><font size="4" color="Magenta">109</font><font size="4"> </font><font size="4" color="Magenta">577</font><font size="4" color="Cyan">,</font><font size="4"> next </font><font size="4" color="Magenta">919</font><font size="4"> </font><font size="4" color="Magenta">353</font><font size="4" color="Red">]</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>where</u></font><font size="4"><br></font><font size="4" color="Cyan">></font><font size="4"> next x y </font><font size="4" color="Red">=</font><font size="4"> </font><font size="4" color="Cyan">(</font><font size="4">x </font><font size="4" color="Cyan">*</font><font size="4"> n </font><font size="4" color="Cyan">+</font><font size="4"> y</font><font size="4" color="Cyan">)</font><font size="4"> </font><font size="4" color="Cyan">`mod`</font><font size="4"> </font><font size="4" color="Magenta">5000</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> expensive </font><font size="4" color="Red">=</font><font size="4"> sum </font><font size="4" color="Red">[</font><font size="4" color="Magenta">1</font><font size="4" color="Red">..</font><font size="4" color="Magenta">50</font><font size="4" color="Cyan">*</font><font size="4">n</font><font size="4" color="Red">]</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> <br></font><font size="4" color="Cyan">></font><font size="4"> main </font><font size="4" color="Red">::</font><font size="4"> IO ()<br></font><font size="4" color="Cyan">></font><font size="4"> main </font><font size="4" color="Red">=</font><font size="4"> </font><font size="4" color="Green"><u>do</u></font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> </font><font size="4" color="Green"><u>let</u></font><font size="4"> r </font><font size="4" color="Red">=</font><font size="4"> reduce Memo</font><font size="4" color="Cyan">.</font><font size="4">integral rule </font><font size="4" color="Magenta">1</font><font size="4"><br>
</font><font size="4" color="Cyan">></font><font size="4"> print </font><font size="4" color="Cyan">(</font><font size="4">length r</font><font size="4" color="Cyan">)</font><font size="4"><br></font></pre>
The results are quite promising:
% ghc --make -O2 rules2 -threaded
% time ./rules2
5000
./rules2 13.25s user 0.08s system 99% cpu 13.396 total
% time ./rules2 +RTS -N2
5000
./rules2 +RTS -N2 12.52s user 0.30s system 159% cpu 8.015 total
That's 40% decrease in running time! Woot! I'd love to see
what it does on a machine with more than 2 cores.
<br><br>Enjoy!<br>Luke<br>