log time instead of linear for case matching

[Greg Weber]

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.

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.

data Msg = Model
         | Year
         | Please

-- Rendering function for English.
renderEnglish Model  = "Model"
renderEnglish Year   = "Year"
renderEnglish Please = "Please fill in your car's details"

-- Rendering function for Swedish.
renderSwedish Model  = "Modell"
renderSwedish Year   = "Årgång"
renderSwedish Please = "Vänligen fyll i uppgifterna för din bil"

So if there are 100 custom messages on a site, that will setup a case match
with potentially 100 comparisons.

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.

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't change.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20111009/b38cc1e0/attachment-0001.htm>