[Haskell-cafe] Parallelism and expensive calculations that may not
Felipe Almeida Lessa
felipe.lessa at gmail.com
Thu Jun 7 15:33:45 EDT 2007
(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?
More information about the Haskell-Cafe