1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Lazy Evaluation with Standard ML</title>
<link rel="shortcut icon" type="image/gif" href="/favicon.ico" />
<style type="text/css">
body {
margin: auto;
padding-left: 10px;
padding-right: 10px;
max-width: 900px;
font-family: sans-serif;
font-size: 18px;
background-color: #222;
color: #ffffef;
}
a {
color: #0ca;
text-decoration: none;
}
a:hover {
color: #c0f;
text-decoration: none;
}
img {
max-width: 600px;
max-height: 400px;
display: block;
margin: auto;
}
pre {
display: block;
background-color: #111;
color: #fff;
padding: 5px;
overflow-x: auto;
}
a.textlink:before {
content: " ⇒ ";
padding-left: 2px;
}
</style>
</head>
<body>
<h1>Lazy Evaluation with Standard ML</h1>
<pre>
_____|~~\_____ _____________
_-~ \ | \
_- | ) \ |__/ \ \
_- ) | | | \ \
_- | ) / |--| | |
__-_______________ /__/_______| |_________
( |---- | |
`---------------'--\\\\ .`--' -Glyde-
`||||
</pre>
<p class="quote"><i>Written by Paul Buetow 2010-05-07</i></p>
<p>In contrast to Haskell, Standard SML does not use lazy evaluation by default but an eager evaluation. </p>
<a class="textlink" href="https://en.wikipedia.org/wiki/Eager_evaluation">https://en.wikipedia.org/wiki/Eager_evaluation</a><br />
<a class="textlink" href="https://en.wikipedia.org/wiki/Lazy_evaluation">https://en.wikipedia.org/wiki/Lazy_evaluation</a><br />
<p>You can solve specific problems with lazy evaluation easier than with eager evaluation. For example, you might want to list the number Pi or another infinite list of something. With the help of lazy evaluation, each element of the list is calculated when it is accessed first, but not earlier.</p>
<h2>Emulating lazy evaluation in SML</h2>
<p>However, it is possible to emulate lazy evaluation in most eager evaluation languages. This is how it is done with Standard ML (with some play with an infinite list of natural number tuples filtering out 0 elements):</p>
<pre>
type ’a lazy = unit -> ’a;
fun force (f:’a lazy) = f ();
fun delay x = (fn () => x) : ’a lazy;
datatype ’a sequ = NIL | CONS of ’a * ’a sequ lazy;
fun first 0 s = []
| first n NIL = []
| first n (CONS (i,r)) = i :: first (n-1) (force r);
fun filters p NIL = NIL
| filters p (CONS (x,r)) =
if p x
then CONS (x, fn () => filters p (force r))
else
filters p (force r);
fun nat_pairs () =
let
fun from_pair (x,0) =
CONS ((x,0), fn () => from_pair (0,x+1))
| from_pair (up,dn) =
CONS ((up,dn), fn () => from_pair (up+1,dn-1))
in from_pair (0,0)
end;
(* Test
val test = first 10 (nat_pairs ())
*)
fun nat_pairs_not_null () =
filters (fn (x,y) => x > 0 andalso y > 0) (nat_pairs ());
(* Test
val test = first 10 (nat_pairs_not_null ());
*)
</pre>
<a class="textlink" href="http://smlnj.org/">http://smlnj.org/</a><br />
<h2>Real laziness with Haskell </h2>
<p>As Haskell already uses lazy evaluation by default, there is no need to construct a new data type. Lists in Haskell are lazy by default. You will notice that the code is also much shorter and easier to understand than the SML version. </p>
<pre>
{- Just to make it look like the ML example -}
first = take
filters = filter
{- Implementation -}
nat_pairs = from_pair 0 0
where
from_pair x 0 = [x,0] : from_pair 0 (x+1)
from_pair up dn = [up,dn] : from_pair (up+1) (dn-1)
{- Test:
first 10 nat_pairs
-}
nat_pairs_not_null = filters (\[x,y] -> x > 0 && y > 0) nat_pairs
{- Test:
first 10 nat_pairs_not_null
-}
</pre>
<a class="textlink" href="http://www.haskell.org/">http://www.haskell.org/</a><br />
<p>E-Mail me your thoughts at comments@mx.buetow.org!</p>
<a class="textlink" href="../">Go back to the main site</a><br />
</body>
</html>
|
