[Haskell-cafe] xkcd #287 "NP-Complete"

[Henning Thielemann]

On Tue, 10 Jul 2007, Donald Bruce Stewart wrote:

> These smaller NP problems really love the list monad. here's roconnor's
> solution from #haskell:
>
>     import Control.Monad
>
>     menu = [("Mixed Fruit",215),("French Fries",275)
>            ,("Side Salad",335),("Hot Wings",355)
>            ,("Mozzarella Sticks",420),("Sampler Plate",580)]
>
>     main = mapM_ print
>             [ map fst y
>             | i <- [0..]
>             , y <- replicateM i menu
>             , sum (map snd y) == 1505 ]

Shouldn't we stay away from integer indices on lists?

[ map fst y |
    y <- concat (iterate (liftM2 (:) menu) [[]]),
    sum (map snd y) == 1505]