Programming Praxis – Streaming Knapsack

In today’s Programming Praxis exercise, our goal is to write that a function that gives the first possible knapsack, i.e. the first combination of k values that sum up to a given value n, from a lazy list. The list should not be evaluated further than necessary. Let’s get started, shall we?

Some imports:

import Data.List
import Debug.Trace
import System.IO

Rather than constructing a matrix we use a solution that probably isn’t as efficient, but significantly more compact and easy to understand. Just take all possible combinations of numbers and find the first one of length k that sums up to n.

knapsack :: Num a => Int -> a -> [a] -> Maybe [a]
knapsack k n = find (\s -> length s == k && sum s == n) . subsequences

To demonstrate that the function is indeed lazy, we apply it to a list that indicates when one of its elements is evaluated. The hFlush is to make sure the result of the first function is printed before the second list gets evaluated, since without it the two results will be printed at the end.

main :: IO ()
main = do print . knapsack 7 37 $ map debugEval [1..20]
          hFlush stdout
          print . knapsack 7 17 $ map debugEval [1..20]
    where debugEval n = trace ("evaluated: " ++ show n) n

Tags: , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: