On Wed, Dec 30, 2009 at 10:35 AM, Ralf Hinze <[email protected]> wrote: > 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
