Haskell Knapsack

Я написал ответ на проблему ограниченного рюкзака с одним из каждого элемента в Scala и попытался перенести его на Haskell со следующим результатом:

knapsack :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> Int -> [ ( Int, Int ) ]
knapsack xs [] _   = xs
knapsack xs ys max =
    foldr (maxOf) [ ] [ knapsack ( y : xs ) ( filter (y /=) ys ) max | y <- ys
        , weightOf( y : xs ) <= max ]

maxOf :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> [ ( Int, Int ) ]
maxOf a b = if valueOf a > valueOf b then a else b

valueOf :: [ ( Int, Int ) ] -> Int
valueOf [ ]        = 0
valueOf ( x : xs ) = fst x + valueOf xs

weightOf :: [ ( Int, Int ) ] -> Int
weightOf [ ]        = 0
weightOf ( x : xs ) = snd x + weightOf xs

Я не ищу за советами о том, как очистить код, чтобы он заработал. Насколько мне известно, он должен делать следующее:

• Для каждого параметра кортежа (в ys)
  • , если общий вес текущего кортежа (y) и промежуточной суммы (xs) меньше, чем вместимость
  • , получить оптимальный рюкзак, содержащий текущий кортеж и текущую сумму (xs), используя доступные кортежи. (в ys) минус текущий кортеж
• Наконец, получите наиболее ценный из этих результатов и верните его

* Edit: * Извините, забыл сказать, что не так ... Итак, компилируется нормально , но дает неправильный ответ. Для следующих входных данных, что я ожидаю и что это дает:

knapsack [] [(1,1),(2,2)] 5
Expect: [(1,1),(2,2)]
Produces: [(1,1),(2,2)]

knapsack [] [(1,1),(2,2),(3,3)] 5
Expect: [(2,2),(3,3)]
Produces: []

knapsack [] [(2,1),(3,2),(4,3),(6,4)] 5
Expect: [(2,1),(6,4)]
Produces: []

Итак, мне было интересно, в чем может быть причина несоответствия?

Решение, благодаря sepp2k:

ks = knapsack []

knapsack :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> Int -> [ ( Int, Int ) ]
knapsack xs [] _   = xs
knapsack xs ys max =
    foldr (maxOf) [ ] ( xs : [ knapsack ( y : xs ) ( ys #- y ) max
                             | y <- ys, weightOf( y : xs ) <= max ] )

(#-) :: [ ( Int, Int ) ] -> ( Int, Int ) -> [ ( Int, Int ) ]
[ ]        #- _ = [ ]
( x : xs ) #- y = if x == y then xs else x : ( xs #- y )

maxOf :: [ ( Int, Int ) ] -> [ ( Int, Int ) ] -> [ ( Int, Int ) ]
maxOf a b = if valueOf a > valueOf b then a else b

valueOf :: [ ( Int, Int ) ] -> Int
valueOf [ ]        = 0
valueOf ( x : xs ) = fst x + valueOf xs

weightOf :: [ ( Int, Int ) ] -> Int
weightOf [ ]        = 0
weightOf ( x : xs ) = snd x + weightOf xs

Что возвращает ожидаемые результаты, см. Выше.