unfoldForestM and friends can't specialize

[meooow25]

unfoldForestM and friends are missing INLINABLE pragmas.

containers/containers/src/Data/Tree.hs

Lines 503 to 536 in 0c3b9ee

	-- | Monadic tree builder, in depth-first order.
	unfoldTreeM :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
	unfoldTreeM f b = do
	(a, bs) <- f b
	ts <- unfoldForestM f bs
	return (Node a ts)
	-- | Monadic forest builder, in depth-first order.
	unfoldForestM :: Monad m => (b -> m (a, [b])) -> [b] -> m ([Tree a])
	unfoldForestM f = Prelude.mapM (unfoldTreeM f)
	-- | Monadic tree builder, in breadth-first order.
	--
	-- See 'unfoldTree' for more info.
	--
	-- Implemented using an algorithm adapted from
	-- /Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design/,
	-- by Chris Okasaki, /ICFP'00/.
	unfoldTreeM_BF :: Monad m => (b -> m (a, [b])) -> b -> m (Tree a)
	unfoldTreeM_BF f b = liftM getElement $ unfoldForestQ f (singleton b)
	where
	getElement xs = case viewl xs of
	x :< _ -> x
	EmptyL -> error "unfoldTreeM_BF"
	-- | Monadic forest builder, in breadth-first order.
	--
	-- See 'unfoldForest' for more info.
	--
	-- Implemented using an algorithm adapted from
	-- /Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design/,
	-- by Chris Okasaki, /ICFP'00/.
	unfoldForestM_BF :: Monad m => (b -> m (a, [b])) -> [b] -> m ([Tree a])
	unfoldForestM_BF f = liftM toList . unfoldForestQ f . fromList

I was looking at alga and noticed that it uses unfoldForestM_BF to implement breadth-first search (https://hackage-content.haskell.org/package/algebraic-graphs-0.8/docs/src/Algebra.Graph.AdjacencyMap.Algorithm.html#bfsForest). It was nice to see unfoldForestM_BF used in the wild, followed by the realization that it is not being specialized for State.

[meooow25]

Side note: It's a shame that dfs cannot be implemented using unfoldForestM, though bfs can be implemented using unfoldForestM_BF. The issue is that we have unfoldForestM :: Monad m => (b -> m (a, [b])) -> [b] -> m [Tree a] and the b -> m (a, [b]) demands all the children at once. For dfs, we know the neighbors of a vertex right away, but a neighbor needs to be excluded from being a child if it is already visited by the time we reach it while processing the list of neighbors.

To make it work we would need to replace the list [b] with some form of monadic stream, but there is no such thing in base so we are out of luck. There is the option of representing the stream as m (Maybe b), but I'm not sure if I like that...