[Haskell-cafe] Perfect example

[Hugh Perkins]

There's a neat Haskell solution to the knapsack problem which runs very
fast.  I'm not 100% sure that it runs faster than an optimal solution in
other GC'd imperative languages, but it's very concise and not (too)
convoluted.  Have a search for the thread with "xkcd" in the title.

Chung-chieh Shan wrote:

Here's my solution to the xkcd problem (yay infinite lists):

xkcd_c287' = foldr
       (\cost without ->
           let (poor, rich) = splitAt cost without
               with = poor ++ zipWith (++) rich (map (map (cost:)) with)
           in with)
       ([[]] : repeat [])
       [215, 275, 335, 355, 420, 580] -- [2, 4, 150001]
       !!
       1505 -- 150005

Replacing the two lines with comments by the comments solves your case
quickly.

Explication of how it works from "haskell at list.mightyreason.com":

I will jump in and explain, using a more finely named version:

xkcd_c287' = foldr
        (\cost without ->
            let (poor, rich) = splitAt cost without
                with = poor ++ zipWith (++) rich using_cost
                using cost = (map (add_cost) with)
                  where add_cost xs = cost:xs
            in with)
        ([[]] : repeat [])
        [215, 275, 335, 355, 420, 580] -- [2, 4, 150001]
        !!
        1505 -- 150005

At the top level it uses (!!) to pick the 1505th element of the list
produced by
the use of foldr.

foldr <function to combine new value with previous result>
      <seed result>
      <list of new values>

Here the list of new values is the list of item prices (in pennies) from the
menu.

The seed result is the answer in the absence of anything on the menu.

The seed is ([[]] : repeat []) which is a list of (list of prices).  The "n
th"
member of the outer list holds the solution for a price of "n pennies".

Thus the (!! 1505) selects the answer for a target price of $15.05.

The seed result has an empty list in the 0th position since ordering nothing
is
a solution to a target price of $0.00.

The function works as follows:
>         (\cost without ->

The 'cost' is the price of the new item on the menu.
The 'without' is the answer taking into account all previously processed
items
on the menu (before the 'cost' item).
The result will be a new answer taking into account 'cost' as well.

>             let (poor, rich) = splitAt cost without

The items in the old answer 'without' before the index 'cost' are solutions
for
a target price cheaper than 'cost' and these are in the 'poor' list.  These
answers are unchanged by the addition of the 'cost' item.

The items in the 'rich' part of the answer may get new solutions that
include
ordering the new 'cost' item.

>                 with = poor ++ zipWith (++) rich using_cost
>                 using cost = (map add_cost with)
>                   where add_cost xs = cost:xs
>             in with)

The new answer will be 'with' which is defined recursively.

The first elements of 'with' are the 'poor' parts of the old answer
'without'
that are obviously unchanged.

The 'zipWith (++) rich using_cost' combines the previous 'rich' answers
without
'cost' with a new list that uses the 'cost' item.  This is:

using cost = (map add_cost with)
  where add_cost xs = cost:xs

The using_cost list is made from taking the list of answers and prepending
the
'cost' item to all the solutions.

If this were applied to 'without' instead of 'with'...

using cost = (map add_cost without)
  where add_cost xs = cost:xs

...then the definition of 'with' would not be recursive and would allow for
solutions that only order each menu item 0 or 1 times.

Since the definition of using_cost does apply the map to 'with' it can
add_cost
to answers that already have has add_cost applied to them.  Thus it finds
all
answers that order the menu items 0,1,2,3.. arbitrarily many times.

The "n th" item in 'with' or 'without' has total price of "n", and after
add_cost it has a total price of "cost+n", and must be in the "(cost+n)th"
position in the answer 'with'.  This is achieve by the using_cost items
being
after the (poor ++) which means they have been shifted by (length poor)
positions which, by the definition of (splitN cost), is equal to 'cost'.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070806/7162aba5/attachment.htm