Sequential ordering of evaluation

The seq primitive, despite its name, is not required to evaluate its parameters in some predefined order, according to the Haskell 2010 Report. For parallel programming, sometimes a variant of seq is needed with such an ordering:

The seq combinator implements sequential composition. When the expression e1 ‘seq‘ e2 is evaluated, e1 is evaluated to weak head normal form first, and then the value of e2 is returned. In the following parallel nfib function, seq is used to force the evaluation of n2 before the addition takes place. This is because Haskell does not specify which operand is evaluated first, and if n1 was evaluated before n2, there would be no parallelism.

nfib :: Int -> Int
nfib n | n <= 1    = 1
       | otherwise = n1 ‘par‘ (n2 ‘seq‘ n1 + n2 + 1)
                     where
                       n1 = nfib (n-1)
                       n2 = nfib (n-2)

Accidents always Come in Threes: A Case Study of Data-intensive Programs in Parallel Haskell (page 2 of 14).

2.1 The need forpseq

The pseq combinator is used for sequencing; informally, it evaluates its first argument to weak-head normal form, and then evaluates its second argument, returning the value of its second argument. Consider this definition of parMap:

parMap f []     = []
parMap f (x:xs) = y ‘par‘ (ys ‘pseq‘ y:ys)
   where y  = f x
         ys = parMap f xs

The intention here is to spark the evaluation of f x, and then evaluate parMap f xs, before returning the new list y:ys. The programmer is hoping to express an ordering of the evaluation: first spark y, then evaluate ys.

Runtime Support for Multicore Haskell (page 2 of 12).

Instead of two or more similar primitives with similar purposes, extend the existing seq primitive with the traditional ordering of evaluation for its parameters - first, then second; with the role of simple strictness-control being performed by a new primitive with a more appropriate name e.g. amid, in Strictness without ordering, or confusion.

Atravers 02:00, 7 January 2019 (UTC)