One of Haskell's main features is non-strict semantics, which is implemented by lazy evaluation in all popular Haskell compilers. However many Haskell libraries found on Hackage are implemented as if Haskell were a strict language. This leads to unnecessary inefficiencies, memory leaks and, we suspect, unintended semantics. In this article we want to go through some techniques on how to check lazy behaviour on functions, examples of typical constructs which break laziness without need, and finally we want to link to techniques that may yield the same effect without laziness.
1 Checking laziness
1.1 manual checks
If you want to check whether a function is lazy enough, you may feed it with undefined values.An undefined value can be
The latter one has the advantage that it cannot be hidden by some hacks like "catching" the error in the IO monad.
filter even [0..] filter even ([0..5] ++ undefined)
An automated unit test can check whether infinite or corrupted input data produces correct prefixes.Those tests usually do not fail by returning
testFilter0 = filter even [0..100] `isPrefixOf` filter even [0..] testFilter1 = filter even [0..100] `isPrefixOf` filter even ([0..102]++undefined) testFilter2 = let x = filter even [0..] !! 100 in x==x testFilter3 = let x = filter even ([0..102]++undefined) !! 50 in x==x
1.2 automated checks
If you are lazy when searching for laziness breakers, you may use the automated tool StrictCheck.
*StrictCheck> test1 10 (unzip :: [(Int,Int)] -> ([Int],[Int])) Function seems not to be least strict. Input(s): _|_ Current output: _|_ Proposed output: (_|_, _|_) Continue?
2 Laziness breakers
2.1 Maybe, Either, Exceptions
Some laziness breakers are visible in type signatures:
decodeUTF8 :: [Word8] -> Either Message String
For this decision, the complete input must be decoded. A better type signature is
decodeUTF8 :: [Word8] -> (Maybe Message, String)
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
Instead of the unspecific pair type you should use the special type for asynchronous exceptions as found in the explicit exception package.
Especially in parsers you may find a function, called Wadler's force function. It works as follows:
force y = let Just x = y in Just x
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
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
many :: StateT [Word8] Maybe a -> StateT [Word8] Maybe [a]
It shall just return an empty list, if parsing of one element fails.A quick hack would be to define
many :: StateT [Word8] Maybe a -> StateT [Word8] Identity [a]
2.2 Early decision
2.2.1 List construction
Be aware that the following two expressions are not equivalent.
-- less lazy if b then f x else f y -- more lazy f (if b then x else y)
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
if b then [x] else y:ys
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
let z:zs = if b then [x] else y:ys in z:zs
This error can only caught at run-time which is bad. We can avoid it using the single constructor pair type.
let (z,zs) = if b then (x,) else (y,ys) in z:zs
which can be abbreviated to
uncurry (:) (if b then (x,) else (y,ys))
In the Haskell 98 report the implementation
inits :: [a] -> [[a]] inits  = [] inits (x:xs) = [] ++ map (x:) (inits xs)
is suggested.However you find that
The following implementation does exactly this:
inits :: [a] -> [[a]] inits xt =  : case xt of  ->  x:xs -> map (x:) (inits xs)
See also the article on base cases and identities.
2.2.2 Reader-Writer-State monad
I do not know whether the following example can be simplified. In this form it occurred in a real application, namely the HTTP package.Consider the following action of the
The state of the monad is the input list we fetch the elements from. The reader part provides an element which means that the input is consumed. It is returned as singleton when the caller tries to read from a completely read input. The writer allows to log some information, however the considered action does not output anything to the log.
getN :: Int -> RWS a [Int] [a] [a] getN n = do input <- get if null input then asks (:) else let (fetched,rest) = splitAt n input in put rest >> return fetched
This works in even more many corner cases, but not in the following one.Although
*Test> (\(_a,_s,w) -> w) $ runRWS (getN 5) '\n' undefined *** Exception: Prelude.undefined
Thus we must ensure, that the invoked monadic actions are run independent from the input. Only this way, the run-time system can see that the logging stream is never touched.We start refactoring by calling
getN :: Int -> RWS a [Int] [a] [a] getN n = do input <- get let (fetched,rest) = splitAt n input put rest if null input then asks (:) else return fetched
getN :: Int -> RWS a [Int] [a] [a] getN n = do input <- get let (fetched,rest) = splitAt n input put rest endOfInput <- ask return $ if null input then [endOfInput] else fetched
Now things work as expected:
*Test> (\(_a,_s,w) -> w) $ runRWS (getN 5) '\n' undefined 
We learn from this example, that sometimes in Haskell it is more efficient to call functions that are not needed under some circumstances. Always remind, that the do notation looks only imperative, but it is not imperative.E.g.,
2.3 Strict pattern matching in a recursionConsider the
This function should also work on infinite lists, but the implementation shipped with GHC up to 6.2 failed on infinite lists. What happened?
The reason was that pattern matching was too strict.
Let's first consider the following correct implementation:
partition :: (a -> Bool) -> [a] -> ([a], [a]) partition p = foldr (\x ~(y,z) -> if p x then (x : y, z) else (y, x : z)) (,)
However, how can this work if there is a list without an end?That can be seen when applying the definition of
foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ b  = b foldr f b (a:as) = f a (foldr f b as)
Now we expand this once for an infinite input list, we get
partition p (a:as) = (\ ~(y,z) -> if p a then (a:y, z) else (y, a:z)) (foldr ... (,) as)
Omitting it, would require the evaluation of the whole input list before the first output element can be determined.This fails for infinite lists and is inefficient for finite lists, and that was the bug in former implementations of
Btw. by the expansion you also see, that it would not help to omit the tilde and apply the above 'force' trick to the 'if-then-else' expression.
However, there still remains a small laziness break:There is an unnecessary decision between the pair constructor of the initial accumulator value
partition :: (a -> Bool) -> [a] -> ([a], [a]) partition p = (\ ~(ys,zs) -> (ys,zs)) . foldr (\x ~(y,z) -> if p x then (x : y, z) else (y, x : z)) (,)
2.4 List reversalAny use of the list function
3 Input and Output
In general functions, output of lazily generated data is no problem, whereas lazily reading data requires a sort of a hack and thus caution. Consider the nice program
readFile "source" >>= writeFile "target"
sourceto the file
targetwith constant memory consumption, since
However it fails badly, when a file shall be updated in-place:
readFile "text" >>= writeFile "text" . map toUpper
- The function is needed for deferring the calls tounsafeInterleaveIOuntil the characters are actually needed.hGetChar
- Exceptions, that occur while reading the file, are raised in the code that writes the result of processing the file content to somewhere. I.e. the exceptions produced by can occur in code that has nothing to do with file reading and there is no warning, that they might occur there. Again, I want to advertise the explicit exception package, which helps making the reason for the stop of the file read explicit. Exceptions must still be handled in code, that does not read the file, but the fact that they are explicit helps you to not forget it.readFile
- The file must be closed after it is no longer needed. The documentation says, that the file is put into a semi-closed state. Maybe this means, it uses Weak Reference which lets the garbage collector close the file, once no reference to data of the file exists anymore. However, the garbage collector never works immediately, but in phases. It may be that the file remains open for a long time, maybe until the program exits. The function explicitly closes the file after the last byte is read. The advantage is, that the file is closed immediately. The disadvantage is, that the file is not closed at all, when not all bytes are read. E.g. if a parser encounters a parse error, it has to read the rest of the file anyway, in order to get it closed.Data.ByteString.Lazy.readFile
You can use it like
withFile "source" ReadMode $ \h -> hGetLine h >>= putStrLn
However this is dangerous:If you leak lazily read contents from the file out of
it is very different: I does not work.How can you implement a function like
because the order must be preserved.E.g. in
hGetContents h >>= putStrLn . drop 10
hGetContents h = let go = unsafeInterleaveIO $ liftM2 (:) (hGetChar h) go in go
.In contrast to the standard
(by the way, it does even not handle the end of the file), but the advantage of not relying on some automatism to close the file somewhen is, that you can close the file immediately after you stopped processing its content. The disadvantage is that you must not forget to close the file and must do it only once.
So far we have only considered lazy read. It might also be necessary to trigger write actions when fetching data. Consider a server-client interaction, where data can only be read, when a request was sent before. It would be nice if the request is triggered by reading the result from the server. Such interactions can be programmed using the LazyIO package.
From the above issues, you see that laziness is a fragile thing. Make one mistake and a function, carefully developed with laziness in mind, is no longer lazy. The type system will rarely help you hunting laziness breakers, and there is little support by debuggers.
Thus, detecting laziness breakers often requires understanding a large portion of code, which is against the idea of modularity.
Maybe for your case you will prefer a different idiom, that achieves the same goals in a safer way. See e.g. the Enumerator and iteratee pattern.
5 See also
- Haskell-Cafe on Maintaining laziness
- Haskell-Cafe on How to make code least strict?
- Blog post Lazier function definitions by merging partial values by Conal Elliott
- Laziness is not always good