組み合わせ
こちらも、
「プログラミングコンテストチャレンジブック」にあった問題です。
整数nと、いくつかの数字列が与えられたときに、 与えられた数字列から重複を許して4つ値を取り出したとき、 その和がnになるかの姓があるかどうか
という問題があります
まずは素直に、リスト内包表記で解きましょう
main = getLine >>= print.answer.map read.words answer :: [Int] -> Bool answer (n:xs) = any (==n) [a+b+c+d | a<-xs , b<-xs , c<-xs , d<-xs]
当然これで答えは出ます。
anyを使っているのでこれは、
どれか一つでも条件を満たすものが出た時点で残りのリストは評価しません。
実際、
main = print.answer $ [1..1000000] answer :: [Int] -> Bool answer (n:xs) = any (==n) [a+b+c+d | a<-xs , b<-xs , c<-xs , d<-xs]
では処理はなかなか終了しませんでしたが、
main = print.answer $ (100,[1..1000000]) answer :: [Int] -> Bool answer (n:xs) = any (==n) [a+b+c+d | a<-xs , b<-xs , c<-xs , d<-xs]
などではすぐに評価が終わります。
遅延評価って便利。