Shouldn't head xs give an exception on an empty list?
An error, and only if it's evaluated. Lazy evaluation means it's not evaluated here.
Of course another non-strict algorithm *might* evaluate head xs here, so this version won't work in all possible Haskell implementations, only the current ones which use lazy evaluation.