Indent from the main monad in Monad Transformer
As a side project, I am working on implementing my own Regex parser / compiler .
I realized that the actual matched part would be a great time to learn how some of the backing monads work; for example, as a list monad.
I ended up constructing my "match" algorithm like this:
data Expr
= Group Int Expr
| Terms [Expr]
| OneOf [Expr]
| Repetition Expr Int (Maybe Int)
| Empty
| BackRef Int
| Wildcard
| Atom Char
| Start
| End
deriving (Show)
data RState = RState
{ groups :: Groups
, leftover :: String
} deriving Show
match :: Expr -> ListT (State RState) String
where ListT belongs to Gabriel List.Transformer lib
The state monad plot keeps track of the groups that were captured (so I can use them when I match backlinks), and the rest of the line remains in use. Expr
is a data structure representing Regex like AST.
Anyway; it works well; I am recursing trying to make matches, if a match succeeds, I will return the corresponding part and change the remainders and groups in the state accordingly, this ends up working without determinism because it will continue to use all possible previous matches when trying to process the next part of the regex ... The problem is that it only steps back from the previous results, but NOT to the previous state! As a result, my matching code alternative
for matching option chains in a regex (e.g. a | b * | c; where each part is a term) looks like this:
match (OneOf terms) = do
st <- get
-- Backtrack the state and try again on each alternative
let try t = put st >> match t
asum (try <$> terms)
I basically try to match each term, but even if the match fails, it still changes state! So I need to manually rewind the state between failures. This is related to the ListT implementation <|>
:
ListT m <|> l = ListT (do
s <- m
case s of
Nil -> next l
Cons x l' -> return (Cons x (l' <|> l)) )
Where we can see that it controls the main monad and continues in the same context.
I want something similar to this:
ListT m <|> l = ListT (do
st <- get
s <- m
case s of
Nil -> put st >> next l
Cons x l' -> return (Cons x (l' <|> l)) )
... But for all monad effects in general; I'm not even sure if this is possible.
I looked at Logic Monad as a possible solution, but even after reading the article I can't tell if it can do it what I want, maybe it can be done with ifte
?
Is there a monastic monad that not only repels the result of the monad, but also monadic computation? I suppose this is not possible for things like IO, but theoretically possible for pure monads? I'm guessing this means it's not possible at all, but is there a type-class I could implement to get this functionality for my case?
Thank! I know I am silent here, thanks for helping me think it through!
source to share
The solution is to invert the stack as @danidiaz suggests.
It is helpful for me to remember that external monad transformers are at the mercy of internal ones. Thus, it SomeMonadT (State s)
will be "single threaded" in its consistency, no matter what it does SomeMonadT
.
An illustrative example is unfolding a monad-transformer StateT
on top of another monad. Let's say we have:
foo :: StateT S M A
bar :: StateT S M B
do a <- foo
b <- bar
return (a,b)
This is just a fancy way of writing:
foo :: S -> M (A, S)
bar :: S -> M (B, S)
\s1 -> do
(a,s2) <- foo s1
(b,s3) <- bar s2
return ((a,b),s3)
This is the usual pattern that motivates a monad State
, except that the pattern takes place in a different monadic context. This context is king, there is nothing a transformer can do.
This means that it ListT (State s)
is a computation that keeps track of one state s
, and then some "sugar" is found on top, which is determined ListT
. You might think of it as implementing non-determinism in a stateful machine (which only has the ability to track one state).
Whereas StateT s []
is a computation that is essentially non-deterministic, and then there is some "sugar" that emulates the state. The main machine is a non-deterministic backtracking machine and then the transformer uses a coding pattern to simulate the state on that machine.
Here's a diagram by Dan Piponi to help provide some intuition:
This is a bit of desirable and intuitive territory, so I hope this was helpful.
Further reading: How do I create a monodic stack?
source to share