Semidependent Actions in Haskell

Question

I am looking for a Haskell design to compose a chain of monadic actions (usually IO) in a manner, that later actions are dependent on previous ones but in some cases can be executed before they have finished.

The solution I came up with so far is:

type Future m a = m (m a)

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

So in some chain a >>= b >>= c b gets an action returning a’s result. If b evaluates this action it waits for a to finish, otherwise it will be run in parallel. That also means that if some action does not require the result of the previous one as argument, it does not depend on it by definition, so the dependencies are explicit.

Some example code:

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"

There is a problem through: if an action decides to wait for the previous one it will always be dependent on all the others before (in my case). But in the example above if c decides to wait for b but b did not decide to wait for a, c may start before a has finished, which should not happen.

As a solution I wrote another combining operator:

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

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

The actual problem is in >=>: f r1 may evaluate r1 in wich case it does not need to be sequenced with r2 in the return statement (as it already was executed and thus a has finished). But it also might not, I cannot know.

So what I basically want is exactly this but without the possibility to run the wait actions several times. Unfortunately I am not very experienced in functional design.

So I hope you can enlighten me in some way how to augment or change my design or point me to a different, more flexible approach.

Edit According to the answers so far I like to give some more clarification about what I actually want:

I do not want to defer (or even skip) the execution of actions, neither do I require threads or similar parallelism features. Actually I am calling external processes. An example would be

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

When I now chain actions like backup >=> otherAction, otherAction can run while the backup is running (which saves much time overall). But otherAction may require the backup to be completed, in which case it can use its parameter to wait for the backup and to check whether it was successful. Either way the backup has to be executed.

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

Update I found a solution that worked for me. I described it in a seperate answer below.

You might want to choose a different name for your new combinator, because >=> is already taken. — Matt Fenwick
Even though you do not require parallel execution, threads (as mentioned in some answers) may be a good solution. Threads in Haskell are fairly easy to use. — Heatsink
It's worth pointing out that for sufficiently lazy monads, (e.g. the lazy State monad), you don't need to do anything to get the semantics you want. — John L
@JohnL That sounds very interesting. I was wondering whether Haskell’s lazyness would help me and I was not able to come up with something working. Does this also work with my constrain, that if in a >>= b >>= c c waits for b it also waits for a automatically? — ipsec
You might find inspiration in the Orc library, which can be used to coordinate external processes. In particular, it has a combinator eagerly, which spawns an action and returns a handle that can be used to wait for the action to terminate. — Magnus Carlsson

Gabriella Gonzalez Gabriella Gonzalez · Accepted Answer · 2012-08-15T02:57:29

I'm pretty sure you actually wanted this signature:

(>>=) :: Future m a -> (a -> Future m b) -> Future m b

Here's how you implement what you want:

import Control.Concurrent
import Control.Monad
import Control.Monad.Trans

newtype Future m a = Future { runFuture :: m (m a) }

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 is specialized to the IO monad. However, the following example will show how you use it in conjunction with the IO monad to chain futures:

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 haven't yet proven that it satisfies the monad laws or the monad transformer laws, but I will try to do that and I will update you on whether or not it checks out. Until then, there might be a misplaced join somewhere in there.

Edit: Nope! Not even close. It definitely does not satisfy the monad laws. I don't know if I was close or not, but just assume this answer is incorrect for now. However, I'm kind of intrigued now and wonder if it's possible.

Semidependent Actions in Haskell

5 Answers