オペレータの閉包を計算するための効率的な関数アルゴリズム

Question

単項演算子の下でコンテナの閉包を計算するための効率的な機能アルゴリズム（好ましくは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) 

より効率的な実装は、新しい各段階（「フリンジ」）で生成された要素とのdoesnのトラックを保持しますxsが[0..19]の空でない部分リストである場合、closure' (\x->(x+3)`mod`20) xsは[0..19]であり、反復が安定で、

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) 

例として：「tは、それが既に適用された要素に関数を適用しますの20ステップ、[0,1]の13ステップ、[0,4,8,12,16]の4ステップ。

ツリーベースの順序付けされた実装を使用すると、さらに効率を上げることができます。 これはすでに完了していますか？バイナリ（またはより高いアリティ）演算子でのクロージャの関連するしかしより困難な問題はどうでしょうか？

Answer 1

このようなものは、unordered-containersのHash Array Mapped Trieデータ構造を使用します。順序付けられていないコンテナの場合、memberとinsertはO（分（n、W））です。ここで、Wはハッシュの長さです。

ここでは、解決策セットを幅広く第1の方法で生成する、上記のバリエーションを示します。

data Closed' a = Unchanging | Closed' (a -> a) (HashSet a) (Closed' a) 

close' :: (Hashable a, Eq a) => (a -> a) -> [a] -> Closed' a 
close' iter = build Set.empty where 
    inserter :: (Hashable a, Eq a) => a -> (HashSet a, [a]) -> (HashSet a, [a]) 
    inserter a (set, fresh) | Set.member a set = (set, fresh) 
          | otherwise  = (Set.insert a set, a:fresh) 
    build curr [] = Unchanging 
    build curr as = 
    Closed' iter curr $ step (foldr inserter (curr, []) as) 
    step (set, added) = build set (map iter added) 

-- Only computes enough iterations of the closure to 
-- determine whether a particular element has been generated yet 
-- 
-- Returns both a boolean and a new 'Closed'' value which will 
-- will be more precisely defined and thus be faster to query 
member :: (Hashable a, Eq a) => a -> Closed' a -> (Bool, Closed' a) 
member _ Unchanging = False 
member a c@(Closed' _ set next) | Set.member a set = (True, c) 
           | otherwise  = member a next 

improve :: Closed' a -> Maybe ([a], Closed' a) 
improve Unchanging = Nothing 
improve (Closed' _ set next) = Just (Set.toList set, next) 

seen' :: Closed' a -> HashSet a 
seen' Unchanging = Set.empty 
seen' (Closed' _ set Unchanging) = set 
seen' (Closed' _ set next)  = seen' next 

そして

>>> member 6 $ close (+1) [0] 
... 

>>> fst . member 6 $ close' (+1) [0] 
True