24/12/16 15:36:56.21 5AL+G6v+.net
(重さ,価値)のリストを受け取る関数で以下のようなhaskellコードがあったのですが理解できません
何をやっているんでしょうか
sieve :: [(Int, Int)] -> [(Int, Int)]
sieve lis = map snd . filter (\((w1, v1), (w2, v2)) -> v1 < v2) $ adj
where
slis = sort lis
adj = zip (scanl (\(w, v) (w', v') -> (w', max v v')) (0, 0) slis) slis
例えばテストケースに以下のリストを渡すとadjの内容はコメントしたように(3,3)という存在しないデータが出てきます
一応上のフィルタで消えるのですが、常にこれは成り立つ？
[(1,1),(2,3),(3,2),(4,5)] -- [((0,0),(1,1)),((1,1),(2,3)),((2,3),(3,2)),((3,3),(4,5))]
最終的な結果は
[(1,1),(2,3),(4,5)]