[Haskell-cafe] List comprehension order of evaluation

[Jonathan Cast]

On Thu, 2007-10-25 at 19:59 -0200, Maurí­cio wrote:
> Hi,
> 
> Today, if I write:
> 
> [a:[b] | a<-"ab" , b<-"12"]
> 
> I get:
> 
> ["a1","a2","b1","b2"]
> 
> Are there any guarantees that I'll never
> get ["a1","b1","a2","b2"] instead, i.e.,
> that the first list will always be the
> last one to be fully transversed? Even
> if I use a different compiler or a
> future version of Haskell?

> Reading how list comprehensions are
> translated in the Haskell report it
> seems the answer is yes.

Correct.

>  Is that
> written in stone?

Yes.  It's a consequence of the MonadPlus law (for [] and other
non-determinism monads)

(xn `mplus` ys) >>= f = (xn >>= f) `mplus` (ys >>= f)

which implies

  [ f x y | x <- xn ++ xn', y <- ys]
= [ f x y | x <- xn, y <- ys] ++ [ f x y | x <- xn', y <- ys]

(This rule plus the monad laws plus the natural transformation law for
return

  map f (return x) = return (f x)

provides a complete calculation system for list comprehensions, btw.
And those laws are all very much set in stone.)

>  Can compilers do
> it in their own different way?

No.

jcc