dec2int and foldl

So, I'm trying to learn Haskell (as well as about functional programming) and I have a book I'm using: Programming in Haskell by Graham Hutton.

At the end of each chapter there are exercises.

Chapter 7 is about higher-order functions and one of the exercises is to create a function dec2int which is of the type dec2int :: [Int] -> Int and takes a list of decimal numbers (i.e. numbers 0 to 9); so given the input [1,2,5,7] dec2int would output 1257. The other stipulation is that the function must use foldl.

Step 1 - define dec2int recursively

My first thought in solving this problem was that I wanted to have a working dec2int function.

dec2int [] = 0 dec2int (x:xs) = x*10^(length xs) + dec2int xs

Not very efficient, obviously, as it has to call length for each call to the function, but it works and gives a general idea as to how to write the function.

Step 2 - define dec2int to the letter but not the spirit of the problem

I spent quite some time trying to understand foldl as it's described in the book. foldl's type is foldl :: (a->b->a)->a->[b]->a. A recursive definition looks like this (taken from the book)

foldl f v [] = v foldl f v (x:xs) = foldl f(f v x) xs

So the function f that's passed into foldl has to take a default value, a current value, and return a value that can be used in the function in place of the default value.

My first successful attempt at this does not seem to me to be in keeping with the spirit of the problem:

xANDpos :: [a] -> [(a,Int)] xANDpos [] = [] xANDpos (x:xs) = (x,len):xNp len xs where len = length xs xNp _ [] = [] xNp (pos + 1) (x:xs) = (x,pos):xNp pos xs dec2int :: [Int] -> Int dec2int xs = foldl dec2int' 0 (xANDpos xs) where dec2int' n (x,pow) = n + x*10^pow

f in this instance is dec2int'. xANDpos is a function that takes a list of something and returns a list of tuples of something and its position in the list, if the list were reversed. Not the best name for the function.

I don't think this is in the spirit of the problem because, while it does accomplish the goal, it adds an extra section of recursion when recursion is meant to be being handled by foldl.

Step 3 - this time with spirit

It took some time, but I finally realised that my first function wasn't the only way to get to the answer. The final version is a lot simpler than the second, and therefore more beautiful.

dec2int :: [Integer] -> Integer dec2int = foldl d2i 0 where d2i n x = n*10 + x

This is also a lot quicker - it doesn't traverse the list multiple times. As you can see, I've changed the type of the function, slightly, to allow for bigger numbers to be produced.

Here is a worked example of how the function functions:

dec2int [3,7,0,4,2] = foldl d2i 0 [3,7,0,4,2] = foldl d2i(d2i 0 3 = 0*10 + 3) [7,0,4,2] = foldl d2i(d2i 3 7 = 3*10 + 7) [0,4,2] = foldl d2i(d2i 37 0 = 37*10 + 0) [4,2] = foldl d2i(d2i 370 4 = 370*10 + 4) [2] = foldl d2i(d2i 3704 2 = 3704*10 + 2) [] = foldl d2i 37042 [] = 37042

The function can also be written as a one liner, using lambda: dec2int = foldl(\n x -> n * 10 + x) 0 however I think the other version is more readable.

The problem I encountered here was that my first assumption was incorrect, i.e. the function I came up with in step 1 was not the only way to solve the problem using recursion.

Lesson learned!