Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Skip the remaining actions in a monad - like return

Hi I'm looking for a good way to allow a monad stack to skip the remaining actions, without skipping out entirely. Kind of like return in C-family langauges.

For example, let's say I'm using monadic actions for the side effects

type MyMonad = ??
doStuff :: MyMonad ()
doStuff = do
   r <- doSomething

   -- equivalent to if (r == "X") return; in C
   dontGoPastHereIf (r == "X")

   doSomeSideEffects r

So I want it to only perform doSomeSideEffects on some condition.

I know you can do something close to this with guard and when already. Is it possible to do without nesting though?

ExceptT already allows you to exit the normal flow and return with an early result. But with ExceptT the error / skip will propogate. I want to only skip the rest of the steps in the local function

doTwoSteps :: MyMonad ()
doTwoSteps = do
  -- if I used ExceptT, an error in the first function will skip the second.
  -- But I still want to do the second step here
  doStuff
  doStuff

It seems like bind >>= already does this. At least it's certainly within the possibilities of a monad, but I'm not sure how to do with monad transformers.


Here's a more complete example. This system is supposed to perform a "workflow". Each step can result in a response, which is supposed to stop the entire workflow and respond (ExceptT).

The workflow can be restarted by passing ApplicationState. If a step has a previous Continue we can skip the logic for that step, but we still need to execute the next step.

Is there a better way to do this? Is there some monad transformer or a way to define my Flow monad such that I can run checkShouldSkip without passing in an action?

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE FlexibleContexts #-}

module Main where

import Control.Monad.Except (throwError, ExceptT)
import Control.Monad.State (gets, StateT, modify)
import Data.Text (Text)

data ApplicationState = ApplicationState
    { step1Result :: Maybe StepResult
    , step2Result :: Maybe StepResult
    } deriving (Show, Eq)

data StepResult
    = Stop
    | Continue
    deriving (Show, Eq)

type Flow a = StateT ApplicationState (ExceptT Text IO) a


flow :: Flow ()
flow = do
    step1
    step2

step1 :: Flow ()
step1 = do
    ms <- gets step1Result
    checkShouldSkip ms $ do
      info <- getStuffFromAServer
      let r = runSomeLogic info
      modify $ setStep1 $ Just r
      checkShouldRespond r

  where
    getStuffFromAServer = undefined
    runSomeLogic _ = undefined
    setStep1 r s = s { step1Result = r }


step2 :: Flow ()
step2 = do
    ms <- gets step2Result
    checkShouldSkip ms $ do
      -- this will run some different logic, eventually resulting in a step result
      r <- getStuffAndRunLogic
      modify $ setStep2 $ Just r
      checkShouldRespond r

  where
    getStuffAndRunLogic = undefined
    setStep2 r s = s { step2Result = r }


checkShouldSkip :: Maybe StepResult -> Flow () -> Flow ()
checkShouldSkip (Just Continue) _ = pure () -- skip the logic, continue
checkShouldSkip (Just Stop) _ = respond "Stop" -- skip the logic, stop everything
checkShouldSkip Nothing a = a -- run the action


checkShouldRespond :: StepResult -> Flow ()
checkShouldRespond Continue = pure ()
checkShouldRespond Stop = respond "Stop" -- if a response, stop all execution


-- rename because these aren't really errors, I just want to stop everything
respond :: Text -> Flow ()
respond t = throwError t
like image 916
Sean Clark Hess Avatar asked Dec 08 '22 18:12

Sean Clark Hess


1 Answers

The other answer is great! I wanted to talk a little bit about how exactly the continuation solution works so I wrote up this weird big thing. Hope it helps.

Act I: A Trap Is Laid

We begin our journey in the low rolling plains of IO, our favorite state monad:

module Lib where

step1 :: IO String
step1 = do
  print "step1 - A"
  print "step1 - B"
  pure "--step1 result--"

step2 :: String -> IO String
step2 input = do
  print input
  print "step2 - A"
  print "step2 - B"
  pure "--step2 complete--"

main :: IO ()
main = do
  result <- step1 >>= step2
  print "--done--"
  print result

We want to ascend upward and find a way of returning early from step one. Our first attempt is to introduce some sort of questionably-typed escape mechanism:

step1 :: (String -> ???) -> IO String
step1 escape = do
  print "step1 - A"
  escape "escaped!"
  print "step1 - B"
  pure "--step1 result--"

We cross our fingers, hoping that the string we pass to escape will end up as the string in IO String, and ponder what exactly can fill in those pesky question marks.

It seems to us that we need to hijack the >>= here if we are to have any hope of wresting the control flow away from the IO monad. We cautiously guess that we will need our own monad transformer.

newtype StrangeT inner a =
  StrangeT { runStrangeT :: a -> ??? }

lift :: IO a -> StrangeT IO a
lift io =
  StrangeT (\trapDoor -> io >>= trapDoor)

