Algoritmo funzionale efficiente per il calcolo della chiusura sotto un operatore

Question

Sono interessato ad algoritmi funzionali efficienti (preferibilmente in Haskell, e ancor più preferibilmente già implementati come parte di una libreria!) Per calcolare la chiusura di un contenitore con un operatore unario.

un esempio di base e inefficiente di quello che ho in mente, per le liste, è:

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) 

Un'implementazione più efficiente mantiene tracce dei nuovi elementi generati in ogni fase (la "frangia") e doesn 't applicare la funzione di elementi di cui è già stato applicato:

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) 

ad esempio, se xs è un elenco secondario vuoto di [0..19], quindi closure' (\x->(x+3)`mod`20) xs è [0..19], e l'iterazione stabilizza in 20 passaggi per [0], 13 passaggi per [0,1] e 4 passaggi per [0,4,8,12,16].

È possibile ottenere un'efficienza ancora maggiore utilizzando un'implementazione di serie ordinata basata su albero. È già stato fatto? Che ne è della relativa ma più difficile domanda di chiusura sotto operatori binari (o di più alto livello)?

Answer 1

Come su qualcosa di simile che utilizza le strutture dati Trie Hash Array Mappate in unordered-containers. Per i contenitori non ordinati member e insert sono O (min (n, W)) dove W è la lunghezza dell'hash.

module Closed where 

import Data.HashSet (HashSet) 
import Data.Hashable 
import qualified Data.HashSet as Set 

data Closed a = Closed { seen :: HashSet a, iter :: a -> a } 

insert :: (Hashable a, Eq a) => a -> Closed a -> Closed a 
insert a c@(Closed set iter) 
    | Set.member a set = c 
    | otherwise  = insert (iter a) $ Closed (Set.insert a set) iter 

empty :: (a -> a) -> Closed a 
empty = Closed Set.empty 

close :: (Hashable a, Eq a) => (a -> a) -> [a] -> Closed a 
close iter = foldr insert (empty iter) 

Ecco una variante di quanto precede che genera la soluzione calare più pigramente, in modo ampiezza.

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 

E per controllare

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

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