log time instead of linear for case matching

Edward Z. Yang ezyang at MIT.EDU
Sun Oct 9 19:05:51 CEST 2011

Excerpts from Greg Weber's message of Sun Oct 09 12:39:03 -0400 2011:
> 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.

GHC will compile case-matches over large sum types into jump tables,
so the lookup becomes constant.  I don't think we have any cleverness for


More information about the Glasgow-haskell-users mailing list