[Haskell-cafe] Evaluating parallel computations in order of finishing (approximately)
rrnewton at gmail.com
Tue Feb 7 22:10:14 CET 2012
In stream processing frameworks this is a (common) non-deterministic merge
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 Chan library has a primitive, getChanContents, that encapsulates the
lazy IO and makes this very easy to do:
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.
On Mon, Feb 6, 2012 at 6:24 PM, Edward Amsden <eca7215 at cs.rit.edu> wrote:
> Conal Elliot did something like this for his FRP system in the paper
> Push-Pull Functional Reactive Programming . 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.
>  http://conal.net/papers/push-pull-frp/
> On Mon, Feb 6, 2012 at 5:46 PM, Victor Miller <victorsmiller at gmail.com>
> > Suppose that we have a list [a] of computations that we want to evaluate
> > 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
> > 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
> > 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
> > be the first value whose computation finished.
> > Does such a thing exist?
> > Victor
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> Edward Amsden
> Computer Science
> Rochester Institute of Technology
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe