Semidependent Actions in Haskell

Question

I am looking for a Haskell design to put together a chain of monadic actions (usually IO) in such a way that the next steps depend on the previous ones, but in some cases can be performed before they are completed.

The solution I came up with so far:

type Future ma = m (ma) 

Read: monadic action, which starts a certain process and returns an action that will return the result of this process (possibly waiting for the completion of this process).

So, in some chain a >>= b >>= c b receives the action returned as a result. If b evaluates this action, it waits for completion, otherwise it will be executed in parallel. It also means that if an action does not require the result of the previous one as an argument, it does not depend on it by definition, so the dependencies are explicit.

Code example:

 date :: Future IO String -- long process to find out the date date = do print "attempting to get date" -- will usually start some thread or process to compute the date return (print "today") -- will wait for this thread or process and return the computed date main = do d <- date -- starts recieving the date print "foo" -- some other process d >>= print -- waits until the date has been computed and prints it out 

Output:

 "attempting to get date" "foo" "today" 

A problem arises: if an action decides to wait for the previous one, it will always depend on everyone else until (in my case). But in the above example, if c decides to wait for b, but b did not decide to wait for a, c can start before completion, which should not happen.

As a solution, I wrote another combination operator:

 (>=>) :: Monad m => Future ma -> (ma -> Future mb) -> Future mb a >=> f = do r1 <- a r2 <- f r1 return (r1 >> r2) 

So, this will combine the “wait actions”, and a >=> b >=> c will work fine, if c waits for b, this wait action will also wait. However, there is another problem with this approach (in addition, you need to remember that you need to use> => instead of → =): wait actions can be evaluated many times. If b waits for a and c waits for b, wait b will be connected to wait, however, and therefore wait a will be executed twice.

The actual problem is in> =>: f r1 can evaluate r1 when the return statement does not need to be sequenced with r2 (since it has already been executed and thus finished). But it also cannot be, I do not know.

So I basically want this, but without the ability to trigger wait actions several times. Unfortunately, I am not very versed in functional design.

So, I hope that you can somehow illuminate me, how to increase or change my design or point to another, more flexible approach.

Change In accordance with the answers so far, I would like to give some clarification on what I really want:

I do not want to delay (or even skip) the execution of actions, I also do not need threads or similar parallelism functions. Actually, I call external processes. Example:

 backup :: Future IO ExitCode backup = do pid <- startProcess "backup" return (waitForProcessAndGetExitCode pid) 

When I now perform actions like backup >=> otherAction , otherAction can be triggered during backup (which saves a lot of time in general). But otherAction may require the completion of the backup, in which case it can use its parameter to wait for the backup and check if it was successful. In any case, the backup should be performed.

Now I am looking for a good general solution, ideally not tied to the IO monad.

Update I found a solution that worked for me. I described this in a separate answer below.

Answer 1

I'm sure you really wanted this signature:

 (>>=) :: Future ma -> (a -> Future mb) -> Future mb 

Here you implement what you want:

 import Control.Concurrent import Control.Monad import Control.Monad.Trans newtype Future ma = Future { runFuture :: m (ma) } instance (Monad m) => Monad (Future m) where return = Future . return . return m >>= f = Future $ do fut1 <- runFuture m return $ join $ join $ liftM (runFuture . f) fut1 instance MonadTrans Future where lift = Future . liftM return 

In other words, Future is a monad transformer, and nothing about its implementation specializes in IO monad. However, the following example will show how you use it in conjunction with the IO monad for the futures chain:

 parallel :: IO a -> Future IO a parallel m = Future $ do v <- newEmptyMVar forkIO $ m >>= putMVar v return $ takeMVar v future1 = parallel $ do threadDelay 1000000 putStrLn "Hello, World" return 1 future2 n = parallel $ do threadDelay 1000000 print n return 2 future3 = future1 >>= future2 main = do f <- runFuture future3 putStrLn "I'm waiting..." r <- f print r 

I have not yet proven that it satisfies the laws of the monad or the laws of the transformer of the monad, but I will try to do this, and I will clarify whether it checks it. Until then, join may be lost there.

Edit: No! Not even close. This definitely does not satisfy the laws of the monad. I don’t know if I was there or not, but just suppose this answer is incorrect. However, I am intrigued right now and am wondering if this is possible.

Answer 2

Perhaps one of the possibilities is to refuse to even run f until its output is required:

 mma >=> fab = return $ do ma <- mma b <- fab ma b 

Depending on what you want, it may be important to start mma first:

 mma >=> fab = do ma <- mma return $ do b <- fab ma b 

Answer 3

If you add a restriction on the MonadIO instance for m , you can do something like this (from memory, unverified):

 share :: IO a -> IO (IO a) share m = do ref <- newIORef Nothing let reader = do cached <- readIORef ref case cached of Just a -> return a Nothing -> m >>= \a -> writeIORef ref (Just a) >> return a return reader 

You can change this to share2 :: IO a -> IO a by wrapping the IORef creation in unsafePerformIO and simply generalizing it to any MonadIO instance.

But, depending on your problem, you might be better off with something like threads or IVar .

Answer 4

For cases where you want to spark some streams and collect results at some point, check http://hackage.haskell.org/packages/archive/base/4.5.1.0/doc/html/Control-Concurrent-SampleVar.html and http://hackage.haskell.org/packages/archive/base/4.5.1.0/doc/html/Control-Concurrent.html#g:2 as they seem relevant

In cases where you need to perform actions on demand, you may find this code useful Not verified by GHC, but should work after typos are corrected.

 module Promise (SuspendedAction, createSuspendedAction, getValueFromSuspendedAction) import Data.IORef data Promise a = Suspended (IO a) | Done a data SuspendedAction = SA (IORef (Promise a)) createSuspendedAction :: ma -> m (SuspendedAction a) createSuspendedAction act = newIORef (Suspended act) readSuspendedAction :: SuspendedAction a -> ma readSuspendedAction (SA ref) = readIORef ref >>= \suspended -> case suspended of Done a -> return a Suspended sact -> sact >>= \rv -> writeIORef ref (Done rv) >> return rv 

By the way, check the hackers carefully, there was a package that allows you to perform IO-actions lazily, observing their order.

Answer 5

I found a solution myself, although not completely for the problem, I have a postet.

I realized that I need to know in advance somehow whether the action depends on the previous one. I tried different approaches and even came up with what I’ll talk about now. My solution allows you to write code like

 a :: Process IO x () a = independant $ do print "start a" return $ print "end a" b :: Process IO x Int b = independant $ do print "start b" return $ print "end b" >> return 0 c :: Process IO Int () c = dependant $ \x -> do print $ "start c with " ++ show x return $ print ("end c, started with " ++ show x) chain = a >~ b >~ c main = exec chain -- outputs: "start a" "start b" "end a" "end b" "start c with 0" "end c, started with 0" 

(some more examples below)

I used the following types

 type Future ma = m (ma) type Action mab = a -> Future mb type Process mab = forall c. Action mca -> Action mcb -- will need -XRank2Types 

with the following primitives:

 -- sequences f after g, f is dependant of g and gets its result -- dependant :: Monad m => Action mab -> Action mca -> Action cb dependant :: Monad m => Action mab -> Process mab dependant fga = join (ga) >>= f -- sequences f after g, f is independant of g independant :: Monad m => Future ma -> Process mba independant fga = do w1 <- ga w2 <- f return (w1 >> w2) -- concenation of processes (>~) = flip (.) 

This approach allows other primitives to also simplify processing, for example:

 -- lifts a pure function into an action pureA :: Monad m => (a -> b) -> Action mab pureA fa = return . return $ fa -- makes an action wich always returns the same result constA :: Monad m => b -> Action mab constA = pureA . const -- no operation action nop :: Monad m => Action ma () nop = constA () -- puts a sequence point wait :: Monad m => Process maa wait = dependant $ pureA id -- modify its result with a pure function modify :: (Monad m, Functor m) => (a -> b) -> Process mab modify f act a = do x <- act a return (fmap fx) -- makes a process, wich always returns the same result constP :: (Monad m, Functor m) => b -> Process mab constP = modify . const 

And finally, the function to start the process:

 -- executes a process exec :: Monad m => Process m () b -> mb exec p = join $ p nop undefined 

So, a few more complex examples:

 simleI :: String -> a -> Process IO ba simpleI name r = independant $ do print ("start " ++ name) return $ print ("end " ++ name) >> return r simpleD :: (Show a, Show b) => String -> (a -> b) -> Process IO ab simpleD name f = dependant $ \a -> do print ("start " ++ name ++ " with " ++ show a) let r = fa return $ print ("end " ++ name ++ " with " ++ show r ++ " (started with " ++ show a ++ ")") >> return r a = simpleI "a" () b = simpleI "b" 42 c = simpleD "c" (+1) d = simpleI "d" () chain1 = a >~ b >~ c >~ d -- == d . c . b . a chain2 = a >~ wait >~ b >~ c >~ d chain3 = a >~ b >~ modify (+1) >~ c >~ d main = do exec chain1 print "---" exec chain2 print "---" exec chain3 

Output:

 "start a" "start b" "end a" "end b" "start c with 42" "start d" "end c with 43 (started with 42)" "end d" "---" "start a" "end a" "start b" "end b" "start c with 42" "start d" "end c with 43 (started with 42)" "end d" "---" "start a" "start b" "end a" "end b" "start c with 43" "start d" "end c with 44 (started with 43)" "end d" 

This is almost what I want.

I am a little curious to classify an action and a process. These are not monads. They may be arrows, but I'm too unfamiliar with arrows to tell. A process can be applicative with fmap = modify and pure = const. constA oder is something like this.

Please feel free to comment on everything that comes to my mind about my approach, especially about how to expand or simplify it.