0

入力で分数ナップザック問題を解こうとしていますが、

[("label 1", value, weight), ("label 2", value, weight), ...]

そして出力、

[("label 1", value, solution_weight), ("label 2", value, solution_weight), ...]

しかし、エラーが発生し続けますcomputeKnapsack:

"Couldn't match expected type `(t1, t2, t0)' with actual type `[a0]`"

何が問題なのか理解できません。3 エントリのタプルのリストを作成しようとしています。単一の 3 エントリのタプルを期待しないようにするにはどうすればよいですか?

fst3 (a,b,c) = a
snd3 (a,b,c) = b
trd3 (a,b,c) = c
fst4 (a,b,c,d) = a
snd4 (a,b,c,d) = b
trd4 (a,b,c,d) = c
qud4 (a,b,c,d) = d

sortFrac (a1, b1, c1, d1) (a2, b2, c2, d2)
  | d1 > d2 = GT
  | d1 <= d2 = LT

fracKnap (x:xs) =
    fractionalKnapsack (x:xs) []

fractionalKnapsack (x:xs) fracList =
    if length (x:xs) <= 1
        then computeKnapsack (sortBy sortFrac (((fst3 x),(snd3 x),(trd3 x),(snd3 x) / (trd3 x)):fracList)) 100
        else fractionalKnapsack xs (((fst3 x),(snd3 x),(trd3 x),(snd3 x) / (trd3 x)):fracList)

computeKnapsack (x:xs) weightLeft =
    if length (x:xs) <= 1
        then (fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x)))
        else (fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x))):(computeKnapsack xs (weightLeft-(floor (weightLeft / (qud4 x))*(qud4 x))))
4

3 に答える 3

7

結果のthen分岐でcomputeKnapsackは単一の 3 タプルですが、else分岐では 3 タプルのリストです。

私はあなたのために書き直すつもりcomputeKnapsackです。エラーが修正されたバージョンから始めます。

computeKnapsack (x:xs) weightLeft =
    if length (x:xs) <= 1
        then [(fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x)))]
        else  (fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x))) : (computeKnapsack xs (weightLeft-(floor (weightLeft / (qud4 x))*(qud4 x))))

computeKnapsack最初に、 の最初の引数が空のリストである場合に何が起こるかを説明します。

computeKnapsack []     _          = []
computeKnapsack (x:xs) weightLeft =
    (fst4 x, snd4 x, ((floor (weightLeft / (qud4 x)))*(qud4 x))) : (computeKnapsack xs (weightLeft-(floor (weightLeft / (qud4 x))*(qud4 x))))

ifこれにより、 -testを取り除くことができ、コード全体が短くなり、理解しやすくなります。

次に、分解しますx。

computeKnapsack []             _          = []
computeKnapsack ((a,b,_,d):xs) weightLeft =
    (a, b, ((floor (weightLeft / d))*d)) : (computeKnapsack xs (weightLeft-(floor (weightLeft / d)*d)))

leftaroundabout の提案に従って、代わりに意味のある名前のレコード タイプを作成することをお勧めします。しかし、タプルを引き続き使用する場合は、パターン マッチングによってタプルを分解する方が、fst4, snd4etc 関数を使用するよりもはるかに明確です。

a繰り返しますが、コードは短くなり、理解しやすくなりましたが、 、b、およびよりも意味のある名前を使用すると役立つ場合がありdます。

この流れで続けることができます：

computeKnapsack []             _          = []
computeKnapsack ((a,b,_,d):xs) weightLeft = (a, b, weight) : (computeKnapsack xs (weightLeft - weight))
  where weight = floor (weightLeft / d) * d

ここで、同じ値が 2 つの異なる場所で計算されていることを発見し、その値を独自の名前付き変数に抽出しました。weight2 回ではなく 1 回だけ計算する必要があるため、computeKnapsackわずかに効率的になりました。さらに重要なことに、私は今何をしているのかを理解しcomputeKnapsackています。

あなたが Haskell の初心者であることは理解しています。より明確な Haskell コードを作成する方法についての建設的な提案として、これを受け取ってください。

于 2012-08-05T17:32:28.850 に答える
2

computeKnapsack問題をより明確に確認できるように、関数を自由にクリーンアップしました。

computeKnapsack (x:xs) weightLeft =
 let e = (fst4 x, snd4 x, floor (weightLeft / qud4 x) * qud4 x)
  in if length (x:xs) <= 1
     then e
     else e:computeKnapsack xs (weightLeft - floor (weightLeft / qud4 x) * qud4 x)

私の変更は純粋に表面的なものでした。私の変更の後でも、あなたのcomputeKnapsack関数はまだ壊れていて、悪いアルゴリズムと悪いコーディングスタイルです。

書き直されたバージョンから、ifステートメントに2つのブランチがあり、1つはタプルを返し、もう1つはタプルのリストを返すことがわかります。最初のブランチを変更して単一の要素を持つリストを返すだけで、これを修正できます。

computeKnapsack (x:xs) weightLeft =
 let e = (fst4 x, snd4 x, floor (weightLeft / qud4 x) * qud4 x)
  in if length (x:xs) <= 1
     then [e]
     else e:computeKnapsack xs (weightLeft - floor (weightLeft / qud4 x) * qud4 x)

また、StackOverflowに3番目の質問を送信する前に、 http：//learnyouahaskell.com/のようなHaskellの入門チュートリアルを完了する時間を取ってください。これは多くの問題を解決するのに役立ちます。

于 2012-08-05T17:43:32.483 に答える
0

のthenでそのエラーをスローする1つの問題fractionalKnapsack。その行computeKnapsackでは、の代わりにタプルを入力として関数を呼び出しますlist。

于 2012-08-05T17:07:13.630 に答える