Is lazy evaluation required for do-notation?
It is not required that the language is lazy. The do notation exists in SML family of languages (for instance OCaml), which are eager. In these languages the do-notation is written as the let-notation, that is, instead of writing

do x1 &lt;- e1
   x2 &lt;- e2
   ...
   return e


we write

let x1 = e1 in
let x2 = e2 in
...
e


Note however that let in OCaml has a fixed monad (what in Haskell would be the IO monad), whereas the do notation in Haskell works for any monad. There are extensions of OCaml which allow you to use any monad.