CODEWITHSUNDEEP
haskellrecursionparallel-processing
andrew_j
andrew_j

Reputation: 41

Recursion and parallelism in Haskell

I'm trying to understand how paralleling in Haskell works and I've found following example in Control.Parallel docs.

import Control.Parallel

-- Equation for the upper hemisphere of the unit circle

circle :: Double -> Double
circle x = sqrt (abs(1 - x^2))

-- Calculate the area of a right-handed Riemann rectangle

area :: Double -> Double -> Double
area x1 x2 = (x2 - x1) * circle x2

-- Recursively add the areas of the Riemann rectangles

parEstimate :: [Double] -> Double
parEstimate (x:[]) = 0
parEstimate (x:y:[]) = area x y
parEstimate (x:y:xs) =
smaller `par` (larger `pseq` smaller + larger)
  where smaller = area x y
        larger = parEstimate (y:xs)

But I couldn't find an explanation of how this recursion works: parEstimate (x:y:xs), cause all examples I've found contains only two arguments. That's why I cannot find out how to run this function. That's how I do:

main = print (parEstimate [1.0, 2.0])

but not sure, if it's correct. Also I would like to implement function calculating definite integral based on this example.

Upvotes: 0

Views: 425

Answers (1)

chepner
chepner

Reputation: 531808

The recursion, essentially, is a simple fold-like recursion scheme; if this were purely sequential, you might write it as

seqEstimate :: [Double] -> Double
seqEstimate (x:[]) = 0
seqEstimate (x:y:[]) = area x y
seqEstimate (x:y:xs) = smaller + larger
    where smaller = area x y
          larger = seqEstimate (y:xs)

(In fact, you would probably just use zipWith instead: seqEstimate xs = sum (zipWith area xs (tail xs)).)

The parallelized version is similar. This time, though, par is used to indicate that the left-hand side (smaller) can be evaluated in parallel with the right-hand side (pseq larger (smaller + larger)). Whether or not the compiler chooses to do so, and regardless of whether smaller completes before or after larger, the sum of smaller + larger will be correctly computed.

Upvotes: 3

Related Questions