On Wed, Dec 30, 2009 at 10:35 AM, Ralf Hinze
As an aside, in one of my libraries I have a combinator for folding a list in a binary-subdivision scheme.
foldm :: (a -> a -> a) -> a -> [a] -> a
I would use: foldm :: Monoid m => [m] -> m Which is just a better implementation of mconcat / fold. The reason I prefer this interface is that foldm has a precondition in order to have a simple semantics: the operator you're giving it has to be associative. I like to use typeclasses to express laws. You don't need to prove anything to use a function, but you do often need to prove something to make an instance of a typeclass. Fortunately Monoid already has what we need.
foldm (*) e x | null x = e | otherwise = fst (rec (length x) x) where rec 1 (a : as) = (a, as) rec n as = (a1 * a2, as2) where m = n `div` 2 (a1, as1) = rec (n - m) as (a2, as2) = rec m as1
Then factorial can be defined more succinctly
factorial n = foldm (*) 1 [1 .. n]
Cheers, Ralf _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe