組み合わせのリストに対してある種の比較を実行したいとします。たとえば、次のようになります。
combs [] r = [r]
combs (x:xs) r = combs xs (x:r) ++ combs xs r
answer = minimumBy (\a b -> compare (length . compress $ a)
(length . compress $ b)) list
where compress =
...something complicated involving values external to the list.
*Main> combs "ABCD" [] --Imagine a larger list of larger combinations.
["DCBA","CBA","DBA","BA","DCA","CA","DA","A",
"DCB","CB","DB","B","DC","C","D",""]
(実際のリストは、文字列の組み合わせのより複雑な構造になりますが、同様の無駄であり、x
組み合わせ全体の妥当性についての洞察を提供するものはありません)
リストが非常に大きくなった場合、リスト全体を表す値で比較を呼び出すよりも、不適切な組み合わせを作成して破棄するときに何らかの結果を更新する方が効率的でしょうか?
例: (疑似)
loop = do c <- nextComb
if c > r then c else r
loop
Haskell でそれを行うにはどうすればよいでしょうか? または、Haskell のコンパイラanswer
は、リストの要素を自動的に破棄して値を最適化しますか? それとも、私が見逃しているかもしれない何か他のものですか?