[Haskell-cafe] Horner's Rule, foldl, and direct recursion

[Daniel Fischer]

Am Mittwoch, 11. März 2009 00:58 schrieb R J:
> Given a list of decimal digits represented by Integers between 0 and 9--for
> example, the list [1,2,3, 4]--with the high-order digit at the left, the
> list can be converted to a decimal integer n using the following formula,
> an instance of Horner's rule:
>
>               n = 10 *  10 * 10 * 1 + 10 * 10 * 2 + 10 * 3 + 4
>                 = 10 * (10 * 10 * 1 + 10 * 2 + 3) + 4
>                 = 10 * (10 *(10 * 1 + 2) + 3) + 4
>
> In Haskell, the foldl function neatly captures this pattern:
>
> horner          :: [Integer] -> Integer
> horner          =  myFoldl timesPlus 0
>                    where timesPlus x y = 10 * x + y
>
> What is the direct recursive calculation of this function without using the
> call to foldl?  In other words, what's the second equation of:
>
> horner2          :: [Integer] -> Integer
> horner2 []       =  0
> horner2 (x : xs) =  ?
>
> Given that we've already got the definition using foldl, it ought to be
> easy to express the second equation, but it's eluding me.
>
> Thanks.

horner2 (x:xs) = go x xs
   where
      go m [] = m
      go m (y:ys) = go (10*m+y) ys

But I always write it as

foldl' ((+) . (*10)) 0