Personal tools

Laziness is not always good

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(exercise)
Current revision (16:21, 21 September 2011) (edit) (undo)
m (Removed extra line-breaks.)
 
(2 intermediate revisions not shown.)
Line 1: Line 1:
-
Generally, since Haskell is a [[Non-strict_semantics|non-strict]] language,
+
Generally, since Haskell is a [[Non-strict_semantics|non-strict]] language, you should try to make a function [[maintaining laziness|least strict]].
-
you should try to make a function [[maintaining laziness|least strict]].
+
This is in many cases the best semantics and the most efficient implementation.
This is in many cases the best semantics and the most efficient implementation.
However, here is an important exception from the rule:
However, here is an important exception from the rule:
Line 15: Line 14:
forall a. mappend a mempty = a
forall a. mappend a mempty = a
</haskell>
</haskell>
-
You find that it is not <hask>mappend mempty undefined = undefined</hask>,
+
You find that it is not <hask>mappend mempty undefined = undefined</hask>, but <hask>mappend mempty undefined = mempty</hask>.
-
but <hask>mappend mempty undefined = mempty</hask>.
+
Is this academic nitpicking or practically relevant?
Is this academic nitpicking or practically relevant?
-
I think it is the latter one, because a <hask>Monoid</hask> instance implicitly promises
+
I think it is the latter one, because a <hask>Monoid</hask> instance implicitly promises that monoid laws can be applied in every case.
-
that monoid laws can be applied in every case.
+
A programmer expects that every occurence of <hask>mappend mempty a</hask> can be safely replaced by <hask>a</hask>.
A programmer expects that every occurence of <hask>mappend mempty a</hask> can be safely replaced by <hask>a</hask>.
You might even create an [[Playing by the rules|optimizer rule]] doing this.
You might even create an [[Playing by the rules|optimizer rule]] doing this.
-
The above implementation of <hask>mappend</hask> however evaluates its operands lazily,
+
The above implementation of <hask>mappend</hask> however evaluates its operands lazily, and this gets lost when the optimization is applied.
-
and this gets lost when the optimization is applied.
+
The solution of this issue is to define
The solution of this issue is to define
Line 43: Line 39:
== Exercise ==
== Exercise ==
-
Find out, whether it would help to define <hask>mempty = undefined</hask>.
+
Find out whether it would help to define <hask>mempty = undefined</hask>.
== See also ==
== See also ==
* Haskell-Cafe on [http://www.haskell.org/pipermail/haskell-cafe/2009-January/054261.html Laws and partial values]
* Haskell-Cafe on [http://www.haskell.org/pipermail/haskell-cafe/2009-January/054261.html Laws and partial values]
 +
* Haskell-Cafe on a space leak caused by [http://www.haskell.org/pipermail/haskell-cafe/2010-June/079444.html the garbage collector that did not recognize a selector-like function call]
* [[Maintaining laziness]]
* [[Maintaining laziness]]
[[Category:Idioms]]
[[Category:Idioms]]
[[Category:Style]]
[[Category:Style]]

Current revision

Generally, since Haskell is a non-strict language, you should try to make a function least strict. This is in many cases the best semantics and the most efficient implementation. However, here is an important exception from the rule:

Consider the
Monoid
instance of the null type
()
: 
mempty = ()
mappend _ _ = ()

These functions are least strict, but have a subtle problem: They do not generally satisfy the monoid laws.

Remind you:
mempty
must be the identity element with respect to
mappend
: 
forall a. mappend mempty a = a
forall a. mappend a mempty = a
You find that it is not
mappend mempty undefined = undefined
, but
mappend mempty undefined = mempty
.

Is this academic nitpicking or practically relevant?

I think it is the latter one, because a
Monoid
instance implicitly promises that monoid laws can be applied in every case. A programmer expects that every occurence of
mappend mempty a
can be safely replaced by
a
.

You might even create an optimizer rule doing this.

The above implementation of
mappend
however evaluates its operands lazily, and this gets lost when the optimization is applied.

The solution of this issue is to define 

mempty = ()
mappend () () = ()
 
force :: () -> ()
force _ = ()

and write 

mappend (force a) (force b)
instead of
mappend a b
.

If you find that example too academic, you can choose any other data type with one constructor instead.

1 Exercise

Find out whether it would help to define
mempty = undefined
.

2 See also

Retrieved from "http://www.haskell.org/haskellwiki/Laziness_is_not_always_good"

Categories: Idioms | Style