Safe Haskell	None
Language	Haskell2010

Control.Effect.NonDet

Synopsis

data NonDet :: Effect where
- Empty :: NonDet m a
- Choose :: NonDet m Bool
class Applicative f => Alternative (f :: Type -> Type) where
- empty :: f a
- (<|>) :: f a -> f a -> f a
- some :: f a -> f [a]
- many :: f a -> f [a]
runNonDetAll :: Alternative f => Eff (NonDet ': effs) a -> Eff effs (f a)

Documentation

data NonDet :: Effect where Source #

The NonDet effect provides so-called nondeterministic execution, which runs all branches of a computation and collects some or all of their results. Actual execution is not usually truly nondeterministic in the sense that it is somehow random; rather, NonDet models nondeterministic binary choice by executing both possibilities rather than choosing just one.

Constructors

Empty :: NonDet m a
Choose :: NonDet m Bool

class Applicative f => Alternative (f :: Type -> Type) 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

Instances details

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 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 SmallArray
Instance details Defined in Data.Primitive.SmallArray Methods empty :: SmallArray a # (<\|>) :: SmallArray a -> SmallArray a -> SmallArray a # some :: SmallArray a -> SmallArray [a] # many :: SmallArray a -> SmallArray [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] #
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] #
(Functor m, Monad m) => Alternative (MaybeT m)
Instance details Defined in Control.Monad.Trans.Maybe Methods empty :: MaybeT m a # (<\|>) :: MaybeT m a -> MaybeT m a -> MaybeT m a # some :: MaybeT m a -> MaybeT m [a] # many :: MaybeT m a -> MaybeT m [a] #
Applicative m => Alternative (ListT m)
Instance details Defined in Control.Monad.Trans.List Methods empty :: ListT m a # (<\|>) :: ListT m a -> ListT m a -> ListT m a # some :: ListT m a -> ListT m [a] # many :: ListT m a -> ListT m [a] #
NonDet :< effs => Alternative (Eff effs) Source #
Instance details Defined in Control.Effect.Internal Methods empty :: Eff effs a # (<\|>) :: Eff effs a -> Eff effs a -> Eff effs a # some :: Eff effs a -> Eff effs [a] # many :: Eff effs a -> Eff effs [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] #
(Monoid w, Alternative m) => Alternative (WriterT w m)
Instance details Defined in Control.Monad.Trans.Writer.Strict Methods empty :: WriterT w m a # (<\|>) :: WriterT w m a -> WriterT w m a -> WriterT w m a # some :: WriterT w m a -> WriterT w m [a] # many :: WriterT w m a -> WriterT w m [a] #
(Monoid w, Functor m, MonadPlus m) => Alternative (AccumT w m)
Instance details Defined in Control.Monad.Trans.Accum Methods empty :: AccumT w m a # (<\|>) :: AccumT w m a -> AccumT w m a -> AccumT w m a # some :: AccumT w m a -> AccumT w m [a] # many :: AccumT w m a -> AccumT w m [a] #
(Monoid w, Alternative m) => Alternative (WriterT w m)
Instance details Defined in Control.Monad.Trans.Writer.Lazy Methods empty :: WriterT w m a # (<\|>) :: WriterT w m a -> WriterT w m a -> WriterT w m a # some :: WriterT w m a -> WriterT w m [a] # many :: WriterT w m a -> WriterT w m [a] #
(Functor m, MonadPlus m) => Alternative (WriterT w m)
Instance details Defined in Control.Monad.Trans.Writer.CPS Methods empty :: WriterT w m a # (<\|>) :: WriterT w m a -> WriterT w m a -> WriterT w m a # some :: WriterT w m a -> WriterT w m [a] # many :: WriterT w m a -> WriterT w m [a] #
(Functor m, MonadPlus m) => Alternative (StateT s m)
Instance details Defined in Control.Monad.Trans.State.Strict Methods empty :: StateT s m a # (<\|>) :: StateT s m a -> StateT s m a -> StateT s m a # some :: StateT s m a -> StateT s m [a] # many :: StateT s m a -> StateT s m [a] #
(Functor m, MonadPlus m) => Alternative (StateT s m)
Instance details Defined in Control.Monad.Trans.State.Lazy Methods empty :: StateT s m a # (<\|>) :: StateT s m a -> StateT s m a -> StateT s m a # some :: StateT s m a -> StateT s m [a] # many :: StateT s m a -> StateT s m [a] #
(Functor m, MonadPlus m) => Alternative (SelectT r m)
Instance details Defined in Control.Monad.Trans.Select Methods empty :: SelectT r m a # (<\|>) :: SelectT r m a -> SelectT r m a -> SelectT r m a # some :: SelectT r m a -> SelectT r m [a] # many :: SelectT r m a -> SelectT r m [a] #
Alternative m => Alternative (ReaderT r m)
Instance details Defined in Control.Monad.Trans.Reader Methods empty :: ReaderT r m a # (<\|>) :: ReaderT r m a -> ReaderT r m a -> ReaderT r m a # some :: ReaderT r m a -> ReaderT r m [a] # many :: ReaderT r m a -> ReaderT r m [a] #
Alternative m => Alternative (IdentityT m)
Instance details Defined in Control.Monad.Trans.Identity Methods empty :: IdentityT m a # (<\|>) :: IdentityT m a -> IdentityT m a -> IdentityT m a # some :: IdentityT m a -> IdentityT m [a] # many :: IdentityT m a -> IdentityT m [a] #
(Functor m, Monad m, Monoid e) => Alternative (ExceptT e m)
Instance details Defined in Control.Monad.Trans.Except Methods empty :: ExceptT e m a # (<\|>) :: ExceptT e m a -> ExceptT e m a -> ExceptT e m a # some :: ExceptT e m a -> ExceptT e m [a] # many :: ExceptT e m a -> ExceptT e m [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] #
(Monoid w, Functor m, MonadPlus m) => Alternative (RWST r w s m)
Instance details Defined in Control.Monad.Trans.RWS.Strict Methods empty :: RWST r w s m a # (<\|>) :: RWST r w s m a -> RWST r w s m a -> RWST r w s m a # some :: RWST r w s m a -> RWST r w s m [a] # many :: RWST r w s m a -> RWST r w s m [a] #
(Monoid w, Functor m, MonadPlus m) => Alternative (RWST r w s m)
Instance details Defined in Control.Monad.Trans.RWS.Lazy Methods empty :: RWST r w s m a # (<\|>) :: RWST r w s m a -> RWST r w s m a -> RWST r w s m a # some :: RWST r w s m a -> RWST r w s m [a] # many :: RWST r w s m a -> RWST r w s m [a] #
(Functor m, MonadPlus m) => Alternative (RWST r w s m)
Instance details Defined in Control.Monad.Trans.RWS.CPS Methods empty :: RWST r w s m a # (<\|>) :: RWST r w s m a -> RWST r w s m a -> RWST r w s m a # some :: RWST r w s m a -> RWST r w s m [a] # many :: RWST r w s m a -> RWST r w s m [a] #

runNonDetAll :: Alternative f => Eff (NonDet ': effs) a -> Eff effs (f a) Source #

Handles a NonDet effect, collecting the results of all branches of the computation. The results are collected strictly, which means that all effects are evaluated (even if using an Alternative that ignores subsequent results, such as Maybe).

The result is also built using a left-associated sequence of <|> calls, which allows the result to be constructed in constant space if an appropriate Alternative instance is used, but can lead to very poor performance for types with inefficient append operations, such as []. Consider using a data structure that supports efficient appends, such as Data.Sequence.Seq.