Safe Haskell | None |
---|---|

Language | Haskell2010 |

This module creates an `IntSet`

type with a phantom type variable, allowing
it to conform to `Functor`

, `Foldable`

, etc. Other than that, it's a
duplication of the Data.IntSet module.

- data IntSet a
- (\\) :: IntSet a -> IntSet a -> IntSet a
- lookupLT :: a -> IntSet a -> Maybe a
- lookupLE :: a -> IntSet a -> Maybe a
- lookupGT :: a -> IntSet a -> Maybe a
- lookupGE :: a -> IntSet a -> Maybe a
- isSubsetOf :: IntSet a -> IntSet a -> Bool
- isProperSubsetOf :: IntSet a -> IntSet a -> Bool
- insert :: a -> IntSet a -> IntSet a
- delete :: a -> IntSet a -> IntSet a
- difference :: IntSet a -> IntSet a -> IntSet a
- intersection :: IntSet a -> IntSet a -> IntSet a
- filter :: (a -> Bool) -> IntSet a -> IntSet a
- partition :: (a -> Bool) -> IntSet a -> (IntSet a, IntSet a)
- split :: a -> IntSet a -> (IntSet a, IntSet a)
- splitMember :: a -> IntSet a -> (IntSet a, Bool, IntSet a)
- splitRoot :: IntSet a -> [IntSet a]
- maxView :: IntSet a -> Maybe (a, IntSet a)
- minView :: IntSet a -> Maybe (a, IntSet a)
- deleteMin :: IntSet a -> IntSet a
- deleteMax :: IntSet a -> IntSet a
- toAscList :: IntSet a -> [a]
- toDescList :: IntSet a -> [a]
- fromAscList :: [Int] -> IntSet Int
- fromDistinctAscList :: [Int] -> IntSet Int

# IntSet type

This type is a wrapper around `IntSet`

, with a phantom type
variable which must always be `Int`

. This allows it to conform to `Functor`

,
`Foldable`

, `Applicative`

, `Monad`

, etc.

Foldable IntSet Source # | |

Eq1 IntSet Source # | |

Ord1 IntSet Source # | |

Show1 IntSet Source # | |

Alternative IntSet Source # | |

Monad IntSet Source # | |

Applicative IntSet Source # | |

Functor IntSet Source # | |

(~) * a Int => IsList (IntSet a) Source # | |

Eq a => Eq (IntSet a) Source # | |

(~) * a Int => Data (IntSet a) Source # | |

Ord a => Ord (IntSet a) Source # | |

(~) * a Int => Read (IntSet a) Source # | |

Show a => Show (IntSet a) Source # | |

Semigroup (IntSet a) Source # | |

(~) * a Int => Monoid (IntSet a) Source # | |

NFData (IntSet a) Source # | |

type Unconstrained IntSet Source # | |

type Suitable IntSet a Source # | |

type Item (IntSet a) Source # | |

# Operators

# Query

lookupLT :: a -> IntSet a -> Maybe a Source #

*O(log n)*. Find largest element smaller than the given one.

lookupLT 3 (fromList [3, 5]) == Nothing lookupLT 5 (fromList [3, 5]) == Just 3

lookupLE :: a -> IntSet a -> Maybe a Source #

*O(log n)*. Find largest element smaller or equal to the given one.

lookupLE 2 (fromList [3, 5]) == Nothing lookupLE 4 (fromList [3, 5]) == Just 3 lookupLE 5 (fromList [3, 5]) == Just 5

lookupGT :: a -> IntSet a -> Maybe a Source #

*O(log n)*. Find smallest element greater than the given one.

lookupGT 4 (fromList [3, 5]) == Just 5 lookupGT 5 (fromList [3, 5]) == Nothing

lookupGE :: a -> IntSet a -> Maybe a Source #

*O(log n)*. Find smallest element greater or equal to the given one.

lookupGE 3 (fromList [3, 5]) == Just 3 lookupGE 4 (fromList [3, 5]) == Just 5 lookupGE 6 (fromList [3, 5]) == Nothing

# Construction

insert :: a -> IntSet a -> IntSet a Source #

*O(min(n,W))*. Add a value to the set. There is no left- or right bias for
IntSets.

delete :: a -> IntSet a -> IntSet a Source #

*O(min(n,W))*. Delete a value in the set. Returns the
original set when the value was not present.

# Combine

# Filter

filter :: (a -> Bool) -> IntSet a -> IntSet a Source #

*O(n)*. Filter all elements that satisfy some predicate.

partition :: (a -> Bool) -> IntSet a -> (IntSet a, IntSet a) Source #

*O(n)*. partition the set according to some predicate.

split :: a -> IntSet a -> (IntSet a, IntSet a) Source #

*O(min(n,W))*. The expression (

) is a pair `split`

x set`(set1,set2)`

where `set1`

comprises the elements of `set`

less than `x`

and `set2`

comprises the elements of `set`

greater than `x`

.

split 3 (fromList [1..5]) == (fromList [1,2], fromList [4,5])

# Min/Max

maxView :: IntSet a -> Maybe (a, IntSet a) Source #

*O(min(n,W))*. Retrieves the maximal key of the set, and the set
stripped of that element, or `Nothing`

if passed an empty set.

minView :: IntSet a -> Maybe (a, IntSet a) Source #

*O(min(n,W))*. Retrieves the minimal key of the set, and the set
stripped of that element, or `Nothing`

if passed an empty set.

# Ordered List

toDescList :: IntSet a -> [a] Source #