Tuesday, February 09, 2010

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!

3 comments:

Anonymous said...

You can write this using foldl1, which just uses the first element of the list as a starting value, so you don't have to pass the 0:

foldl1 (\ n x -> n * 10 + x) [1, 2, 3, 4]

Also, you don't have to use a lambda there, you can just use function composition and partial application on the (+) and (*) operators, like this:

foldl1 ((+) . (10 *)) [1, 2, 3, 4]

Of course, one could argue that this version is not quite as readable :).

Anyway, enjoy your Haskell! :D

Mojo said...

Thanks!

The succinctness of your second example is astounding!

Haskell is opening up to me a world of things I hadn't realised about programming.

Allan said...

IT companies are gaining popularity with every passing day and tend to grow at a rapid speed. Software development company procedures are getting purifies and verified with a brilliant merge of existing and new technologies everyday. Due to the massive demand of automation and perfection, many organizations are now opting outsourcing software development in order to meet their business needs.