Personal tools

Maintaining laziness

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(introduction and conclusion)
 
(partition)
Line 24: Line 24:
 
reader monad
 
reader monad
   
=== reverse ===
+
=== Strict pattern matching in a recursion ===
   
[[Infinity and efficiency]]
+
The implementation of the <hask>partition</hask> 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:
  +
<haskell>
  +
partition :: (a -> Bool) -> [a] -> ([a], [a])
  +
partition p =
  +
foldr
  +
(\x ~(y,z) ->
  +
if p x
  +
then (x : y, z)
  +
else (y, x : z))
  +
([],[])
  +
</haskell>
  +
  +
...
  +
  +
=== List reversal ===
  +
  +
Any use of the list function <hask>reverse</hask> 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.
   
 
== Alternatives ==
 
== Alternatives ==

Revision as of 17:49, 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

2.2 Early decision

if then else

state monad

reader monad

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.