Editing Maintaining laziness (section)

=== Maybe, Either, Exceptions ===

Some laziness breakers are visible in type signatures:
<haskell>
decodeUTF8 :: [Word8] -> Either Message String
</haskell>
The <hask>Either</hask> type signals that the function marks decoding-failure by using the <hask>Left</hask> constructor of <hask>Either</hask>.
This function cannot be lazy, because when you access the first character of the result, it must already be computed, whether the result is <hask>Left</hask> or <hask>Right</hask>.
For this decision, the complete input must be decoded.
A better type signature is
<haskell>
decodeUTF8 :: [Word8] -> (Maybe Message, String)
</haskell> 
where the <hask>String</hask> contains as much characters as could be decoded and <hask>Maybe Message</hask> gives the reason for the stop of the decoding.
<hask>Nothing</hask> means the input was completely read, <hask>Just msg</hask> means the decoding was aborted for the reason described in <hask>msg</hask>.
If you touch the first element of the pair, the complete decodings is triggered, thus laziness is broken.
This means you should first process the <hask>String</hask> and look at <hask>Maybe Message</hask> afterwards.

Instead of the unspecific pair type you should use the special type for asynchronous exceptions as found in the [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/explicit-exception explicit exception] package.

Especially in parsers you may find a function, called Wadler's force function.
It works as follows:
<haskell>
force y =
   let Just x = y
   in  Just x
</haskell>
It looks like a complicated expression for <hask>y</hask> with an added danger of failing unrecoverably when <hask>y</hask> is not <hask>Just</hask>.
Its purpose is to use the lazy pattern matching of <hask>let</hask> and to show to the runtime system, that we expect that <hask>y</hask> is always a <hask>Just</hask>.
Then the runtime system does not need to wait until it can determine the right constructor but it can proceed immediately.
This way, a function can be made lazy, also if it returns <hask>Maybe</hask>.
It can however fail, if later it turns out, that <hask>y</hask> is actually <hask>Nothing</hask>. <!-- fail how? To be lazy? Or it is some hideous failure like 'head []'? -->

Using force-like functions is sometimes necessary, but should be avoided for data types with more than one constructor.
It is better to use an interim data type with one constructor and lift to the multi-constructor datatype when needed.
Consider parsers of type <hask>StateT [Word8] Maybe a</hask>.
Now consider the parser combinator <haskell>many :: StateT [Word8] Maybe a -> StateT [Word8] Maybe [a]</haskell>
which parses as many elements of type <hask>a</hask> as possible.
It shall be lazy and thus must be infallible and must not use the <hask>Maybe</hask>.
It shall just return an empty list, if parsing of one element fails.
A quick hack would be to define <hask>many</hask> using a <hask>force</hask> function.
It would be better to show by the type, that <hask>many</hask> cannot fail:
<haskell>many :: StateT [Word8] Maybe a -> StateT [Word8] Identity [a]</haskell>.