Copyright | (c) Masahiro Sakai 2016 |
---|---|
License | BSD-style |
Maintainer | masahiro.sakai@gmail.com |
Stability | provisional |
Portability | non-portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
Extensions |
|
- D. Gunopulos, H. Mannila, R. Khardon, and H. Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), in Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, ser. PODS '97. 1997, pp. 209-216. http://almaden.ibm.com/cs/projects/iis/hdb/Publications/papers/pods97_trans.pdf
Synopsis
- class Monad m => IsProblem prob m | prob -> m where
- universe :: prob -> IntSet
- isInteresting :: prob -> IntSet -> m Bool
- isInteresting' :: prob -> IntSet -> m InterestingOrUninterestingSet
- grow :: prob -> IntSet -> m IntSet
- shrink :: prob -> IntSet -> m IntSet
- maximalInterestingSet :: prob -> IntSet -> m (Maybe IntSet)
- minimalUninterestingSet :: prob -> IntSet -> m (Maybe IntSet)
- minimalUninterestingSetOrMaximalInterestingSet :: prob -> IntSet -> m InterestingOrUninterestingSet
- data InterestingOrUninterestingSet
- defaultGrow :: IsProblem prob m => prob -> IntSet -> m IntSet
- defaultShrink :: IsProblem prob m => prob -> IntSet -> m IntSet
- defaultMaximalInterestingSet :: IsProblem prob m => prob -> IntSet -> m (Maybe IntSet)
- defaultMinimalUninterestingSet :: IsProblem prob m => prob -> IntSet -> m (Maybe IntSet)
- defaultMinimalUninterestingSetOrMaximalInterestingSet :: IsProblem prob m => prob -> IntSet -> m InterestingOrUninterestingSet
- data SimpleProblem (m :: * -> *) = SimpleProblem IntSet (IntSet -> Bool)
- data Options m = Options {
- optMinimalHittingSets :: Set IntSet -> m (Set IntSet)
- optMaximalInterestingSets :: Set IntSet
- optMinimalUninterestingSets :: Set IntSet
- optOnMaximalInterestingSetFound :: IntSet -> m ()
- optOnMinimalUninterestingSetFound :: IntSet -> m ()
- data ImplicateOrImplicant
Problem definition
class Monad m => IsProblem prob m | prob -> m where Source #
A problem is essentially a pair of an IntSet
(universe
) and
a monotone pure function IntSet -> Bool
(isInteresting
), but
we generalize a bit for potentialial optimization opportunity.
For simple cases you can just use SimpleProblem
instance.
universe :: prob -> IntSet Source #
isInteresting :: prob -> IntSet -> m Bool Source #
Interesting sets are lower closed subsets of universe
, i.e. if xs
is
interesting then ys
⊆ xs
is also interesting.
isInteresting' :: prob -> IntSet -> m InterestingOrUninterestingSet Source #
If xs
is interesting it returns InterestingSet ys
where ys
is an interesting superset of xs
.
If xs
is uninteresting it returns UninterestingSet ys
where ys
is an uninteresting subset of xs
.
grow :: prob -> IntSet -> m IntSet Source #
grow xs
computes maximal interesting set ys
that is a superset of xs
.
shrink :: prob -> IntSet -> m IntSet Source #
shrink xs
computes minimal uninteresting set ys
that is a subset of xs
.
maximalInterestingSet :: prob -> IntSet -> m (Maybe IntSet) Source #
If xs
is an interesting set maximalInterestingSet prob xs
returns Just ys
such that ys
is a maximal interesting superset of xs
, otherwise it returns Nothing
.
minimalUninterestingSet :: prob -> IntSet -> m (Maybe IntSet) Source #
If xs
is an uninteresting set minimalUninterestingSet prob xs
returns Just ys
such that ys
is a minimal uninteresting subset of xs
, otherwise it returns Nothing
.
minimalUninterestingSetOrMaximalInterestingSet :: prob -> IntSet -> m InterestingOrUninterestingSet Source #
If xs
is an uninteresting set minimalUninterestingSetOrMaximalInterestingSet prob xs
returns Left ys
such that ys
is a minimal uninteresting subset of xs
.
If xs
is an interesting set minimalUninterestingSetOrMaximalInterestingSet prob xs
returns Right ys
such that ys
is a maximal interesting superset of xs
Instances
Monad m => IsProblem (SimpleProblem m) m Source # | |
Defined in ToySolver.Combinatorial.HittingSet.InterestingSets universe :: SimpleProblem m -> IntSet Source # isInteresting :: SimpleProblem m -> IntSet -> m Bool Source # isInteresting' :: SimpleProblem m -> IntSet -> m InterestingOrUninterestingSet Source # grow :: SimpleProblem m -> IntSet -> m IntSet Source # shrink :: SimpleProblem m -> IntSet -> m IntSet Source # maximalInterestingSet :: SimpleProblem m -> IntSet -> m (Maybe IntSet) Source # minimalUninterestingSet :: SimpleProblem m -> IntSet -> m (Maybe IntSet) Source # minimalUninterestingSetOrMaximalInterestingSet :: SimpleProblem m -> IntSet -> m InterestingOrUninterestingSet Source # |
data InterestingOrUninterestingSet Source #
Instances
defaultGrow :: IsProblem prob m => prob -> IntSet -> m IntSet Source #
Default implementation of grow
using isInteresting'
.
defaultShrink :: IsProblem prob m => prob -> IntSet -> m IntSet Source #
Default implementation of shrink
using isInteresting'
.
defaultMaximalInterestingSet :: IsProblem prob m => prob -> IntSet -> m (Maybe IntSet) Source #
Default implementation of maximalUninterestingSet
using isInteresting'
and grow
.
defaultMinimalUninterestingSet :: IsProblem prob m => prob -> IntSet -> m (Maybe IntSet) Source #
Default implementation of minimalUninterestingSet
using isInteresting'
and shrink
.
defaultMinimalUninterestingSetOrMaximalInterestingSet :: IsProblem prob m => prob -> IntSet -> m InterestingOrUninterestingSet Source #
Default implementation of minimalUninterestingSetOrMaximalInterestingSet
using isInteresting'
, shrink
grow
.
data SimpleProblem (m :: * -> *) Source #
SimpleProblem IntSet (IntSet -> Bool) |
Instances
Monad m => IsProblem (SimpleProblem m) m Source # | |
Defined in ToySolver.Combinatorial.HittingSet.InterestingSets universe :: SimpleProblem m -> IntSet Source # isInteresting :: SimpleProblem m -> IntSet -> m Bool Source # isInteresting' :: SimpleProblem m -> IntSet -> m InterestingOrUninterestingSet Source # grow :: SimpleProblem m -> IntSet -> m IntSet Source # shrink :: SimpleProblem m -> IntSet -> m IntSet Source # maximalInterestingSet :: SimpleProblem m -> IntSet -> m (Maybe IntSet) Source # minimalUninterestingSet :: SimpleProblem m -> IntSet -> m (Maybe IntSet) Source # minimalUninterestingSetOrMaximalInterestingSet :: SimpleProblem m -> IntSet -> m InterestingOrUninterestingSet Source # |
Options for maximal interesting sets enumeration
Options | |
|
Datatype for monotone CNF/DNF dualization
data ImplicateOrImplicant Source #