単項演算子の下でコンテナーのクロージャーを計算するための効率的な関数型アルゴリズム (できれば Haskell、さらにできればライブラリの一部として既に実装されているもの) に興味があります。
リストについて、私が考えている基本的で非効率的な例は次のとおりです。
closure :: Ord a => (a -> a) -> [a] -> [a]
closure f xs = first_dup (iterate (\xs -> nub $ sort $ xs ++ map f xs) xs) where
first_dup (xs:ys:rest) = if xs == ys then xs else first_dup (ys:rest)
より効率的な実装では、各段階で生成された新しい要素 (「フリンジ」) を追跡し、既に適用されている要素には関数を適用しません。
closure' :: Ord a => (a -> a) -> [a] -> [a]
closure' f xs = stable (iterate close (xs, [])) where
-- return list when it stabilizes, i.e., when fringe is empty
stable ((fringe,xs):iterates) = if null fringe then xs else stable iterates
-- one iteration of closure on (fringe, rest); key invariants:
-- (1) fringe and rest are disjoint; (2) (map f rest) subset (fringe ++ rest)
close (fringe, xs) = (fringe', xs') where
xs' = sort (fringe ++ xs)
fringe' = filter (`notElem` xs') (map f fringe)
例として、xs
が の空でないサブリストである[0..19]
場合、closure' (\x->(x+3)`mod`20) xs
は [0..19] であり、反復は の場合は 20 ステップ、 の[0]
場合は 13 ステップ、 の[0,1]
場合は 4 ステップで安定します[0,4,8,12,16]
。
ツリーベースの順序付きセットの実装を使用すると、さらに効率が向上します。これはすでに行われていますか?2 項 (またはより高いアリティ) 演算子の下でのクロージャに関する、関連はあるが難しい問題についてはどうでしょうか?