<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page Section1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-GB link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Philip<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Thanks for your email. We are quite good at lazily
reading (and <b>caching</b>) things – an example is hGetContents -- but
at the moment we don’t have a good mechanism for <b>un-caching</b>
things. That is, taking a big data structure, throwing it away, and
replacing it with a thunk. Clearly we need programmer help to know
when and how to do this.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>As luck would have it, I was talking with Conal Eliot about just
such a mechanism at ICFP. Here’s the idea.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Suppose we have<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> data
Revertable a b = REV (a->b) a b<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> mkRevertable
:: (a->b) -> a -> Revertable a b<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> getValue
:: Revertable a b -> b<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>The idea is that a value (REV f x v) is a kind of thunk: it has
code (f), its argument (x), and its value (v). If the garbage collector
is short of space, it’s free to rewrite<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> REV
f x v --> REF f x (f x)<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>thereby discarding v in favour of a small thunk (f x).<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>In your case (f x) would fetch data from the disk again.
[Which involves I/O but I assume that you are willing to promise that teh data
isn’t changing, so unsafePerformIO is ok.]<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>The main thing I’m unhappy about is that if the user of a
Revertable does something like <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> let
x = tail (getValue r)<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>and evaluates x, then he has a pointer into the value ‘v’
(inside that Revertable), so it’ll be retained after all. But I guess
you just have Revertables every so often in the structure, at a granularity you
decide.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Anyway none of this is implemented. But it doesn’t look
too hard. Maybe an intern.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Simon<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p> </o:p></span></p>
<div style='border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt'>
<div>
<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'>
<p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:
"Tahoma","sans-serif"'>From:</span></b><span lang=EN-US style='font-size:10.0pt;
font-family:"Tahoma","sans-serif"'> Philip Scott
[mailto:Philip.Scott@cantabcapital.com] <br>
<b>Sent:</b> 20 October 2009 20:17<br>
<b>To:</b> Simon Peyton-Jones<br>
<b>Subject:</b> Haskell fun<o:p></o:p></span></p>
</div>
</div>
<p class=MsoNormal><o:p> </o:p></p>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Hi
Simon,</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal> <o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Thanks
for coming in the other day, it was very interesting to hear what you had to
say. Just finished reading your bit in "Coders at Work" too, very
enlightening. Inspired, I downloaded ghc and have been having a play. I've got
a little pet problem, and was wondering if you might have any insight to offer.
It is related to my question I had for you about timeseries data, if you can
remember it!</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal> <o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>So
here is the problem:</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal> <o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>I
have a large (very, ~2 gigabytes) list of <timestamp, value>
pairs stored in a file. I would like to interact with this thing as a
bidirectional lazy stream with the ability to do random access. But what
would really be crucial is the ability to have some kind of cache, both for the
initial data fetching and for any expensive operations I perform later. Can you
think of any way of doing this nicely and efficiently in haskell?</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal> <o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>For
example, I might like to say</span><o:p></o:p></p>
</div>
<blockquote style='margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt'>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>mystream =
stream("foo.bin")</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>mystream.find(
time("1 Jul 09, 10:00:00 ") )</span><o:p></o:p></p>
</div>
</blockquote>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>And
then get some values and either increment or decrement my pointer with
something like</span><o:p></o:p></p>
<blockquote style='margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt'>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>mystream.next</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>mystream.prev</span><o:p></o:p></p>
</div>
</blockquote>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>The
hard bit, so far as I can se, would be the ability to keep mystream around
(e.g. in an interactive program), along with a cache of the values it has already
found so that if I ask the same question I don't have to return to the file.
Some ability to manage the cache (e.g. size limit it, get rid of the least
accessed etc..) would be handy as well.</span><o:p></o:p></p>
</div>
<div>
<div>
<p class=MsoNormal> <o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>That
part doesn't _feel_ very functional, but I really love the composibility
of lazy streams of operations. It works just great when I am just zipping
through a whole file spurting the data out but in an more interactive way I
have got stuck.</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal> <o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>I
appreciate you're a busy chap, don't worry too much if you do not get chance to
answer; I've got Duncan and haskell-beginners to bother next :)</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal> <o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Thanks,</span><o:p></o:p></p>
</div>
<div>
<p class=MsoNormal> <o:p></o:p></p>
</div>
<div>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Philip</span><o:p></o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>