Data.Recursive.Set

The type RS.RSet a is like Set a, but allows recursive definitions:

>>> :{
  let s1 = RS.insert 23 s2
      s2 = RS.insert 42 s1
  in RS.get s1
 :}
fromList [23,42]

Documentation

data RSet a

Like Set, but admits recursive definitions.

get :: RSet a -> Set a

Extracts the value of a 'RSet a'

mk :: Set a -> RSet a

RB.get (RB.mk s) === s

empty :: RSet a

RS.get RS.empty === S.empty

singleton :: a -> RSet a

RS.get (RS.singleton x) === S.singleton x

insert :: Ord a => a -> RSet a -> RSet a

RS.get (RS.insert n r1) === S.insert n (RS.get r1)

delete :: Ord a => a -> RSet a -> RSet a

RS.get (RS.delete n r1) === S.delete n (RS.get r1)

filter :: Ord a => (a -> Bool) -> RSet a -> RSet a

\(Fun _ p) -> RS.get (RS.filter p r1) === S.filter p (RS.get r1)

union :: Ord a => RSet a -> RSet a -> RSet a

RS.get (RS.union r1 r2) === S.union (RS.get r1) (RS.get r2)

unions :: Ord a => [RSet a] -> RSet a

RS.get (RS.unions rs) === S.unions (map RS.get rs)

intersection :: Ord a => RSet a -> RSet a -> RSet a

RS.get (RS.intersection r1 r2) === S.intersection (RS.get r1) (RS.get r2)

member :: Ord a => a -> RSet a -> RBool

RB.get (RS.member n r1) === S.member n (RS.get r1)

notMember :: Ord a => a -> RSet a -> RDualBool

RDB.get (RS.notMember n r1) === S.notMember n (RS.get r1)

null :: RSet a -> RDualBool

RDB.get (RS.null s) === S.null (RS.get s)

disjoint :: Ord a => RSet a -> RSet a -> RDualBool

RDB.get (RS.disjoint r1 r2) === S.disjoint (RS.get r1) (RS.get r2)

when :: RBool -> RSet a -> RSet a

An kind of if-then-else statement. Because of monotonicity requirements, this should be sufficient.

RS.get (RS.when b r) === (if RB.get b then RS.get r else S.empty)

id :: RSet a -> RSet a

The identity function. This is useful when tying the knot, to avoid a loop that bottoms out:

let x = x in RS.get x

will not work, but

>>> let x = RS.id x in RS.get x
fromList []

does.

| prop> RS.get (RS.id s) === RS.get s