CODEWITHSUNDEEP
haskellrecursionmonadsmonad-transformers
Da Li
Da Li

Reputation: 43

How to traverse a Monad with recursion definition and collect the results?

I implement the monad transformer MaybeT.

newtype MaybeT m a =
    MaybeT { runMaybeT :: m (Maybe a) }

Then, I write a monad for backtracking.

newtype BackT m a =
    BackT { unBackT :: MaybeT m (a, BackT m a) }

Here,Back m a has recursion definition.

In my mind, there are isomorphisms.

                 unBackT
BackT m a <-------------------> MaybeT m (a, BackT m a)
            BackT(constructor)    

                              runMaybeT
MaybeT m (a, BackT m a) <------------------> m (Maybe (a, BackT m a))
                         MaybeT(constructor)

Thus, I actually get something like

m (Just(1, m (Just(2, m (Just(3, m (Just(4, Nothing))))))))

In the example given above, there are 4 computations(Monad is computation?). I need something called runBackT to collect them using [].

Thanks for the answer from @rampion , and I remove some meaningless questions.

Update

Monad can be divided into two classes: "opened monads" (like [], Maybe) and "closed monads" (like IO). The "opened monads" have functions with type m a -> b to open them. e.g.

showMaybe :: (Show a) => Maybe a -> String
showMaybe mx = case mx of
    Nothing -> "Nothing"
    Just x -> show x
  1. How to implement (Monad m, Show m) => BackT m a -> [String]?
  2. More generally, Monad m => (m a -> b) -> BackT m a -> [b]?
  3. Under what conditions, does Monad m => BackT m a -> [m a] exist? BackT m a sequences computations m a recursive by cross-recursive definition. How to change it into iteration [m a]? If it exists, how to implement it? We can map m a -> b to [m a], and question (2) will be solved.
  4. Monad m => (m a -> a) -> BackT m a -> m [a]? Just wrap the result of question(2) by constructor m.

Therefore, the key point is question (3).

The most difficult part for me is recursion definition of BackT m a. I'd appreciate it if you could show the implement or share some advice.

Answers only for question (3) is OK.

Update

Thanks for comments from @rampion, the ListT from list-t package answered my questions.

Upvotes: 4

Views: 289

Answers (1)

rampion
rampion

Reputation: 89143

How to collect all arguments like 1, 2, 3, 4 in example. It's type should be [a]. Does such a BackT m a -> [a] function exist? Or we can only get m [a]?

Think of this the other way around first.

We can certainly get a BackT m a value for any Monad m:

Prelude> emptyBackT = BackT (MaybeT (return Nothing))
Prelude> :t emptyBackT
emptyBackT :: Monad m => BackT m a

And with the power of fmap, we can convert any m a to a BackT m a for any Functor m:

Prelude> lift ma = BackT (MaybeT (fmap (\a -> Just (a, emptyBackT)) ma))
Prelude> :t lift
lift :: Monad m => m a -> BackT m a

So if we had a way to convert any BackT m a -> [a], we could combine that with lift to get m a -> [a] for any Functor m!

But we know we can't do that in Haskell. Some functors (like [] or Maybe) unwrapped, but there's others (like IO) that can't.

So runBackT needs to have type BackT m a -> m [a].

As for implementation, here's some leading questions.

You've got an isomorphism from BackT m a to m (Maybe (a, BackT m a)), so

  • Assuming runBackT :: BackT m a -> m [a] were already implemented, could you implement consBackT :: a -> BackT m a -> m [a]?
  • Assuming runBackT :: BackT m a -> m [a] were already implemented, could you implement unwrapBackT :: Maybe (a, BackT m a) -> m [a]?
  • Assuming unwrapBackT :: Maybe (a, BackT m a) -> m [a] were already implemented, could you implement innerToList :: m (Maybe (a, BackT m a)) -> m [a]?

(Hint: the types I've used in the leading questions are incomplete)

Upvotes: 2

Related Questions