New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider alternative unfoldTreeM_BF and unfoldForestM_BF implementations #124

Open
treeowl opened this Issue Dec 31, 2014 · 8 comments

Comments

Projects
None yet
4 participants
@treeowl
Copy link
Member

treeowl commented Dec 31, 2014

These algorithms only need queues; the full power of Seq is overkill, and must necessarily slow things down. We could switch to something simpler, like Okasaki's bootstrapped queues. Alternatively, there might, perhaps, be some other algorithms that avoid the need for queues altogether.

@foxik

This comment has been minimized.

Copy link
Member

foxik commented Dec 31, 2014

It is quite late, but if I am looking correctly at it, standard queues implemented using two stacks (the ones with amortized constant complexity when used single threadedly; called BatchedQueue in Okasaki) should be enough.

@foxik

This comment has been minimized.

Copy link
Member

foxik commented Dec 31, 2014

Also, happy New Year! I am in CET, so it is exactly 0:00 here now :-).

@treeowl

This comment has been minimized.

Copy link
Member

treeowl commented Dec 31, 2014

I would be surprised if a batched queue were sufficient. What happens in
the nondeterminism (list) monad? I would be much less surprised if there
were a way to do it without queues, and I think I have an idea for
accomplishing that. Happy new year to you too!

On Wed, Dec 31, 2014 at 6:02 PM, Milan Straka notifications@github.com
wrote:

Also, happy New Year! I am in CET, so it is exactly 0:00 here now :-).


Reply to this email directly or view it on GitHub
#124 (comment).

@treeowl

This comment has been minimized.

Copy link
Member

treeowl commented Dec 31, 2014

There don't seem to be any tests for these functions, so I'm not sure if this works, but I think this is what Okasaki calls a "level-oriented" solution in the referenced paper:

unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)
unfoldForestM_BF f [] = return []
unfoldForestM_BF f bs = do
  (as', bss') <- mapAndUnzipM f bs
  return . rebuild as' bss' =<< unfoldForestM_BF f (concat bss')

rebuild :: [a] -> [[b]] -> [Tree a] -> [Tree a]
rebuild [] [] [] = []
rebuild (a:as) (bs:bss) ts = case splitAt (length bs) ts of
  (us,ts') -> Node a us : rebuild as bss ts'

Some things could obviously be cleaned up, but I think this is probably the right idea.

@treeowl

This comment has been minimized.

Copy link
Member

treeowl commented Jan 1, 2015

Here's one way to clean it up:

unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)
unfoldForestM_BF f [] = return []
unfoldForestM_BF f bs = do
  asbss' <- mapM f bs
  return . rebuild asbss' =<< unfoldForestM_BF f (concatMap snd asbss')

rebuild :: [(a,[b])] -> [Tree a] -> [Tree a]
rebuild = foldr go id
  where
    go (a,bs) r ts = case splitAt (length bs) ts of
                               (us,ts') -> Node a us : r ts'
@treeowl

This comment has been minimized.

Copy link
Member

treeowl commented Jan 1, 2015

We can/should probably also fuse the length measurement with the concatMap.

@treeowl

This comment has been minimized.

Copy link
Member

treeowl commented Mar 12, 2018

I am not convinced that may proposed implementations are the best, particularly in the monadic case. But I really want to remove the dependency of Data.Tree and Data.Graph on Data.Sequence. Why? Because Data.Sequence takes a long time to build, and this could be unnecessarily serializing GHC's build process. Let's try to investigate our options here.

@oisdk

This comment has been minimized.

Copy link
Contributor

oisdk commented Mar 13, 2018

I think you can get away just a list as a queue—based on a breadth-first traversal like this:

breadthFirst :: Forest a -> [a]
breadthFirst ts = b [ts]
  where
    f (Node x xs) fw bw = x : fw (xs:bw)

    b [] = []
    b qs = foldl (foldr f) b qs []

Maybe something like this?

unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m (Forest a)
unfoldForestM_BF f ts = b [ts] (const id)
  where
    b [] k = pure (k [] [])
    b qs k = foldl (foldr t) b qs [] (\x xs -> k [] (foldr (uncurry run) id x xs))

    t a fw bw k = do
        (x,cs) <- f a
        let !n = length cs
        fw (cs : bw) (k . (:) (x, n))

    run x n xs ys =
      case splitAt n ys of
          (cs,zs) -> Node x cs : xs zs

I think it also avoids the space leak and extra fmaps.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment