Search code examples
haskellrecursiontype-inferencerecursion-schemesfoldable

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.