-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Somebody claiming to be Michael Snoyman wrote:
On Sun, Mar 18, 2012 at 2:21 PM, Gregory Collins
you might be interested in looking at the routing code in scotty, which has some extra features.
Routing there is also O(n) in the number of handlers
The code at play for Yesod is in the Yesod.Routes.Dispatch[1] module. The source[2] is highly commented Literate Haskell, which goes into details of our algorithm, which takes advantage of vectors for an initial O(1) whittling down of possible routes, followed by a series of Map lookups[3], and finally a linear traversal of the remaining routes to address parsing of dynamic pieces. If you avoid overlapping routes (highly recommended), then the last stage will always have either 0 or 1 matches.
Hmm, this also looks interesting. Though it's more of a backend algorithm for a router than a router itself (which is fine). It might be interesting to patch support into Scotty (definitely possible). I wonder what the overhead is (ie: approximately how many routes one needs before the fancy algorithm is faster). - -- Stephen Paul Weber, @singpolyma See http://singpolyma.net for how I prefer to be contacted edition right joseph -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQIcBAEBCAAGBQJPZhd6AAoJENEcKRHOUZzefwQQAJyxhr9cz0HD8vjZTqPURFBL mTZPITi/3MLlxTS+fFPLe0G3QAG3ZgjGkGsx3TQ80kx1X1os9D/BoGHWs2Vi1asv G/7N5Q7GzafrguhgJOReTLkOwztJwVwoB9YBGWCnXd3Ml+ass8pZokvvjwGwt4Ta DVDdP1VAisjSWKB/v5OO3Yxk5l0ekr9Ivml2JiqxnKwQ+E6wRWl7bpVZuHPXU/jD xXwf3PUFtLbKNuL4BLQfr94qaeIVAWObYUnTL92jc+qHL3+QzbDG9vKLNvT1u7WY Wf1WWyRZ3OcrfdhiQyRz8JuhBfjNPxTigc5jmZAhBJ8KhKzGmXChsb/ItD7Dn/BK NHfG9K2Z7bBRkuOBDcnLp25+F6aACugn/sQvKIYd9+6wdyaRNme4xFTg42T/KvYk vTIrUygqZVApjuzWvNEG1jvu1rLzRcfseIG1FVBR2btFWBiRth0HI3RTxZB6pY0l sfDf5Y79cVSaAvcgvvVC1YKZI1Vpp2zVD/5Z0nVkNz7+q8ARfnLunmsDlvtRVdFo vHCuNbYd5Clm66X8ZzCJhRFmpDNwmZo5JOxkxZ8OVxaZZlV/kS5xwlB7a0yiC1ef LC90P0I+rq8sgDlOMnKesKdpY3lJLsGX+rGWUX6cDmQPp5M1HQvJ0LbzsC9t7UuN x4uri5wvjvsHxC7vRQ3u =ZGsM -----END PGP SIGNATURE-----