Editing Maintaining laziness (section)

==== List construction ====

Be aware that the following two expressions are not equivalent.
<haskell>
-- less lazy
if b then f x else f y
-- more lazy
f (if b then x else y)
</haskell>
It is <hask>if undefined then f x else f y</hask> is <hask>undefined</hask>, whereas <hask>f (if b then x else y)</hask> is <hask>f undefined</hask>, which is a difference in [[non-strict semantics]].
Consider e.g. <hask>if b then 'a':x else 'a':y</hask>.

It is common source of too much strictness to make decisions too early and thus duplicate code in the decision branches.
Intuitively spoken, the bad thing about [[code duplication]] (stylistic questions put aside) is, that the run-time system cannot see that in the branches, some things are equal and do it in common before the critical decision.
Actually, the compiler and run-time system could be "improved" to do so, but in order to keep things predictable, they do not do so.
Even more, this behaviour is required by theory, since by pushing decisions to the inner of an expression you change the semantics of the expression.
So we return to the question, what the programmer actually wants.

Now, do you think this expression
<haskell>
if b
  then [x]
  else y:ys
</haskell>
is maximally lazy?
It seems so, but actually it is not. In both branches we create non-empty lists, but the run-time system cannot see this.
It is <hask>null (if undefined then [x] else y:ys)</hask> again <hask>undefined</hask>, but we like to have it evaluated to <hask>False</hask>.
Here we need lazy pattern matching as provided by <hask>let</hask>.
<haskell>
let z:zs =
      if b
        then [x]
        else y:ys
in  z:zs
</haskell>
This expression always returns the constructor <hask>(:)</hask> and thus <hask>null</hask> knows that the list is not empty.
However, this is a little bit unsafe, because the <hask>let z:zs</hask> may fail if in the branches of <hask>if</hask> there is an empty list.
This error can only caught at run-time which is bad.
We can avoid it using the single constructor pair type.
<haskell>
let (z,zs) =
      if b
        then (x,[])
        else (y,ys)
in  z:zs
</haskell>
which can be abbreviated to
<haskell>
uncurry (:) (if b then (x,[]) else (y,ys))
</haskell>

Another example is the <hask>inits</hask> function.
In the Haskell 98 report the implementation
<haskell>
inits        :: [a] -> [[a]]
inits []     = [[]]
inits (x:xs) = [[]] ++ map (x:) (inits xs)
</haskell>
is suggested.
However you find that <hask>inits undefined</hask> is undefined, although <hask>inits</hask> always should return the empty list as first element.
The following implementation does exactly this:
<haskell>
inits :: [a] -> [[a]]
inits xt =
   [] :
   case xt of
      [] -> []
      x:xs -> map (x:) (inits xs)
</haskell>
See also the article on [[base cases and identities]].