[Haskell-cafe] Mysterious factorial

[Luke Palmer]

On Wed, Dec 30, 2009 at 10:35 AM, Ralf Hinze <ralf.hinze at comlab.ox.ac.uk> 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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>