[Haskell-cafe] Re: The Knight's Tour: solutions please

[Duncan Coutts]

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