escape :: a -> StrangeT IO a
escape a =
  StrangeT (\trapDoorA -> trapDoorA a)

step1 :: StrangeT IO String
step1 = do
  lift (print "step1 - A")
  escape "escaped!"
  lift (print "step1 - B")
  pure "--step1 result--"

We can think of trapDoorA as an escape mechanism guarded by a key, the key being any value of type a. Once the door is open we fall through into the next step of the computation.

What type to insert for the question marks? We have sort of boxed ourselves into a corner; in order for this code to compile we it can only be:

newtype StrangeT inner a =
  StrangeT { runStrangeT :: (a -> inner a) -> inner a }

Act II: Stranger Still

We now need to instance Monad (StrangeT inner). Unfortunately we are going to run into a big problem. StrangeT is not a functor!

The reason for this is that "a" appears in the "negative position":

newtype StrangeT inner a =
  StrangeT { runStrangeT :: (a -> inner a) -> inner a }
                               -- ^^^^^^^
                               -- :(

(For a full discussion of this topic see What is a contravariant functor?.)

We can employ a nasty trick, which is to split the "negatives" and the "positives" into two different type variables (a and result):

newtype StrangeT result inner a =
  StrangeT { runStrangeT :: (a -> inner result) -> inner result }

lift :: IO a -> StrangeT whatever IO a
lift io = StrangeT (\trapDoor -> io >>= trapDoor)

escape :: a -> StrangeT whatever IO a
escape x = StrangeT (\trapDoor -> trapDoor x)

This makes everything possible. We can now instance Functor, Applicative, and Monad. Rather than trying to puzzle out the answers though, we will simply let the type checker take over. Any answer that type checks will be the right one.

instance Functor (StrangeT result inner) where
  fmap a2b (StrangeT strange) =
    StrangeT $ \trapDoor -> strange (\a -> trapDoor (a2b a))
             -- ^^^^^^^^
             -- b -> inner result

Train of logic:

  • trapDoor is the only way to build an inner result value.

  • It needs a value of type b.

  • We have a2b :: a -> b and a :: a.

    instance Applicative (StrangeT result inner) where
      pure :: a -> StrangeT result inner a
      pure a = StrangeT $ \trapDoor -> trapDoor a
    
      (<*>) :: StrangeT result inner (a -> b) ->
               StrangeT result inner a ->
               StrangeT result inner b
      (StrangeT strangeA2B) <*> (StrangeT strangeA) =
    --          ^^^^^^^^^^                ^^^^^^^^
    --          (b -> inner result) -> inner result
    --                                    (a -> inner result) -> inner result
        StrangeT (\trapDoorB -> strangeA2B (\a2b -> strangeA (\a -> trapDoorB (a2b a))))
    --             ^^^^^^^^                 
    --             b -> inner result
    

Train of logic:

  • We have trapDoorB :: b -> inner result (the only way to construct inner result), a2b :: a -> b, and a :: a.

  • We need to construct a StrangeT result inner b;

  • We therefore must at some point evaluate trapDoorB (a2b a).

The monadic instance is about as difficult:

    instance Monad (StrangeT result inner) where
      (StrangeT strangeA) >>= a2strangeB =
         --     ^^^^^^^^
         --     (a -> inner result) -> inner result
        StrangeT
          (\trapDoorB -> strangeA (\a -> let StrangeT strangeB = a2strangeB a in strangeB (\b -> trapDoorB b)))
         -- ^^^^^^^^^                                 ^^^^^^^^
         -- b -> inner result                         (b -> inner result) -> inner result

There is only one way to construct inner result, which by falling through trapDoorB, so everything else is built toward that singular goal.

Act III: A Fumble

We have defined a monad transformer without really knowing what it does or how it works! We simply smashed together the types that looked right.

It would behoove us then to see it in action:

main :: IO ()
main = do
  _ <- runStrangeT (step1 >>= step2) (\a -> pure a)
  print "--done--"
  print result

This results in the following output:

λ> main
"step1 - A"
"step1 - B"
"--step1 result--"
"step2 - A"
"step2 - B"
"--done--"
"--step2 result--"

How frustrating! We are right where we started from.

However, something peculiar happens if we define this function:

escape :: a -> StrangeT whatever IO a
escape x = StrangeT (\trapDoor -> trapDoor x)

escapeWeirdly :: a -> StrangeT whatever IO a
escapeWeirdly x = StrangeT (\trapDoor -> trapDoor x >> trapDoor x >> trapDoor x)

step1 :: StrangeT String IO String
step1 = do
  lift (print "step1 - A")
  escapeWeirdly "--step1 exit--"
  lift (print "step1 - B")
  pure "--step1 result--"

Output:

λ> main
"step1 - A"
"step1 - B"               <- trap door call #1
"--step1 result--"
"step2 - A"
"step2 - B"
"step1 - B"               <- trap door call #2
"--step1 result--"
"step2 - A"
"step2 - B"
"step1 - B"               <- trap door call #3
"--step1 result--"
"step2 - A"
"step2 - B"
"--done--"
"--step2 result--"

step2 runs three times! It seems that "trapDoor" encodes some notion of "everything after this point in the control flow." Calling it once runs everything after it once. Calling it three times runs everything after it three times. Calling it zero times...

cut :: a -> StrangeT a IO a
cut x = StrangeT (\_ -> return x)

step1 :: (String -> StrangeT String IO String) -> StrangeT String IO String
step1 exit = do
  lift (print "step1 - A")
  cut "--step1 exit--"
  lift (print "step1 - B")
  pure "--step1 result--"

main :: IO ()
main = do
  result <- runStrangeT (step1 undefined >>= step2) pure
  print "--done--"
  print result

Output:

λ> main
"step1 - A"
"--done--"
"--step1 exit--"

Nothing runs! This is incredibly close to what we need.

Act IV: Success and the Price Thereof

What if we could mark a do-block of StrangeT actions as needing an early exit? Something very similar to our original escape mechanism:

step1 = withEscape $ \escape -> do
  lift (print "step1 - A")
  escape "--step1 exit--"
  lift (print "step1 - B")
  pure "--step1 result--"

What withEscape does is it runs the do-block as written until someone calls escape, at which point the rest of the computation is aborted but any computation outside the withEscape (namely Step Two here) runs as-is.

This helper must have a type of:

withEscape :: (??? -> StrangeT result inner a) -> StrangeT result inner a

Almost the exact same leap of faith we made when we went from m a to (a -> m a) -> m a.

Since we are passing a String to escape and binding the result of that computation to the next line of the do-block, we can now fill in those question marks:

withEscape :: ((a -> StrangeT result inner whatever) -> StrangeT result inner a)
              -> StrangeT result inner a

A tricksy type! We are going to have to navigate by type again to find the definition:

-- We have to call f at some point, and trapDoorA
-- is the only way to construct an inner result.
withEscape f =
  StrangeT (\trapDoorA -> let StrangeT strangeA = f ??? in strangeA trapDoorA)

-- f is passed the early exit value
withEscape f =
  StrangeT (\trapDoorA ->
    let StrangeT strangeA = f (\a -> ???) in strangeA trapDoorA)

-- We need to construct a StrangeT value
withEscape f =
  StrangeT (\trapDoorA ->
    let StrangeT strangeA = f (\a -> StrangeT (\trapDoorWhatever -> ???)) in
    strangeA trapDoorA)

-- We are going to *ignore* the trapDoorWhatever
-- we are supposed to fall into, and *instead*
-- fall through our original trapDoorA.
withEscape f =
  StrangeT (\trapDoorA ->
    let StrangeT strangeA = f (\a -> StrangeT (\_ -> trapDoor a)) in
    strangeA trapDoorA)

What happened here is that we stumbled onto a solution that gives us two trap doors. Instead of falling through the first door (which would make the helper boil down to something like pure in that it would resume normal control flow) we chose to fall through the original door we built for ourselves. Fans of the movie Primer will recognize this as the original sin; normal people might just view all this with a confused look on their face.

Regardless, this works:

step1 :: StrangeT String IO String
step1 =
  withEscape $ \escape -> do
    lift (print "step1 - A")
    escape "--step1 exit--"
    lift (print "step1 - B")
    pure "--step1 result--"

step2 :: String -> StrangeT String IO String
step2 result = do
  lift (print result)
  lift (print "step2 - A")
  lift (print "step2 - B")
  pure "--step2 result--"

main :: IO ()
main = do
  result <- runStrangeT (step1 >>= step2) pure
  print "--done--"
  print result

Output:

λ> main
"step1 - A"              <- early exit
"--step1 exit--"         <- step2 runs
"step2 - A"
"step2 - B"
"--done--"               <- back to main
"--step2 result--"

Summary

  • As telegraphed, this is the ContT monad and can be found packaged in the transfomers package. What we have been calling trap doors are really continuations.

  • withEscape is better known as callCC (call with current continuation); it lets you give the current continuation at the time you called callCC a name (escape in our examples); when you activate the continuation it allows you to return a value immediately.

  • You can implement a great deal many things with continuations, including early returns and exceptions and generators and god knows what else. We have yet to even talk about delimited continuations (shift and reset). They represent something primal and fundamental to the structure of computer programming.

  • For more information, see the series of papers linked from Oleg Kiselyov's website. There is much much more to be said about continuations.

Should you ever actually do this in real life?

Probably not. ExceptT tends to create fewer headaches in the long run.

But is ExceptT cooler than ContT?

Hardly.

like image 180
hao Avatar answered Jan 02 '23 03:01

hao