<div>I thought it could be a nice GHC feature to optimize string lookup, and that using case arrows could be a nice syntax for creating maps.</div><div><br></div><div>We will be fine using a Map. Making sure that sum types are optimized was the important thing, thanks!</div>

<div><div><br><div class="gmail_quote">On Mon, Oct 10, 2011 at 1:14 AM, Simon Peyton-Jones <span dir="ltr">&lt;<a href="mailto:simonpj@microsoft.com">simonpj@microsoft.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">







<div lang="EN-GB" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">Greg<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">In GHC, big cases are done as tables (if dense) or trees (if sparse).  If you have some examples where things go bad, do submit a bug report.<u></u><u></u></span></p>


<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D">For big dispatches on strings, I’m pretty sure we do something linear, top to bottom.   I’d be strongly inclined to use a proper Map structure if you want good
 performance on that.   Is there some reason you don’t want to?<br>
<br>
Simon<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><u></u> <u></u></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">From:</span></b><span lang="EN-US" style="font-size:10.0pt"> <a href="mailto:glasgow-haskell-users-bounces@haskell.org" target="_blank">glasgow-haskell-users-bounces@haskell.org</a> [mailto:<a href="mailto:glasgow-haskell-users-bounces@haskell.org" target="_blank">glasgow-haskell-users-bounces@haskell.org</a>]
<b>On Behalf Of </b>Greg Weber<br>
<b>Sent:</b> 09 October 2011 17:39<br>
<b>To:</b> GHC users<br>
<b>Subject:</b> log time instead of linear for case matching<u></u><u></u></span></p>
</div>
</div><div><div></div><div class="h5">
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">We have a couple use cases in Yesod that can potentially match many different patterns. Routing connects the url of an http request to a Haskell function. The current code just uses a pattern match, which scales linearly. So if a site has
 a hundred different routes (urls), it could take 100 comparisons to finally match the url to a function. Michael Snoyman is writing some code to make this issue obsolete. One of the things it does is use a Map lookup instead of a case match.<u></u><u></u></p>


<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">More worrying is our system for internationalization of a website. A user is supposed to make a sum type with every custom message as a constructor in that sum type.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<div>
<p class="MsoNormal">data Msg = Model<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">         | Year<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">         | Please<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">-- Rendering function for English.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">renderEnglish Model  = &quot;Model&quot;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">renderEnglish Year   = &quot;Year&quot;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">renderEnglish Please = &quot;Please fill in your car&#39;s details&quot;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">-- Rendering function for Swedish.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">renderSwedish Model  = &quot;Modell&quot;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">renderSwedish Year   = &quot;Årgång&quot;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">renderSwedish Please = &quot;Vänligen fyll i uppgifterna för din bil&quot;<u></u><u></u></p>
</div>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">So if there are 100 custom messages on a site, that will setup a case match with potentially 100 comparisons.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Note that we are using this technique for type safety- switching to a map here would be difficult. We want to know at compile time that a translation exists for every message.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">So first of all I am wondering if a sum type comparison does in fact scale linearly or if there are optimizations in place to make the lookup constant or logarithmic. Second, I as wondering (for the routing case) if Haskell can make a string
 case comparison logarithmic so that users can use case comparisons instead of maps for string collections that are known at compile time and won&#39;t change.<u></u><u></u></p>
</div>
</div></div></div>
</div>
</div>

</blockquote></div><br></div></div>