Recursion

Dynamic Programming in Haskell

Submitted by mrd on Thu, 02/22/2007 - 8:57pm.

Dynamic Programming is an algorithm design strategy which can be essentially described as breaking a problem down into subproblems and re-using previously computed results. Sometimes, a problem which appears to take exponential time to solve can be reformulated using a Dynamic Programming approach in which it becomes tractable. The benefit is especially clear when the subproblem solutions overlap considerably. The technique of memoization is a major time-saver in those cases.

A common Haskell newbie question is: how do I memoize? At first, it appears to be a very difficult problem, because access to mutable arrays and hashtables is restricted. It is important to realize that lazy evaluation is actually memoization itself and can be leveraged in that way for the purposes of Dynamic Programming. In fact, as a result, the expression of these algorithms can be more natural and lucid in Haskell than in a strict language.

Here, I am going to examine the classic ``knapsack problem.'' Given a number of items, their values, and their sizes -- what is the best combination of items that you can fit in a limited-size knapsack?

> module Knapsack where > import Control.Monad > import Data.Array > import Data.List > import Test.QuickCheck
I am going to represent items with this data type. Essentially, it is just a tuple of the item itself, its value, and its size. > data Item a = Item { item :: a, > itemValue :: Int, > itemSize :: Int } > deriving (Eq, Show, Ord)
Cells will be used both to represent the solution to the knapsack problem, and as individual cells in the matrix for the Dynamic Programming algorithm. It is a pair consisting of: summed values, and the items in the sack. > data Cell a = Cell (Int, [Item a]) > deriving (Eq, Show, Ord)
This powerset definition is a very neat use of the List monad (which I pulled from the Haskell wiki). You can think of it as saying: for each element in the list, half the possible subsets will include it, and half will not. > powerset :: [a] -> [[a]] > powerset = filterM (const [True, False])
brutepack considers the powerset of the items, cutting out those subsets which are too large in size, and picking the most valuable subset left. As you might figure, this is going to run in O(2^n) thanks to the use of powerset. The definition should be simple to understand and will provide a sound basis for testing the Dynamic Programming alternative. > brutepack :: (Ord a) => Int -> [Item a] -> Cell a > brutepack size items = maximum [ > cellOf subset | > subset <- powerset items, itemsFit subset > ] > where > itemsFit items = sum (map itemSize items) <= size > cellOf items = Cell (sum (map itemValue items), items)

The Dynamic Programming algorithm is as follows:

Consider a matrix where the rows are indexed by size and the columns by items. The rows range from 1 to the size of the knapsack, and the columns are one-to-one with the items in the list.


value = $30     $20    $40
 size =  4       3      5
_item_|_lion___tiger___bear_
      |
     1|
      |
     2|
      |
     3|
      |
     4|        v(2,4)<--.
      |                 |
     5|                 |
      |                 |
     6|                 |
      |                 |
     7|                 |
      |              <--|    
     8|        v(2,8) v(3,8)
      |

This is a diagram where the knapsack has a maximum size allowance of 8, and we want to stuff some animals in it. Each element in the matrix is going to tell us the best value of items by size. That means the answer to the whole problem is going to be found in v(3,8) which is the bottom-rightmost corner.

The value of any one cell in the matrix will be decided by whether it is worthwhile to add that item to the sack or not. In the v(3,8) cell it compares the v(2,8) cell to the left to the v(2,4) cell up above. The v(2,8) cell has no room for the bear, and the v(2,4) cell represents the situation where the bear will fit. So the question, after determining if the bear will fit in the bag at all, is: is value of bear + v(2,4) better than v(2,8)?

This definition of v lends itself to a very nice recursive formulation.

             
              / v(m-1,n)                    if (s_n) > n
              \ 
    v(m,n) = -|      / v(m-1,n)
              /      \
              \ max -|                      otherwise
                     /
                     \ v(m-1,n-(s_n)) + v_n
where s_n is the size of item n and v_n is its value.

A typical implementation of this algorithm might initialize a 2D array to some value representing ``undefined.'' In Haskell, we can initialize the entire array to the correct value directly and recursively because it will not be computed until needed. All that is necessary is to express the data-dependencies, and the order of evaluation will take care of itself.

This code takes the algorithm a little further by tracking a field in each cell that contains a list of the items in the sack at that point.

> dynapack :: Int -> [Item a] -> Cell a > dynapack size items = valOf noItems size > where > noItems = length items > itemsArr = listArray (1,noItems) items > itemNo n = itemsArr ! n > > table = array ((1,1),(noItems,size)) $ > [ > ((m, n), cell m n) | > m <- [1..noItems], > n <- [1..size] > ] > > valOf m n > | m < 1 || n < 1 = Cell (0, []) > | otherwise = table ! (m,n) > > cell m n = > case itemNo m of > i@(Item _ v s) > | s > n || > vL >= vU + v -> Cell (vL , isL) > | otherwise -> Cell (vU + v, i:isU) > where > Cell (vL, isL) = valOf (m - 1) n > Cell (vU, isU) = valOf (m - 1) (n - s)

The matrix is defined in the variable table and valOf is our function v here. This definition very naturally follows from the algorithmic description because there is no problem with self-reference when defining cells in the array. In a strict language, the programmer would have to manually check for the presence of values and fill in the table.

Testing

