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@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@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@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