<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:x="urn:schemas-microsoft-com:office:excel" xmlns:p="urn:schemas-microsoft-com:office:powerpoint" xmlns:a="urn:schemas-microsoft-com:office:access" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns:s="uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema" xmlns:b="urn:schemas-microsoft-com:office:publisher" xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet" xmlns:c="urn:schemas-microsoft-com:office:component:spreadsheet" xmlns:odc="urn:schemas-microsoft-com:office:odc" xmlns:oa="urn:schemas-microsoft-com:office:activation" xmlns:html="http://www.w3.org/TR/REC-html40" xmlns:q="http://schemas.xmlsoap.org/soap/envelope/" xmlns:rtc="http://microsoft.com/officenet/conferencing" xmlns:D="DAV:" xmlns:Repl="http://schemas.microsoft.com/repl/" xmlns:mt="http://schemas.microsoft.com/sharepoint/soap/meetings/" xmlns:x2="http://schemas.microsoft.com/office/excel/2003/xml" xmlns:ppda="http://www.passport.com/NameSpace.xsd" xmlns:ois="http://schemas.microsoft.com/sharepoint/soap/ois/" xmlns:dir="http://schemas.microsoft.com/sharepoint/soap/directory/" xmlns:ds="http://www.w3.org/2000/09/xmldsig#" xmlns:dsp="http://schemas.microsoft.com/sharepoint/dsp" xmlns:udc="http://schemas.microsoft.com/data/udc" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:sub="http://schemas.microsoft.com/sharepoint/soap/2002/1/alerts/" xmlns:ec="http://www.w3.org/2001/04/xmlenc#" xmlns:sp="http://schemas.microsoft.com/sharepoint/" xmlns:sps="http://schemas.microsoft.com/sharepoint/soap/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:udcs="http://schemas.microsoft.com/data/udc/soap" xmlns:udcxf="http://schemas.microsoft.com/data/udc/xmlfile" xmlns:udcp2p="http://schemas.microsoft.com/data/udc/parttopart" xmlns:wf="http://schemas.microsoft.com/sharepoint/soap/workflow/" xmlns:dsss="http://schemas.microsoft.com/office/2006/digsig-setup" xmlns:dssi="http://schemas.microsoft.com/office/2006/digsig" xmlns:mdssi="http://schemas.openxmlformats.org/package/2006/digital-signature" xmlns:mver="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mrels="http://schemas.openxmlformats.org/package/2006/relationships" xmlns:spwp="http://microsoft.com/sharepoint/webpartpages" xmlns:ex12t="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:ex12m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:pptsl="http://schemas.microsoft.com/sharepoint/soap/SlideLibrary/" xmlns:spsl="http://microsoft.com/webservices/SharePointPortalServer/PublishedLinksService" xmlns:Z="urn:schemas-microsoft-com:" xmlns:st="&#1;" 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:Wingdings;
        panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@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;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
        {mso-style-priority:34;
        margin-top:0cm;
        margin-right:0cm;
        margin-bottom:0cm;
        margin-left:36.0pt;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
span.EmailStyle17
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page WordSection1
        {size:612.0pt 792.0pt;
        margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
        {page:WordSection1;}
 /* List Definitions */
 @list l0
        {mso-list-id:301498186;
        mso-list-type:hybrid;
        mso-list-template-ids:-1830270476 1665444234 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l0:level1
        {mso-level-start-at:2;
        mso-level-number-format:bullet;
        mso-level-text:\F0B7;
        mso-level-tab-stop:none;
        mso-level-number-position:left;
        text-indent:-18.0pt;
        font-family:Symbol;
        mso-fareast-font-family:Calibri;
        mso-bidi-font-family:"Times New Roman";}
@list l1
        {mso-list-id:538398830;
        mso-list-type:hybrid;
        mso-list-template-ids:-944439568 134807567 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l1:level1
        {mso-level-tab-stop:none;
        mso-level-number-position:left;
        text-indent:-18.0pt;}
ol
        {margin-bottom:0cm;}
ul
        {margin-bottom:0cm;}
-->
</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="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
color:#1F497D">You don&#8217;t want to go overboard here.<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo2"><![if !supportLists]><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1F497D"><span style="mso-list:Ignore">1.<span style="font:7.0pt &quot;Times New Roman&quot;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
color:#1F497D">You *<b>want</b>* a distinct blob of lookup code for each different key type, because you really do want a different lookup structure for each<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo2"><![if !supportLists]><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;color:#1F497D"><span style="mso-list:Ignore">2.<span style="font:7.0pt &quot;Times New Roman&quot;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
color:#1F497D">For the most part you *<b>dont want</b>* a different blob of lookup code for each value type, because almost all of them are represented uniformly
 by a pointer.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
color:#1F497D"><o:p>&nbsp;</o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
color:#1F497D">So it&#8217;s be silly to generate all possible combinations of&nbsp; types.&nbsp; The exception to (2) is that &nbsp;you want different code for a handful of types that you want
 to unbox into the tree structure itself: Int#, Float# etc.&nbsp; It would be good to design a convenient way to do that.&nbsp; It&#8217;s nothing directly to do with associated types.&nbsp; We&#8217;d like to allow Maybe Int#, say, but we don&#8217;t at the moment because that data structure
 would really be represented differently.&nbsp; Some kind of data type and code cloning (a la C&#43;&#43;) is probably the right thing.&nbsp; This is what Max meant by &#8220;just engineering&#8221; but it would require careful thought and design.
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
color:#1F497D"><o:p>&nbsp;</o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
color:#1F497D">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:&quot;Calibri&quot;,&quot;sans-serif&quot;;
color:#1F497D"><o:p>&nbsp;</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:
&quot;Tahoma&quot;,&quot;sans-serif&quot;">From:</span></b><span lang="EN-US" style="font-size:10.0pt;
font-family:&quot;Tahoma&quot;,&quot;sans-serif&quot;"> glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org]
<b>On Behalf Of </b>Johan Tibell<br>
<b>Sent:</b> 12 August 2010 16:56<br>
<b>To:</b> Simon Marlow<br>
<b>Cc:</b> glasgow-haskell-users<br>
<b>Subject:</b> Re: Using associated data types to create unpacked data structures<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p>&nbsp;</o:p></p>
<div>
<p class="MsoNormal">On Thu, Aug 12, 2010 at 11:28 AM, Simon Marlow &lt;<a href="mailto:marlowsd@gmail.com">marlowsd@gmail.com</a>&gt; wrote:<o:p></o:p></p>
<p class="MsoNormal">Rather than try to solve this problem in one go, I would go for a low-tech approach for now: write a TH library to generate the code, and ask the user to declare the versions they need. &nbsp;To make a particular version, the user would say
 something like<br>
<br>
&nbsp;module MapIntDouble (module MapIntDouble) where<br>
&nbsp;import TibbeMagicMapGenerator<br>
&nbsp;make_me_a_map ...<br>
<br>
there's no type class of course, so you can't write functions that work over all specialised Maps. &nbsp;But this at least lets you generate optimised maps for only a little boilerplate, and get the performance boost you were after.<o:p></o:p></p>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
To get a better idea of how many specialized maps the user would have to create under this scheme I ran an analysis of the Chromium codebase [1]. The Chromium codebase is not small but some companies have codebases which are several order of magnitudes larger,
 which makes the results below more of a lower bound than an upper bound on the number of specialized maps one might need in a program.<br>
<br>
&nbsp;&nbsp;&nbsp; $ git clone <a href="http://src.chromium.org/git/chromium.git">http://src.chromium.org/git/chromium.git</a><br>
&nbsp;&nbsp;&nbsp; Initialized empty Git repository in /tmp/chromium/.git/<br>
&nbsp;&nbsp;&nbsp; remote: Counting objects: 548595, done.<br>
&nbsp;&nbsp;&nbsp; remote: Compressing objects: 100% (167063/167063), done.<br>
&nbsp;&nbsp;&nbsp; remote: Total 548595 (delta 401993), reused 477011 (delta 343049)<br>
&nbsp;&nbsp;&nbsp; Receiving objects: 100% (548595/548595), 1.02 GiB | 24.44 MiB/s, done.<br>
&nbsp;&nbsp;&nbsp; Resolving deltas: 100% (401993/401993), done.<br>
&nbsp;&nbsp;&nbsp; $ cd chromium<br>
&nbsp;&nbsp;&nbsp; $ find . -name \*.h -o -name \*.cc -exec egrep -o &quot;map&lt;[^,]&#43;, ?[^&gt;]&#43;&gt;&quot; {} \; | sort -u | wc -l<br>
&nbsp;&nbsp;&nbsp; 220<br>
&nbsp;&nbsp;&nbsp; $ find . -name \*.h -o -name \*.cc -exec w -l {} \; | awk '{tot=tot&#43;$1} END {print tot}'<br>
&nbsp;&nbsp;&nbsp; 81328<br>
<br>
So in a code base of about 80 KLOC there are 220 unique key/value combinations. While the numbers might not translate exactly to Haskell it still indicates that the number of modules a user would have to create (and put somewhere in the source tree) would be
 quite large. <br>
<br>
1. <a href="http://src.chromium.org/git/chromium.git">http://src.chromium.org/git/chromium.git</a><br>
<br>
Cheers,<br>
Johan<o:p></o:p></p>
</div>
</div>
</body>
</html>