Difference between revisions of "Dynamic programming example"
(add a reference to a good article) 
(→Available in 6packs, 9packs, 20packs: Add a vector version; modernize to Applicative.) 

Line 14:  Line 14:  
<haskell> 
<haskell> 

⚫  
+   This version uses the "array" library. 

⚫  
buyable n = r!n 
buyable n = r!n 

⚫  
+  where 

⚫  
⚫  
⚫  
+  
+   This version uses the "vector" library. 

+  import Data.Vector ((!), generate) 

+  
+  buyable n = r!n 

+  where 

+  r = generate (n+1) f 

+  f i = i == 0  i >= 6 && r!(i6)  i >= 9 && r!(i9)  i >= 20 && r!(i20) 

</haskell> 
</haskell> 

Line 24:  Line 34:  
<haskell> 
<haskell> 

−  import Data.Array 

+   This version uses the "array" library. 

+  import Data.Array((!), listArray) 

buy n = r!n 
buy n = r!n 

−  where r = listArray (0,n) (Just (0,0,0) : map f [1..n]) 

+  where 

−  f i = case attempt (i6) 

+  r = listArray (0,n) (map f [0..n]) 

−  +  f 0 = Just (0,0,0) 

−  +  f i = case attempt (i6) of 

−  +  Just(x,y,z) > Just(x+1,y,z) 

−  +  _ > case attempt (i9) of 

−  +  Just(x,y,z) > Just(x,y+1,z) 

−  +  _ > case attempt (i20) of 

−  +  Just(x,y,z) > Just(x,y,z+1) 

+  _ > Nothing 

+  attempt x = if x>=0 then r!x else Nothing 

+  
+   This version uses the "vector" library. 

+  import Data.Vector ((!), generate) 

+  
+  buy n = r!n 

+  where 

+  r = generate (n+1) f 

+  f 0 = Just (0,0,0) 

+  f i = case attempt (i6) of 

+  Just(x,y,z) > Just(x+1,y,z) 

+  _ > case attempt (i9) of 

+  Just(x,y,z) > Just(x,y+1,z) 

+  _ > case attempt (i20) of 

+  Just(x,y,z) > Just(x,y,z+1) 

+  _ > Nothing 

+  attempt x = if x>=0 then r!x else Nothing 

</haskell> 
</haskell> 

−  Optional: If you know 
+  Optional: If you know Applicatives and that <hask>Maybe</hask> is an Applicative, you can write it in a more regular way: 
<haskell> 
<haskell> 

−  import Data.Array 

+   This version uses the "array" library. 

−  import Control. 
+  import Control.Applicative((<>)) 
+  import Data.Array((!), listArray) 

+  
+  buy n = r!n 

+  where 

+  r = listArray (0,n) (map f [0..n]) 

+  f 0 = Just (0,0,0) 

+  f i = fmap (\(x,y,z) > (x+1,y,z)) (attempt (i6)) 

+  <> 

+  fmap (\(x,y,z) > (x,y+1,z)) (attempt (i9)) 

+  <> 

+  fmap (\(x,y,z) > (x,y,z+1)) (attempt (i20)) 

+  attempt x = if x>=0 then r!x else Nothing 

+  
+   This version uses the "vector" library. 

+  import Control.Applicative((<>)) 

+  import Data.Vector((!), generate) 

buy n = r!n 
buy n = r!n 

−  where r = listArray (0,n) (Just (0,0,0) : map f [1..n]) 

+  where 

−  f i = do (x,y,z) < attempt (i6) 

+  r = generate (n+1) f 

−  +  f 0 = Just (0,0,0) 

−  +  f i = fmap (\(x,y,z) > (x+1,y,z)) (attempt (i6)) 

−  +  <> 

−  +  fmap (\(x,y,z) > (x,y+1,z)) (attempt (i9)) 

−  +  <> 

−  +  fmap (\(x,y,z) > (x,y,z+1)) (attempt (i20)) 

−  +  attempt x = if x>=0 then r!x else Nothing 

−  attempt x = guard (x>=0) >> r!x 

</haskell> 
</haskell> 

This more regular code can be further generalized. 
This more regular code can be further generalized. 
Revision as of 00:45, 7 December 2017
Dynamic programming refers to translating a problem to be solved into a recurrence formula, and crunching this formula with the help of an array (or any suitable collection) to save useful intermediates and avoid redundant work.
Computationally, dynamic programming boils down to write once, share and read many times. This is exactly what lazy functional programming is for.
Contents
Sample problems and solutions
Available in 6packs, 9packs, 20packs
A fast food place sells a finger food in only boxes of 6 pieces, boxes of 9 pieces, or boxes of 20 pieces. You can only buy zero or more such boxes. Therefore it is impossible to buy exactly 5 pieces, or exactly 7 pieces, etc. Can you buy exactly N pieces?
If I can buy i6 pieces, or i9 pieces, or i20 pieces (provided these are not negative numbers), I can then buy i pieces (by adding a box of 6 or 9 or 20). Below, I set up the array r
for exactly that, with r!0
forced to True
to bootstrap the whole thing.
 This version uses the "array" library.
