Personal tools

Maintaining laziness

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(if and list construction)
(sketch for problems in State and Reader monad)
Line 31: Line 31:
   
 
=== Early decision ===
 
=== Early decision ===
  +
  +
<!-- ==== List construction ==== -->
   
 
Be aware that the following two expression are not equivalent.
 
Be aware that the following two expression are not equivalent.
Line 86: Line 88:
 
</haskell>
 
</haskell>
   
  +
<!-- in my special application this was a problem, however how can I reproduce it in a compact form?
   
state monad
+
==== State monad ====
  +
  +
Consider the following action of the <hask>Control.Monad.State</hask> which fetches a certain number of elements from a list.
  +
The state of the monad is the input list we fetch the elements from.
  +
When the list is empty, this means we encountered the end of input and flag this with a <hask>Left</hask> in the monadic result.
  +
<haskell>
  +
getN :: Int -> State [a] (Either String [a])
  +
getN n =
  +
do input <- get
  +
if null input
  +
then return (Left "end of input reached")
  +
else let (fetched,rest) = splitAt n input
  +
in put rest >> return (Right fetched)
  +
</haskell>
  +
As we learned as good imperative programmers, we only call <hask>splitAt</hask> when the input is non-empty,
  +
that is, only if there is something to fetch.
  +
This is however bad for laziness.
   
reader monad
+
==== Reader monad ====
  +
-->
   
 
=== Strict pattern matching in a recursion ===
 
=== Strict pattern matching in a recursion ===

Revision as of 22:25, 28 December 2008

One of Haskell's main features is non-strict semantics, which in is implemented by lazy evaluation in all popular Haskell compilers. However many Haskell libraries found on Hackage are implemented just as if Haskell would be 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.

Contents

1 Checking laziness

undefined, cycles

unit tests

2 Laziness breakers

2.1 Maybe, Either, Exceptions

Wadler's force function

The following looks cumbersome:

let (Just x) = y
in  Just x
It looks like a complicated expression for
y
, with an added danger of failing unrecoverably when
y
is not
Just
.

...

parsers - leave Maybe where no Maybe is required

2.2 Early decision

Be aware that the following two expression are not equivalent.

-- less lazy
if b then f x else f y
-- more lazy
f (if b then x else y)
It is
if undefined then f x else f y
is
undefined
, whereas
f (if b then x else y)
if
f undefined
,

which is a difference in non-strict semantics.

Consider e.g.
if b then 'a':x else 'a':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
null (if undefined then [x] else y:ys)
again
undefined
, but we like to have it evaluated to
False
. Here we need lazy pattern matching as provided by
let
.
let z:zs =
      if b
        then [x]
        else y:ys
in  z:zs
This expression always returns the constructor
(:)
and thus
null
knows that the list is not empty. However, this is a little bit unsafe, because the
let z:zs
may fail if in the branches of
if
there is an empty list.

This error can only catched 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))


2.3 Strict pattern matching in a recursion

The implementation of the
partition
function in GHC up to 6.2 failed on infinite lists.

What happened? The reason was a too strict pattern matching.

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))
      ([],[])

...

2.4 List reversal

Any use of the list function
reverse
should alert you,

since when you access the first element of a reversed list, then all nodes of the input list must be evaluated and stored in memory. Think twice whether it is really needed. The article Infinity and efficiency shows how to avoid list reversal.

3 Alternatives

From the above issues you see that it laziness is a fragile thing. Only one moment where you do not pay attention and a function, carefully developed with laziness in mind, is no longer lazy, when you call it. The type system can almost not help you hunting laziness breakers and there is little support by debuggers. Thus detection of laziness breakers, often requires understanding of a large portion of code, which is against the idea of modularity. Maybe for your case you might prefer a different idiom, that achieves the same goals in a safer way. See e.g. the Enumerator and iteratee pattern.