[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Mysterious factorial

Subject: Re: [Haskell-cafe] Mysterious factorial
From: Ralf Hinze
Date: Wed, 30 Dec 2009 18:35:48 +0100
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
> 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

<Prev in Thread] Current Thread [Next in Thread>