[Haskell-cafe] traversing a tree using monad.cont
Luke Palmer
lrpalmer at gmail.com
Fri May 1 23:35:22 EDT 2009
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
More information about the Haskell-Cafe
mailing list