import Data.Array((!), listArray)
buyable n = r!n
where
r = listArray (0,n) (map f [0..n])
f i = i == 0  i >= 6 && r!(i6)  i >= 9 && r!(i9)  i >= 20 && r!(i20)
 This version uses the "vector" library.
import Data.Vector ((!), generate)
buyable n = r!n
where
r = generate (n+1) f
f i = i == 0  i >= 6 && r!(i6)  i >= 9 && r!(i9)  i >= 20 && r!(i20)
You certainly want to know how to buy N pieces, in addition to knowing whether it can be done. I now use the array to hold both kinds of information: r!i
is Nothing
if i pieces cannot be bought, or Just (x,y,z)
if i pieces can be bought, and moreover it can be done by x boxes of 6, y boxes of 9, and z boxes of 20. Below the code for buy
is more tedious (understandably) but is just a natural extension of the logic behind the code of buyable
.
 This version uses the "array" library.
import Data.Array((!), listArray)
buy n = r!n
where
r = listArray (0,n) (map f [0..n])
f 0 = Just (0,0,0)
f i = case attempt (i6) of
Just(x,y,z) > Just(x+1,y,z)
_ > case attempt (i9) of
Just(x,y,z) > Just(x,y+1,z)
_ > case attempt (i20) of
Just(x,y,z) > Just(x,y,z+1)
_ > Nothing
attempt x = if x>=0 then r!x else Nothing
 This version uses the "vector" library.
import Data.Vector ((!), generate)
buy n = r!n
where
r = generate (n+1) f
f 0 = Just (0,0,0)
f i = case attempt (i6) of
Just(x,y,z) > Just(x+1,y,z)
_ > case attempt (i9) of
Just(x,y,z) > Just(x,y+1,z)
_ > case attempt (i20) of
Just(x,y,z) > Just(x,y,z+1)
_ > Nothing
attempt x = if x>=0 then r!x else Nothing
Optional: If you know Applicatives and that Maybe
is an Applicative, you can write it in a more regular way:
 This version uses the "array" library.
import Control.Applicative((<>))
import Data.Array((!), listArray)
buy n = r!n
where
r = listArray (0,n) (map f [0..n])
f 0 = Just (0,0,0)
f i = fmap (\(x,y,z) > (x+1,y,z)) (attempt (i6))
<>
fmap (\(x,y,z) > (x,y+1,z)) (attempt (i9))
<>
fmap (\(x,y,z) > (x,y,z+1)) (attempt (i20))
attempt x = if x>=0 then r!x else Nothing
 This version uses the "vector" library.
import Control.Applicative((<>))
import Data.Vector((!), generate)
buy n = r!n
where
r = generate (n+1) f
f 0 = Just (0,0,0)
f i = fmap (\(x,y,z) > (x+1,y,z)) (attempt (i6))
<>
fmap (\(x,y,z) > (x,y+1,z)) (attempt (i9))
<>
fmap (\(x,y,z) > (x,y,z+1)) (attempt (i20))
attempt x = if x>=0 then r!x else Nothing
This more regular code can be further generalized.
Optimization
Simple dynamic programing is usually fast enough (and as always, profile before optimizing!) However, when you need more speed, it is usually fairly easy to shave an order of magnitude off the space usage of dynamic programming problems (with concomitant speedups due to cache effects.) The trick is to manually schedule the computation in order to discard temporary results as soon as possible.
Notice that if we compute results in sequential order from 0 to the needed count, (in the example above) we will always have computed subproblems before the problems. Also, if we do it in this order we need not keep any value for longer than twenty values. So we can use the old fibonacci trick:
buyable n = iter n (True : replicate 19 False)
where iter 0 lst = lst !! 0
iter n lst = iter (n1) ((lst !! 5  lst !! 8  lst !! 19) : take 19 lst)
At each call of iter, the n parameter contains (total  cur) and the lst parameter stores buyable for (cur1, cur2, cur3, ...). Also note that the indexes change meaning through the cons, so we need to offset the !! indexes by 1.
We can improve this more by packing the bit array:
import Data.Bits
buyable n = iter n 1
where iter :: Int > Int > Bool
iter 0 lst = odd lst
iter n lst = iter (n1) ((lst `shiftL` 1) ..
if lst .&. 0x80120 /= 0 then 1 else 0)
This final version is compiled into a single allocationfree loop.
Further Reading
A good detailed explanation: lazy dynamic programming by Tikhon Jelvis.