[Haskell-cafe] Parallelism and expensive calculations that may not be needed

Felipe Almeida Lessa felipe.lessa at gmail.com
Thu Jun 7 15:33:45 EDT 2007


Hello everybody!

(Sorry if this is a newbie question, couldn't find the answer anywhere)

Suppose I have an expensive function (such that even to be reduced to WHNF
it takes a long processing time)

> expensive :: Foo -> Maybe Bar

and I want to calculate it on multiple processors, like in

> calculate = parMap rnf expensive

Well, fine. But suppose that then I give the result to a function like

> final xs = reverse $ final' xs [] where
>     final' []     r = r
>     final' (x:xs) r = case x of Nothing -> []
>                                 Just x  -> final' xs (x:r)

Given list :: [Foo], a sequential calculation as in

> resultS = final $ map expensive list

would not call expensive after finding a Nothing. But

> resultP = final $ calculate list

will keep calculating all the other expensive's because they were sparked?



Also, suppose that in list there are thousands of elements, whereas the last
one is the only x such as "expensive x == Nothing". More importantly,
calculating "expensive x" is very fast for some reason. In both
versions above, all
the initial elements will have to be calculated in order to find that the
last one (that probably was already computed in the parallel version) was
Nothing and that all the work must have to be thrown away.


Are the observations above valid? Is there a way to improve this style
of computation? Any pointers are appreciated =).

I think that to solve the second problem, I needed some sort of fold
that is aware of parallel nature of the list and that folds on the
order in that the thunks get evaluated, and not on order of the list.
But I guess it's not possible to write something like this, right?

Cheers,
Felipe.

-- 
Felipe.


More information about the Haskell-Cafe mailing list