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	TypeSynonymInstances FlexibleInstances ConstrainedClassMethods MultiParamTypeClasses FunctionalDependencies KindSignatures

ToySolver.Combinatorial.HittingSet.InterestingSets

Contents

Problem definition
Options for maximal interesting sets enumeration
Datatype for monotone CNF/DNF dualization

Description

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
- = UninterestingSet IntSet
- | InterestingSet IntSet
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 :: Type -> Type) = 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
- = Implicate IntSet
- | Implicant IntSet

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.

Minimal complete definition

universe, (isInteresting | isInteresting')

Methods

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

Instances details

Monad m => IsProblem (SimpleProblem m) m Source #

Instance details

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

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 #

Constructors

UninterestingSet IntSet
InterestingSet IntSet

Instances

Instances details

Read InterestingOrUninterestingSet Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods readsPrec :: Int -> ReadS InterestingOrUninterestingSet # readList :: ReadS [InterestingOrUninterestingSet] # readPrec :: ReadPrec InterestingOrUninterestingSet # readListPrec :: ReadPrec [InterestingOrUninterestingSet] #
Show InterestingOrUninterestingSet Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods showsPrec :: Int -> InterestingOrUninterestingSet -> ShowS # show :: InterestingOrUninterestingSet -> String # showList :: [InterestingOrUninterestingSet] -> ShowS #
Eq InterestingOrUninterestingSet Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods (==) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool # (/=) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool #
Ord InterestingOrUninterestingSet Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods compare :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Ordering # (<) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool # (<=) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool # (>) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool # (>=) :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> Bool # max :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> InterestingOrUninterestingSet # min :: InterestingOrUninterestingSet -> InterestingOrUninterestingSet -> InterestingOrUninterestingSet #

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 :: Type -> Type) Source #

Constructors

SimpleProblem IntSet (IntSet -> Bool)

Instances

Instances details

Monad m => IsProblem (SimpleProblem m) m Source #

Instance details

Defined in ToySolver.Combinatorial.HittingSet.InterestingSets

Methods

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

data Options m Source #

Constructors

Options
Fields optMinimalHittingSets :: Set IntSet -> m (Set IntSet) optMaximalInterestingSets :: Set IntSet optMinimalUninterestingSets :: Set IntSet optOnMaximalInterestingSetFound :: IntSet -> m () optOnMinimalUninterestingSetFound :: IntSet -> m ()

Instances

Instances details

Monad m => Default (Options m) Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods def :: Options m #

Datatype for monotone CNF/DNF dualization

data ImplicateOrImplicant Source #

Constructors

Implicate IntSet
Implicant IntSet

Instances

Instances details

Read ImplicateOrImplicant Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods readsPrec :: Int -> ReadS ImplicateOrImplicant # readList :: ReadS [ImplicateOrImplicant] # readPrec :: ReadPrec ImplicateOrImplicant # readListPrec :: ReadPrec [ImplicateOrImplicant] #
Show ImplicateOrImplicant Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods showsPrec :: Int -> ImplicateOrImplicant -> ShowS # show :: ImplicateOrImplicant -> String # showList :: [ImplicateOrImplicant] -> ShowS #
Eq ImplicateOrImplicant Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods (==) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool # (/=) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool #
Ord ImplicateOrImplicant Source #
Instance details Defined in ToySolver.Combinatorial.HittingSet.InterestingSets Methods compare :: ImplicateOrImplicant -> ImplicateOrImplicant -> Ordering # (<) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool # (<=) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool # (>) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool # (>=) :: ImplicateOrImplicant -> ImplicateOrImplicant -> Bool # max :: ImplicateOrImplicant -> ImplicateOrImplicant -> ImplicateOrImplicant # min :: ImplicateOrImplicant -> ImplicateOrImplicant -> ImplicateOrImplicant #