Haskell Homework - Decimal List [Int] -> Int

Question

The assignment is to define function decimal :: [Int] -> Int in which a list of positive ints is to give the decimal number so that the list [1,4,3,1,9] is to return the Integer 14319. I am to use the fold function.

I don't really have good idea to start here, so I just need a push in the right direction, but I was thinking about the Horner-scheme. Thanks!

Answer 1

This is my variant

import Data.List
decimal :: [Int] -> Int
decimal xs = foldl' (\sum (pos,x) -> (sum + x*(10^(l-pos)))) 0 $ zip [1..] xs where
            l = length xs


*Main> decimal [1,4,3,1,9]
14319

In Haskell, you have really powerfull weapon - functions for lists processing. One of these functions is foldl (we use strict version of foldl, foldl') It's type

foldl :: (a -> b -> a) -> a -> [b] -> a

This functions takes thre arguments, an accumulating agrument, a list processed, and, the most interest, the function that perform any operation with accumulator and list element and returns the result. Fold is really significant function so you should read detail manual about it.
But, there is a problem, we have three variables it our equation: list element processed (x), total list length (n) and position of processed element (k). But we can traverse to foldl only one element. How can we traverse position of each element? Let's form tuples from Int where first element is a position, and second is a value. It is a standard trick, zip function helps us:

zip [1..] [1,4,3,4,6]
[(1,1),(2,4),(3,3),(4,4),(5,6)]

Than we pass our list of tuples into foldl function, and foldl call lambda function (\sum (pos,x) -> (sum + x*(10^(l-pos)))) for each element of list, summing result in sum

Answer 2

In the fold, you start from the left and move towards the right. As you consume the next element from the list, you multiply what you already had by 10 and add the new element to that.

So if you seed the foldl with 0, and had [1,2,3], your function would multiply current (0) by 10 (also 0), then add 1. Moving on, multiply current (1) by 10 (to get 10) and add 2 (12). Then finally for 3, 12 * 10 = 120, 120 + 3 = 123.

That should be pretty easy to code up :)

Answer 3

Maybe this equation would guide you.

Answer 4

Since this is a homework, let's stop at the suggestion that you expand this expression for some list, and try to extract a recurrent relationship:

x_0*10^n+x_1*10^(n-1)+...+x_n*10^0 = (((x_0*10+x_1)*10+x_2)...)*10+x_n

If you compare this to folds, you will see one fold matches this pattern for a particular function of two arguments.