[Haskell-cafe] Horner's Rule, foldl, and direct recursion
R J
rj248842 at hotmail.com
Tue Mar 10 19:58:45 EDT 2009
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.
_________________________________________________________________
Windows Live™ Groups: Create an online spot for your favorite groups to meet.
http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090310/380ea307/attachment.htm
More information about the Haskell-Cafe
mailing list