It's important to be confident that the algorithm is coded correctly. Let's see if brutepack and dynapack agree on test inputs. I will define my own simple data type to customize the randomly generated test data.

> newtype TestItems = TestItems [(Int, Int, Int)] > deriving (Eq, Show, Ord)
> nubWithKey k = nubBy (\a b -> k a == k b) > fst3 (a,b,c) = a > tripleToItem (i,v,s) = Item i v s

The Arbitrary class expects you to define your customly generated test data in the Gen monad. QuickCheck provides a number of handy combinators, and of course you can use normal monadic functions.

sized is a QuickCheck combinator which binds the generator's notion of "size" to a parameter of the supplied function. This notion of "size" is a hint to test-data creators that QuickCheck wants data on the "order of" that size. Of course, what "size" means can be freely interpreted by the author of the function, in this case I am using it for a couple purposes.

The basic idea is simply: create a list of randomly generated tuples of length "size", and choose values and item-sizes randomly from (1, "size"). Notice how the randomly generated tuple is replicated with the monadic combinator replicateM. Then, before returning, just make sure that there are no "repeated items" by running nubWithKey fst3 over the generated list. That will cut out any items with the same name as previous items.

> instance Arbitrary TestItems where > arbitrary = sized $ \n -> do > items <- replicateM n > $ do > i <- arbitrary > v <- choose (1, n) > s <- choose (1, n) > return $ (i, v, s) > return . TestItems . nubWithKey fst3 $ items

With an Arbitrary instance, we can now define a property: it extracts the tuples and creates Items out of them, then tries out both algorithms for equivalence. Note that I am only checking the final values, not the actual items, because there may be more than one solution of the same value.

> prop_effectivePacking (TestItems items) = v1 == v2 > where items' = map tripleToItem items > Cell (v1,_) = brutepack 16 items' > Cell (v2,_) = dynapack 16 items'
Knapsack> verboseCheck prop_effectivePacking 0: TestItems [(1,2,3),(3,2,2)] 1: TestItems [] 2: TestItems [(1,1,1)] 3: TestItems [(2,1,2),(-1,2,3),(0,2,3)] 4: TestItems [(-2,2,2),(-1,1,1),(3,2,3),(4,2,2)] ...

It will progressively check larger "size" samples and you will notice that the brute force algorithm is going to start dragging down performance mightily. On my computer, in the ghci interpreter, brutepack on even just 20 items takes 10 seconds; while dynapack takes almost no time at all.

Conclusion

Algorithms making use of Dynamic Programming techniques are often expressed in the literature in an imperative style. I have demonstrated an example of one such algorithm in a functional language without resorting to any imperative features. The result is a natural recursive expression of the algorithm, that has its advantage from the use of lazy evaluation.

Newbie: Recursive lambda definitions?

Submitted by dokondr on Sat, 03/18/2006 - 1:04pm.

{-
Haskell newbie: Recursive lambda definitions?
Simon Thompson gives the following exercise (10.9) in his "Haskell. The Craft of Functional Programming" book:

10.9 Define a function total

total:: (Int -> Int) -> (Int -> Int)

so that total f is the function which at value n gives the total

f 0 + f 1 + ... + f n

I use 'where' clause to describe the resulting function 'tot':
-}

total:: (Int -> Int) -> (Int -> Int)
total f = tot 
    where
    tot n
	| n >= 0 = (f n) + (tot (n-1))
	| otherwise = 0

test = total f1 4

{-
Q: Is it possible instead of naming and defining a resulting function (such as 'tot' in this example) just use recursive lambda definition? In this example recursion is required to create a function which is a variable sum of another function applications like:

f 0 + f 1 + ... + f n

Giving function a name ('tot' in this case) makes recursive definition possible. But what about lambda recursion? Can it be defined?
-}

All About Monads, A comprehensive guide to the theory and practice of monadic programming in Haskell.

Submitted by shapr on Wed, 02/23/2005 - 12:44pm.

Jeff Newbern's All About Monads is the best monad tutorial I've seen yet!

This tutorial starts with the most basic definition of a monad, and why you might want one. It covers most of the monad instances in the standard libraries, and also includes monad transformers. It wraps up nicely with links to Parsec, category theory, and arrows. You can read it online, or download as a zip file or tarball.

If you've been looking for a good monads tutorial, try this one first!

"Algorithms: A Functional Programming Approach" by Fethi Rabhi and Guy Lapalme

Submitted by shapr on Tue, 02/22/2005 - 11:13am.

Algorithms: A Functional Programming Approach is one of my top ten favorite computer science books. First, it covers the basics of Haskell and complexity theory. Then for each algorithm it gives first an easy to read implementation, and then a more efficient but harder to read implementation. Each of the transformations from clear to fast versions are discussed, and optimizations are explained. This book was also my first introduction to methodical step-by-step algorithmic optimization systems, in this case the Burstall & Darlington system. I've since used the lessons I learned in this book in my commercial work in Python, SQL, Java, and of course Haskell.

The best audience for this book is those who are looking for a second Haskell book, or new to algorithms, or would like to learn how to optimize pure (non-monadic) Haskell code systematically. The sections on top-down design techniques and dynamic programming would be of interest to programmers who are still learning and wish to know more about structuring larger programs.

Even with all that content, this softcover book is only 256 pages (coincidentally binary?), allowing for easy reading in any spare moment.