[Haskell-cafe] Re: The Knight's Tour: solutions please
duncan.coutts at worc.ox.ac.uk
Mon Dec 1 17:02:47 EST 2008
On Mon, 2008-12-01 at 22:48 +0100, Diego Echeverri wrote:
> >>I've created a wiki page,
> >>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)
> 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.
More information about the Haskell-Cafe