Re: [Haskell-cafe] Evaluating parallel computations in order of finishing (approximately)

In stream processing frameworks this is a (common) non-deterministic merge operation. Because it's nondeterministic it would need to happen in IO: parCompletionOrder :: [a] -> IO [a] But it can be nonblocking (returns immediately, and "lazy IO" happens in the background). The Chan library has a primitive, getChanContents, that encapsulates the lazy IO and makes this very easy to do: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurren... Thus "parCompletionOrder" (or whatever it's called) would only need to fork an IO thread for each element, and have all threads write to a single channel as soon as they are done. (Where done is either evaluating shallowly (weak-head-normal-form) or deeply (full normal form).) Then the main thread invokes getChanContents and voila. Cheers, -Ryan On Mon, Feb 6, 2012 at 6:24 PM, Edward Amsden wrote:

Conal Elliot did something like this for his FRP system in the paper Push-Pull Functional Reactive Programming [1]. It involved a hack in which unsafePerformIO was used to spawn two threads to evaluate two events for occurrences, and return whichever returned first.

Recall though, that monads aren't magic (despite frequent appearances to the contrary.) They are just functional structures that have to obey all of the normal restrictions of a pure functional language, including referential transparency. The entire point of Haskell's parallelism constructs is to make the returned values independent of parallel evaluation order. You're not going to escape that by using a monad, unless its one like IO which exists to order side-effects and isolate them in the type system.

[1] http://conal.net/papers/push-pull-frp/

...

Suppose that we have a list [a] of computations that we want to evaluate in parallel. I would like to have something (probably a monad) which would return the list in order (roughly) of finishing:

Say the monad is M. It would be something like the state monad, in that it would be implemented by a state transformer function. In this case the state would the set of computations to be evaluated.

we might have a function

include :: [a] -> M a ()

which would say that the monad's responsibility would be to evaluate all

...

members of a in parallel. We might also have a function

strategy :: Strategy -> M a ()

which would indicate the parallel strategy to be used.

The key thing would be function, completed, which produces a list of all

On Mon, Feb 6, 2012 at 5:46 PM, Victor Miller wrote: the the

...

computations to be evaluated as a list roughly in order of completion.

That is, if, inside the M monad we finished the do with

completed

then we would have a value M a [a]

which would be the list in order of completion.

Since everything is lazy we could ask for the head of the list, and it would be the first value whose computation finished.

Does such a thing exist?

Victor

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Edward Amsden Student Computer Science Rochester Institute of Technology www.edwardamsden.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe