Portability | non-portable |
---|---|

Stability | experimental |

Maintainer | me@jspha.com |

Safe Haskell | None |

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.

- data Closed a
- seenBy :: Int -> Closed a -> HashSet a
- seen :: Closed a -> HashSet a
- memberWithin' :: (Hashable a, Eq a) => Int -> a -> Closed a -> (Bool, Closed a)
- memberWithin :: (Hashable a, Eq a) => Int -> a -> Closed a -> Bool
- member' :: (Hashable a, Eq a) => a -> Closed a -> (Bool, Closed a)
- member :: (Hashable a, Eq a) => a -> Closed a -> Bool
- close :: (Hashable a, Eq a, Foldable t) => (a -> a) -> t a -> Closed a

# Closed sets

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.

## Operations

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