Consider alternative unfoldTreeM_BF and unfoldForestM_BF implementations

[treeowl]

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]

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]

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

[treeowl]

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 https://github.com/haskell/containers/issues/124#issuecomment-68473997.

[treeowl]

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]

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]

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

[treeowl]

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]

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.