How can I avoid explicit recursion in this case?

I wound up with this skeleton:

``````f :: (Monad m) => b -> m ()
f x = traverse_ (f . g x) =<< h x -- how avoid explicit recursion?
g :: b -> a -> b
-- h :: (Foldable t) => b -> m (t a) -- why "Could not deduce (Foldable t0) arising from a use of ‘traverse_’"
h :: b -> m [a]
``````

How can I avoid the explicit recursion in `f`?

Bonus: When I try to generalize `h` from `[]` to `Foldable`, `f` does not type check (`Could not deduce (Foldable t0) arising from a use of ‘traverse_’`) -- what am I doing wrong?

UPDATE: Here's the real code. The `Right` side is for recursing down directories of security camera footage whose names are integers. `Left` is the base case to process leaves whose names are not integers.

``````a <|||> b = left a . right b

doDir (Right d) = traverse_ (doDir . doInt) =<< listDirectory d
where doInt s = ((<|||>) <\$> (,) <*> const) (d </> s) \$ (TR.readEither :: String -> Either String Int) s
``````

`f = doDir` and `g ~ doInt` but got refactored a little. `h = listDirectory`. to answer the bonus, i was just being silly and wasn't seeing that i had to combine all the definitions to bind the types together:

``````f :: (Monad m, Foldable t) => (b -> a -> b) -> (b -> m (t a)) -> b -> m ()
f g h x = traverse_ (f g h . g x) =<< h x
``````

Solution

• If you don't mind leaking a bit of memory building a `Tree` and then throwing it away, you can use `unfoldTreeM`:

``````f = unfoldTreeM (\b -> (\as -> ((), g b <\$> as)) <\$> h b)
``````

I do not believe there is a corresponding `unfoldTreeM_`, but you could write one (using explicit recursion). To generalize beyond the `Tree`/`[]` connection, you might also like `refoldM`; you can find several similar functions if you search for "hylomorphism" on Hackage.