closure-0.1.0.0: Depth- and breadth-first set closures

Portability non-portable experimental me@jspha.com None

Contents

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 -> BoolSource

`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 -> BoolSource

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.