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

[Ryan Newton]

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-Concurrent-Chan.html

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 <eca7215 at cs.rit.edu> 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/
>
>
> On Mon, Feb 6, 2012 at 5:46 PM, Victor Miller <victorsmiller at gmail.com>
> wrote:
> > 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
> the
> > 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
> 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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120207/9daa586a/attachment.htm>