Algebra.Closure.Set.BreadthFirst

Depth-first closed sets. For a particular endomorphism (p :: a -> a) a Closed set is a set where if some element x is in the set then so is p x. Unlike Algebra.Closure.Set.DepthFirst, this algorithm computes the closure in a depth-first manner and thus can be useful for computing infinite closures.

It's reasonable to think of a breadth-first Closed set as the process of generating a depth-first Closed set frozen in time. This retains information about the number of iterations required for stability and allows us to return answers that depend only upon partial information even if the closure itself is unbounded.

Closed sets

data Closed a

A closed set Closed a, given an endomorphism (p :: a -> a), is a set where if some element x is in the set then so is p x.

seenBy :: Int -> Closed a -> HashSet a

seenBy n converts a Closed set into its underlying set, approximated by n iterations.

seen :: Closed a -> HashSet a

Converts a Closed set into its underlying set. If the Closed set is unbounded then this operation is undefined (see seenBy). It's reasonable to think of this operation as

   let omega = succ omega in seenBy omega

Operations

memberWithin' :: (Hashable a, Eq a) => Int -> a -> Closed a -> (Bool, Closed a)

memberWithin' n a checks to see whether an element is within a Closed set after n improvements. The Closed set returned is a compressed, memoized Closed set which may be faster to query.

memberWithin :: (Hashable a, Eq a) => Int -> a -> Closed a -> Bool

memberWithin' n a checks to see whether an element is within a Closed set after n improvements.

member' :: (Hashable a, Eq a) => a -> Closed a -> (Bool, Closed a)

Determines whether a particular element is in the Closed set. If the element is in the set, this operation is always defined. If it is not and the set is unbounded, this operation is undefined (see memberWithin). It's reasonable to think of this operation as

let omega = succ omega in memberWithin omega The Closed set returned is a compressed, memoized Closed set which may be faster to query.

member :: (Hashable a, Eq a) => a -> Closed a -> Bool

Determines whether a particular element is in the Closed set. If the element is in the set, this operation is always defined. If it is not and the set is unbounded, this operation is undefined (see memberWithin). It's reasonable to think of this operation as

   let omega = succ omega in memberWithin omega

Creation

close :: (Hashable a, Eq a, Foldable t) => (a -> a) -> t a -> Closed a

Converts any Foldable container into the Closed set of its contents.