[Haskell-cafe] Fannkuch Entry

[David F.Place]

On Jan 6, 2006, at 11:48 AM, Sebastian Sylvan wrote:
>
> Yes, Bertram's is faster. But it's also a lot less readable, IMO. It
> uses explicit recursions instead of standard library functions, and
> extra complexities here and there. The usage of >>= (and the list
> monad) is one example,

You can substitute this equivalent definition without penalty

permutations l = foldr perm' [l] [2..length l] where
     perm' n l = concatMap (take n . iterate (rotate n)) l



> but have a look at the flop function. I can
> only speak for myself but to me that's pretty difficult to understand,
> and I really doubt that anyone who hasn't done a significant amount of
> Haskell programming will grasp it at all.

However, it is just the kind of haskell programming that you might  
need to do to make a program run fast.  It's rather elegant compared  
to what you would need to do in an imperative language, yes-no?


>
> So like it says on the wiki, I wrote the most obvious and clear
> solution I could come up with, which proved to be several times faster
> than the existing Haskell solution in the shootout. I do not claim
> that it's the fastest solution possible (in fact, I knew it wasn't)
> but it does *no* optimizations that hurt clarity (by design!).

Well, if I make the following change to your program it doesn't have  
any effect on its performance.

-- fannuch xs = foldl' max 0  $ map flop xs
fannuch xs = foldl max 0  (map flop xs)

The strict foldl and strict apply do seem to be examples of  
optimizations that hurt clarity, but in this case don't seem to help  
performance.

Cheers, David

--------------------------------
David F. Place
mailto:d at vidplace.com