On Mon, 2008-12-01 at 22:48 +0100, Diego Echeverri wrote: > >>I've created a wiki page, > >>http://haskell.org/haskellwiki/The_Knights_Tour > >>I note the LogicT version is the shortest so far. > >>-- Don > > Probably noob question. I was looking into the first solution in the > page and tried to replace > > sortOn f = map snd . sortBy (comparing fst) . map (f &&& id) > for > sortOn' f = sortBy (comparing fst)
Presumably you mean: sortOn' f = sortBy (comparing (f . fst)) > The first one was much faster? Why? Caching. It caches all the calls to f. So f gets called once per-element in the input list rather than every time the sort needs to do a comparison. The number of comparisons sort does is proportional to n * log n. So that's a log factor more calls of f. Presumably f is reasonably expensive in this case, enough to offset the extra book-keeping needed to cache all the calls. Duncan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
