[Haskell-cafe] traversing a tree using monad.cont

[Luke Palmer]

On Fri, May 1, 2009 at 8:47 PM, Anatoly Yakovenko <aeyakovenko at gmail.com>wrote:

> So I am trying to traverse a tree in a specific order, but i have no
> idea where the things that i am looking for are located, and i want to
> avoid explicit backtracking.


Though I don't fully understand what you are doing (specifically what you
mean by "specific order"), 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.

traverse (Tree ts) = concatMap traverse ts
traverse (Leaf x) = [x]

I believe this simple definition has more overhead than necessary because of
all the appends; a DList will be more efficient.

import qualified Data.DList as DList

traverse = DList.toList . traverse'
  where
  traverse' t (Tree ts) = DList.concat (map traverse' ts)
  traverse' t (Leaf x) = DList.singleton x

(DList is on hackage)

I was thinking i could do it with the
> continuation monad.  Here is what i have
>
> module TestCont where
> import Control.Monad.Cont
> import Control.Monad.Identity
> import Control.Monad.State.Lazy
>
> --our stupid tree
> data Tree a = Tree [Tree a]
>            | Leaf a
>
> --traverse all the branches
> search (Tree ts) next = do
>   mapM_ (\ ti -> (callCC (search ti))) ts
>   next $ ()
>
> search tt@(Leaf a) next = do
>   cur <- lift get
>   case ((cur + 1) == a) of
>      True -> do --the current leaf is what we want, update the state and
> return
>         lift $ put a
>         return $ ()
>      False -> do --the current leaf is not what we want, continue
> first, then try again
>         next ()
>         search tt (\ _ -> error "fail")
>
> t1 = Leaf 1
> t2 = Leaf 2
> t3 = Tree [t1,t2]
> t4 = Leaf 3
> t5::Tree Int = Tree [t4,t3]
>
> run =  runIdentity (runStateT ((runContT $ callCC (search t5)) return) 0)
>
> it seems like next isn't quite doing what i want, because i don't
> think I ever try again after i call next $ () in the second clause.
> Any ideas?
>
> Thanks,
> Anatoly
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090501/7f6f67a4/attachment.htm