<div class="gmail_quote">On Fri, May 1, 2009 at 8:47 PM, Anatoly Yakovenko <span dir="ltr">&lt;<a href="mailto:aeyakovenko@gmail.com">aeyakovenko@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
So I am trying to traverse a tree in a specific order, but i have no<br>
idea where the things that i am looking for are located, and i want to<br>
avoid explicit backtracking.  </blockquote><div><br></div><div>Though I don&#39;t fully understand what you are doing (specifically what you mean by &quot;specific order&quot;), but in a lazy language, traversals are usually simply encoded as lists.  Just write a function which returns all the leaves as a list, and filter over it.</div>
<div><br></div><div>traverse (Tree ts) = concatMap traverse ts</div><div>traverse (Leaf x) = [x]</div><div><br></div><div>I believe this simple definition has more overhead than necessary because of all the appends; a DList will be more efficient.</div>
<div><br></div><div>import qualified Data.DList as DList</div><div><br></div><div>traverse = DList.toList . traverse&#39;</div><div>  where</div><div>  traverse&#39; t (Tree ts) = DList.concat (map traverse&#39; ts)</div>
<div>  traverse&#39; t (Leaf x) = DList.singleton x</div><div><br></div><div>(DList is on hackage)</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I was thinking i could do it with the<br>
continuation monad.  Here is what i have<br>
<br>
module TestCont where<br>
import Control.Monad.Cont<br>
import Control.Monad.Identity<br>
import Control.Monad.State.Lazy<br>
<br>
--our stupid tree<br>
data Tree a = Tree [Tree a]<br>
            | Leaf a<br>
<br>
--traverse all the branches<br>
search (Tree ts) next = do<br>
   mapM_ (\ ti -&gt; (callCC (search ti))) ts<br>
   next $ ()<br>
<br>
search tt@(Leaf a) next = do<br>
   cur &lt;- lift get<br>
   case ((cur + 1) == a) of<br>
      True -&gt; do --the current leaf is what we want, update the state and return<br>
         lift $ put a<br>
         return $ ()<br>
      False -&gt; do --the current leaf is not what we want, continue<br>
first, then try again<br>
         next ()<br>
         search tt (\ _ -&gt; error &quot;fail&quot;)<br>
<br>
t1 = Leaf 1<br>
t2 = Leaf 2<br>
t3 = Tree [t1,t2]<br>
t4 = Leaf 3<br>
t5::Tree Int = Tree [t4,t3]<br>
<br>
run =  runIdentity (runStateT ((runContT $ callCC (search t5)) return) 0)<br>
<br>
it seems like next isn&#39;t quite doing what i want, because i don&#39;t<br>
think I ever try again after i call next $ () in the second clause.<br>
Any ideas?<br>
<br>
Thanks,<br>
Anatoly<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br>