How do I remove this type of mutual recursion?

Question

I am running into a mutual recursion issue. The basic structure I have employed is that I have a module that defines a type class and several modules that define instances of that type class. Each instance however is defined in terms of all the other instances.

If that description is a little too abstract here is some code that has a structure like my code. (I've trimmed it down quite a bit to make the necessary bits obvious and added some ellipses to parts that are not relevant to the overall structure).

My class looks like the following:

data Result = ...

class Foo a where
  openFoo  :: Result      -> IO (a, Result)
  runFoo   :: (a, Result) -> IO (a, Result)
  closeFoo :: (a, Result) -> IO Result

Then I have the instances

data XData = ...

instance Foo XData where
   openFoo result = ...
   runFoo (data, result) = do
     currentEvent <- getEvent
     case currentEvent of
       EventA -> return (data, result)
       EventB ->
         (openFoo result :: IO YData)
           >>= runFoo
             >>= closeFoo
               >>= curry return data
   closeFoo (data, result) = ...

---

data YData = ...

instance Foo YData where
   openFoo result = ...
   runFoo (data, result) = do
     currentEvent <- getEvent
     case currentEvent of
       EventA -> return (data, result)
       EventB ->
         (openFoo result :: IO XData)
           >>= runFoo
             >>= closeFoo
               >>= curry return data
   closeFoo (data, result) = ...

Now I could simply resolve this by putting all of my instances into a single module, however rather than the 2 shown in my example I have 8 instances that are all mutually recursive with each other. On top of that each instance is quite large. Meaning the resulting module would be an enormous innavigable mess.

Now the haskell wiki has two suggestion for solving mutual recursion issues, but both of them are really more about mutually recursive types and neither of them is going to work here.

Is there anyway to get around this mutual recursion without simply combining all of my modules?

Walkyrie

I don't think so, unfortunately. – Godlike

Actually, I think that my last comment was wrong. Writing up an answer now. – Godlike

Is your actual code set up like your example? It seems like the logic in each instance is "handle certain events, and pass any other events to the appropriate handler in a consistent way". If this is actually the logic you have (and not just a result of simplification for the question), you may want to reassess your approach, and be sure you're not overengineering. There are much simpler ways to do things like this. – Encaenia

@Encaenia My problem here is that unlike my examples I do not actually select the appropriate handler in a consistant way. I suppose I should reassess my approach altogether though. – Walkyrie

It seems to me splitting up a mess into multiple modules makes more of a mess, no?... I suspect you maybe shouldn't be using type classes here at all – Ruhl

Answer 1

Perhaps you could abstract the recursive requirement out? Something like this:

{-# LANGUAGE ScopedTypeVariables #-}

runFooX :: forall ydata. Foo ydata => Proxy ydata -> (XData, Result) -> IO (XData, Result)
runFooX _ (data, result) = do
  currentEvent <- getEvent
  case currentEvent of
    EventA -> return (data, result)
    EventB ->
      (openFoo result :: IO ydata)
        >>= runFoo
          >>= closeFoo
            >>= curry return data

And in a separate file:

instance Foo XData where
   openFoo result = ...
   runFoo = runFooX (Proxy :: Proxy YData)
   closeFoo (data, result) = ...

This way, your file structure might look something like this:

            +-----------+
            | class Foo |
            +-----------+
              /       \
             v         v
+---------------+   +---------------+
| data XData    |   | data YData    |
| runFooX = ... |   | runFooY = ... |
+---------------+   +---------------+
              |       |
              v       v
       +---------------------+
       | instance Foo XData  |
       | instance Foo YData  |
       +---------------------+

You still need to put all the instance definitions in one file (otherwise, for example, the instance for XData can't know that YData implements Foo), but at least the logic is separated into different modules, which is what you're looking for.

It also looks a little awkward, but I guess it's a trade-off. There may be a way to make it nicer.

Encaenia

Answer 2

Here's one slightly hacky way to do it. First, put your recursive definitions in one module:

module Internal.Recursive

data XData = ...
data YData = ...

-- Recursive definitions...

Then re-export each definition from a separate module:

module XData (IR.XData) where

import qualified Internal.Recursive as IR

---

module YData (IR.XYata) where

import qualified Internal.Recursive as IR

This will give the appearance of mutually recursive modules. (I don't believe that GHC allows any easy way of making actual recursive modules.)

Godlike

My whole intention was to avoid putting all my definitions in a single module. It is nice that I could have each instance in a separate module but this doesn't help me avoid the fact that Internal.Recursive is going to be an absolute mess. – Walkyrie

@SriotchilismO'Zaic It is going to be a mess, unfortunately. There's very little you can do about it. I suppose you could try to separate out just the recursive definitions into a separate module to keep it as simple as possible, but this wouldn't really work above a certain amount of recursion. – Godlike