Portability	non-portable
Stability	experimental
Maintainer	me@jspha.com
Safe Haskell	None

Algebra.Closure.Set.BreadthFirst

Contents

Closed sets
- Operations
- Creation

Description

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.

Synopsis

Closed sets

data Closed a Source

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 aSource

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

seen :: Closed a -> HashSet aSource

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)Source

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 Source

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)Source

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 Source

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 aSource

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