- 関数型プログラミング言語Haskell Part25
709 ：デフォルトの名無しさん[]：2014/05/18(日) 01:28:02.75 ID:oFqJpTun - ある本にあった、"数字の列kからn個取り出してその和がmかどうか調べる"という問題を
下記のように作ったんだけど、組み合わせのリストを作るのに苦労した。
もっとうまいやり方ありません？
checkComb:: Int -> Int -> [Int] -> String
checkComb _ _ [] = "No"
checkComb 0 _ _ = "No"
checkComb n m k = if elem m sumList then "Yes" else "No"
where cb = makeCombList n [([], k)]
sumList = [foldl (+) 0 (fst l) | l<-cb]
makeCombList :: Int -> [([Int],[Int])] -> [([Int],[Int])]
makeCombList n input
| n == 0 = input
| otherwise = makeCombList (n-1) (foldr (++) [] (map f input))
where f it = [(x:(fst it), List.delete x (snd it)) | x<-(snd it)]
| - 関数型プログラミング言語Haskell Part25
711 ：デフォルトの名無しさん[]：2014/05/18(日) 11:58:12.01 ID:oFqJpTun - >>710 ありがと
後でもっと自然に再帰的に書けると思って変更してみた。
checkComb:: Int -> Int -> [Int] -> String
checkComb _ _ [] = "No"
checkComb 0 _ _ = "No"
checkComb n m k = if elem m sumList then "Yes" else "No"
where cb = makeCombList n k
sumList = [foldl (+) 0 l | l<-cb]
makeCombList :: Int -> [Int] -> [[Int]]
makeCombList 0 input = [[]]
makeCombList 1 input = [[a] | a<-input]
makeCombList n input = concat $ map f input
where f a = map (a:) $ makeCombList (n-1) (Data.List.delete a input)
けど、710の方が簡潔ですね。
べき集合のリストを作る→必要な分だけ取り出す みたいな感じにする方が、
遅延評価があるhaskellらしいプログラムになるのか。(計算量は同じ？)
|
|