Safe Haskell	None
Language	Haskell2010

Control.Effect.NonDet

Synopsis

data NonDet (m :: * -> *) k
- = Empty
- | Choose (Bool -> k)
class Applicative f => Alternative (f :: * -> *) where
runNonDet :: (Alternative f, Monad f, Traversable f, Carrier sig m, Effect sig, Applicative m) => Eff (AltC f m) a -> m (f a)
newtype AltC f m a = AltC {
- runAltC :: m (f a)
}
runNonDetOnce :: (Alternative f, Monad f, Traversable f, Carrier sig m, Effect sig, Monad m) => Eff (OnceC f m) a -> m (f a)
newtype OnceC f m a = OnceC {
- runOnceC :: Eff (CullC (Eff (AltC f m))) a
}
data Branch m e a
- = None e
- | Pure a
- | Alt (m a) (m a)
branch :: (e -> a) -> (b -> a) -> (m b -> m b -> a) -> Branch m e b -> a
runBranch :: Alternative m => (e -> m a) -> Branch m e a -> m a

Documentation

data NonDet (m :: * -> *) k Source #

Constructors

Empty
Choose (Bool -> k)

Instances

Effect NonDet Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods handle :: Functor f => f () -> (forall x. f (m x) -> n (f x)) -> NonDet m (m a) -> NonDet n (n (f a)) Source #
HFunctor NonDet Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods fmap' :: (a -> b) -> NonDet m a -> NonDet m b Source # hmap :: (forall x. m x -> n x) -> NonDet m a -> NonDet n a Source #
Functor (NonDet m) Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods fmap :: (a -> b) -> NonDet m a -> NonDet m b # (<$) :: a -> NonDet m b -> NonDet m a #
(Alternative m, Carrier sig m, Effect sig, Monad m) => Carrier (Cull :+: (NonDet :+: sig)) (CullC m) Source #
Instance details Defined in Control.Effect.Cull Methods ret :: a -> CullC m a Source # eff :: (Cull :+: (NonDet :+: sig)) (CullC m) (CullC m a) -> CullC m a Source #
(Alternative m, Carrier sig m, Effect sig, Monad m) => Carrier (Cut :+: (NonDet :+: sig)) (CutC m) Source #
Instance details Defined in Control.Effect.Cut Methods ret :: a -> CutC m a Source # eff :: (Cut :+: (NonDet :+: sig)) (CutC m) (CutC m a) -> CutC m a Source #
(Alternative f, Carrier sig m, Effect sig, Traversable f, Monad f, Monad m) => Carrier (NonDet :+: sig) (OnceC f m) Source #
Instance details Defined in Control.Effect.NonDet Methods ret :: a -> OnceC f m a Source # eff :: (NonDet :+: sig) (OnceC f m) (OnceC f m a) -> OnceC f m a Source #
(Alternative f, Monad f, Traversable f, Carrier sig m, Effect sig, Applicative m) => Carrier (NonDet :+: sig) (AltC f m) Source #
Instance details Defined in Control.Effect.NonDet Methods ret :: a -> AltC f m a Source # eff :: (NonDet :+: sig) (AltC f m) (AltC f m a) -> AltC f m a Source #

class Applicative f => Alternative (f :: * -> *) where #

A monoid on applicative functors.

If defined, some and many should be the least solutions of the equations:

```
some v = (:) <$> v <*> many v
```
```
many v = some v <|> pure []
```

Minimal complete definition

empty, (<|>)

Methods

empty :: f a #

The identity of <|>

(<|>) :: f a -> f a -> f a infixl 3 #

An associative binary operation

some :: f a -> f [a] #

One or more.

many :: f a -> f [a] #

Zero or more.

Instances

Alternative []	Since: base-2.1
Instance details Defined in GHC.Base Methods empty :: [a] # (<\|>) :: [a] -> [a] -> [a] # some :: [a] -> [[a]] # many :: [a] -> [[a]] #
Alternative Maybe	Since: base-2.1
Instance details Defined in GHC.Base Methods empty :: Maybe a # (<\|>) :: Maybe a -> Maybe a -> Maybe a # some :: Maybe a -> Maybe [a] # many :: Maybe a -> Maybe [a] #
Alternative IO	Since: base-4.9.0.0
Instance details Defined in GHC.Base Methods empty :: IO a # (<\|>) :: IO a -> IO a -> IO a # some :: IO a -> IO [a] # many :: IO a -> IO [a] #
Alternative Option	Since: base-4.9.0.0
Instance details Defined in Data.Semigroup Methods empty :: Option a # (<\|>) :: Option a -> Option a -> Option a # some :: Option a -> Option [a] # many :: Option a -> Option [a] #
Alternative ZipList	Since: base-4.11.0.0
Instance details Defined in Control.Applicative Methods empty :: ZipList a # (<\|>) :: ZipList a -> ZipList a -> ZipList a # some :: ZipList a -> ZipList [a] # many :: ZipList a -> ZipList [a] #
Alternative ReadP	Since: base-4.6.0.0
Instance details Defined in Text.ParserCombinators.ReadP Methods empty :: ReadP a # (<\|>) :: ReadP a -> ReadP a -> ReadP a # some :: ReadP a -> ReadP [a] # many :: ReadP a -> ReadP [a] #
Alternative P	Since: base-4.5.0.0
Instance details Defined in Text.ParserCombinators.ReadP Methods empty :: P a # (<\|>) :: P a -> P a -> P a # some :: P a -> P [a] # many :: P a -> P [a] #
Alternative (U1 :: * -> *)	Since: base-4.9.0.0
Instance details Defined in GHC.Generics Methods empty :: U1 a # (<\|>) :: U1 a -> U1 a -> U1 a # some :: U1 a -> U1 [a] # many :: U1 a -> U1 [a] #
MonadPlus m => Alternative (WrappedMonad m)	Since: base-2.1
Instance details Defined in Control.Applicative Methods empty :: WrappedMonad m a # (<\|>) :: WrappedMonad m a -> WrappedMonad m a -> WrappedMonad m a # some :: WrappedMonad m a -> WrappedMonad m [a] # many :: WrappedMonad m a -> WrappedMonad m [a] #
ArrowPlus a => Alternative (ArrowMonad a)	Since: base-4.6.0.0
Instance details Defined in Control.Arrow Methods empty :: ArrowMonad a a0 # (<\|>) :: ArrowMonad a a0 -> ArrowMonad a a0 -> ArrowMonad a a0 # some :: ArrowMonad a a0 -> ArrowMonad a [a0] # many :: ArrowMonad a a0 -> ArrowMonad a [a0] #
Alternative (Proxy :: * -> *)	Since: base-4.9.0.0
Instance details Defined in Data.Proxy Methods empty :: Proxy a # (<\|>) :: Proxy a -> Proxy a -> Proxy a # some :: Proxy a -> Proxy [a] # many :: Proxy a -> Proxy [a] #
(Member NonDet sig, Carrier sig carrier) => Alternative (Eff carrier) #	Run computations nondeterministically. run (runNonDet empty) == [] run (runNonDet empty) == Nothing run (runNonDet (pure a <\|> pure b)) == [a, b] run (runNonDet (pure a <\|> pure b)) == Just a Associativity: run (runNonDet ((pure a <\|> pure b) <\|> pure c)) == (run (runNonDet (pure a <\|> (pure b <\|> pure c))) :: [Integer]) run (runNonDet ((pure a <\|> pure b) <\|> pure c)) == (run (runNonDet (pure a <\|> (pure b <\|> pure c))) :: Maybe Integer) Left-identity: run (runNonDet (empty <\|> pure b)) == (run (runNonDet (pure b)) :: [Integer]) run (runNonDet (empty <\|> pure b)) == (run (runNonDet (pure b)) :: Maybe Integer) Right-identity: run (runNonDet (pure a <\|> empty)) == (run (runNonDet (pure a)) :: [Integer]) run (runNonDet (pure a <\|> empty)) == (run (runNonDet (pure a)) :: Maybe Integer)
Instance details Defined in Control.Effect.Internal Methods empty :: Eff carrier a # (<\|>) :: Eff carrier a -> Eff carrier a -> Eff carrier a # some :: Eff carrier a -> Eff carrier [a] # many :: Eff carrier a -> Eff carrier [a] #
Alternative f => Alternative (Rec1 f)	Since: base-4.9.0.0
Instance details Defined in GHC.Generics Methods empty :: Rec1 f a # (<\|>) :: Rec1 f a -> Rec1 f a -> Rec1 f a # some :: Rec1 f a -> Rec1 f [a] # many :: Rec1 f a -> Rec1 f [a] #
(ArrowZero a, ArrowPlus a) => Alternative (WrappedArrow a b)	Since: base-2.1
Instance details Defined in Control.Applicative Methods empty :: WrappedArrow a b a0 # (<\|>) :: WrappedArrow a b a0 -> WrappedArrow a b a0 -> WrappedArrow a b a0 # some :: WrappedArrow a b a0 -> WrappedArrow a b [a0] # many :: WrappedArrow a b a0 -> WrappedArrow a b [a0] #
Alternative f => Alternative (Alt f)
Instance details Defined in Data.Semigroup.Internal Methods empty :: Alt f a # (<\|>) :: Alt f a -> Alt f a -> Alt f a # some :: Alt f a -> Alt f [a] # many :: Alt f a -> Alt f [a] #
(Functor m, Monad m, Error e) => Alternative (ErrorT e m)
Instance details Defined in Control.Monad.Trans.Error Methods empty :: ErrorT e m a # (<\|>) :: ErrorT e m a -> ErrorT e m a -> ErrorT e m a # some :: ErrorT e m a -> ErrorT e m [a] # many :: ErrorT e m a -> ErrorT e m [a] #
(Alternative f, Alternative g) => Alternative (f :*: g)	Since: base-4.9.0.0
Instance details Defined in GHC.Generics Methods empty :: (f :: g) a # (<\|>) :: (f :: g) a -> (f :: g) a -> (f :: g) a # some :: (f :: g) a -> (f :: g) [a] # many :: (f :: g) a -> (f :: g) [a] #
(Alternative f, Alternative g) => Alternative (Product f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Product Methods empty :: Product f g a # (<\|>) :: Product f g a -> Product f g a -> Product f g a # some :: Product f g a -> Product f g [a] # many :: Product f g a -> Product f g [a] #
Alternative f => Alternative (M1 i c f)	Since: base-4.9.0.0
Instance details Defined in GHC.Generics Methods empty :: M1 i c f a # (<\|>) :: M1 i c f a -> M1 i c f a -> M1 i c f a # some :: M1 i c f a -> M1 i c f [a] # many :: M1 i c f a -> M1 i c f [a] #
(Alternative f, Applicative g) => Alternative (f :.: g)	Since: base-4.9.0.0
Instance details Defined in GHC.Generics Methods empty :: (f :.: g) a # (<\|>) :: (f :.: g) a -> (f :.: g) a -> (f :.: g) a # some :: (f :.: g) a -> (f :.: g) [a] # many :: (f :.: g) a -> (f :.: g) [a] #
(Alternative f, Applicative g) => Alternative (Compose f g)	Since: base-4.9.0.0
Instance details Defined in Data.Functor.Compose Methods empty :: Compose f g a # (<\|>) :: Compose f g a -> Compose f g a -> Compose f g a # some :: Compose f g a -> Compose f g [a] # many :: Compose f g a -> Compose f g [a] #

runNonDet :: (Alternative f, Monad f, Traversable f, Carrier sig m, Effect sig, Applicative m) => Eff (AltC f m) a -> m (f a) Source #

Run a NonDet effect, collecting all branches’ results into an Alternative functor.

Using '[]' as the Alternative functor will produce all results, while Maybe will return only the first. However, unlike runNonDetOnce, this will still enumerate the entire search space before returning, meaning that it will diverge for infinite search spaces, even when using Maybe.

run (runNonDet (pure a)) == [a]

run (runNonDet (pure a)) == Just a

newtype AltC f m a Source #

Constructors

AltC
Fields runAltC :: m (f a)

Instances

(Alternative f, Monad f, Traversable f, Carrier sig m, Effect sig, Applicative m) => Carrier (NonDet :+: sig) (AltC f m) Source #
Instance details Defined in Control.Effect.NonDet Methods ret :: a -> AltC f m a Source # eff :: (NonDet :+: sig) (AltC f m) (AltC f m a) -> AltC f m a Source #

runNonDetOnce :: (Alternative f, Monad f, Traversable f, Carrier sig m, Effect sig, Monad m) => Eff (OnceC f m) a -> m (f a) Source #

Run a NonDet effect, returning the first successful result in an Alternative functor.

Unlike runNonDet, this will terminate immediately upon finding a solution.

run (runNonDetOnce (asum (map pure (repeat a)))) == [a]

run (runNonDetOnce (asum (map pure (repeat a)))) == Just a

newtype OnceC f m a Source #

Constructors

OnceC
Fields runOnceC :: Eff (CullC (Eff (AltC f m))) a

Instances

(Alternative f, Carrier sig m, Effect sig, Traversable f, Monad f, Monad m) => Carrier (NonDet :+: sig) (OnceC f m) Source #
Instance details Defined in Control.Effect.NonDet Methods ret :: a -> OnceC f m a Source # eff :: (NonDet :+: sig) (OnceC f m) (OnceC f m a) -> OnceC f m a Source #

data Branch m e a Source #

The result of a nondeterministic branch of a computation.

Branch can be used to define NonDet carriers which control nondeterminism in some specific way, e.g. pruning branches according to some specific heuristic.

Constructors

None e
Pure a
Alt (m a) (m a)

Instances

Functor m => Functor (Branch m e) Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods fmap :: (a -> b) -> Branch m e a -> Branch m e b # (<$) :: a -> Branch m e b -> Branch m e a #
Foldable m => Foldable (Branch m e) Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods fold :: Monoid m0 => Branch m e m0 -> m0 # foldMap :: Monoid m0 => (a -> m0) -> Branch m e a -> m0 # foldr :: (a -> b -> b) -> b -> Branch m e a -> b # foldr' :: (a -> b -> b) -> b -> Branch m e a -> b # foldl :: (b -> a -> b) -> b -> Branch m e a -> b # foldl' :: (b -> a -> b) -> b -> Branch m e a -> b # foldr1 :: (a -> a -> a) -> Branch m e a -> a # foldl1 :: (a -> a -> a) -> Branch m e a -> a # toList :: Branch m e a -> [a] # null :: Branch m e a -> Bool # length :: Branch m e a -> Int # elem :: Eq a => a -> Branch m e a -> Bool # maximum :: Ord a => Branch m e a -> a # minimum :: Ord a => Branch m e a -> a # sum :: Num a => Branch m e a -> a # product :: Num a => Branch m e a -> a #
Traversable m => Traversable (Branch m e) Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods traverse :: Applicative f => (a -> f b) -> Branch m e a -> f (Branch m e b) # sequenceA :: Applicative f => Branch m e (f a) -> f (Branch m e a) # mapM :: Monad m0 => (a -> m0 b) -> Branch m e a -> m0 (Branch m e b) # sequence :: Monad m0 => Branch m e (m0 a) -> m0 (Branch m e a) #
(Eq e, Eq a, Eq (m a)) => Eq (Branch m e a) Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods (==) :: Branch m e a -> Branch m e a -> Bool # (/=) :: Branch m e a -> Branch m e a -> Bool #
(Ord e, Ord a, Ord (m a)) => Ord (Branch m e a) Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods compare :: Branch m e a -> Branch m e a -> Ordering # (<) :: Branch m e a -> Branch m e a -> Bool # (<=) :: Branch m e a -> Branch m e a -> Bool # (>) :: Branch m e a -> Branch m e a -> Bool # (>=) :: Branch m e a -> Branch m e a -> Bool # max :: Branch m e a -> Branch m e a -> Branch m e a # min :: Branch m e a -> Branch m e a -> Branch m e a #
(Show e, Show a, Show (m a)) => Show (Branch m e a) Source #
Instance details Defined in Control.Effect.NonDet.Internal Methods showsPrec :: Int -> Branch m e a -> ShowS # show :: Branch m e a -> String # showList :: [Branch m e a] -> ShowS #

branch :: (e -> a) -> (b -> a) -> (m b -> m b -> a) -> Branch m e b -> a Source #

Case analysis for Branch, taking a value to use for Cut, a value to use for None, and a function to apply to the contents of Pure.

branch None Pure Alt a == (a :: Branch e [] a)

branch (applyFun f) (applyFun g) (applyFun2 h) (None a :: Branch [] a) == applyFun f a

branch (applyFun f) (applyFun g) (applyFun2 h) (Pure a :: Branch [] a) == applyFun g a

branch (applyFun f) (applyFun g) (applyFun2 h) (Alt a b :: Branch [] a) == applyFun2 h a b

runBranch :: Alternative m => (e -> m a) -> Branch m e a -> m a Source #

Interpret a Branch into an underlying Alternative context.