Safe Haskell	None
Language	Haskell2010

Control.Effect.NonDet

Synopsis

data NonDet (m :: * -> *) k
- = Empty
- | Choose (Bool -> k)
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]
runNonDet :: (Alternative f, Applicative m) => NonDetC m a -> m (f a)
newtype NonDetC m a = NonDetC {
- runNonDetC :: forall b. (a -> m b -> m b) -> m b -> m b
}

Documentation

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

Constructors

Empty
Choose (Bool -> k)

Instances

Effect NonDet Source #
Instance details Defined in Control.Effect.NonDet 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 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 Methods fmap :: (a -> b) -> NonDet m a -> NonDet m b # (<$) :: a -> NonDet m b -> NonDet m a #
(Carrier sig m, Effect sig) => Carrier (NonDet :+: sig) (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods eff :: (NonDet :+: sig) (NonDetC m) (NonDetC m a) -> NonDetC m a Source #
(Carrier sig m, Effect sig) => Carrier (NonDet :+: sig) (OnceC m) Source #
Instance details Defined in Control.Effect.Cull Methods eff :: (NonDet :+: sig) (OnceC m) (OnceC m a) -> OnceC m a Source #
(Carrier sig m, Effect sig) => Carrier (Cut :+: (NonDet :+: sig)) (CutC m) Source #
Instance details Defined in Control.Effect.Cut Methods eff :: (Cut :+: (NonDet :+: sig)) (CutC m) (CutC m a) -> CutC m a Source #
(Carrier sig m, Effect sig) => Carrier (Cull :+: (NonDet :+: sig)) (CullC m) Source #
Instance details Defined in Control.Effect.Cull Methods eff :: (Cull :+: (NonDet :+: sig)) (CullC m) (CullC m a) -> CullC m a Source #

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

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] #
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 :: Type -> Type)	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] #
Alternative m => Alternative (ResourceC m) Source #
Instance details Defined in Control.Effect.Resource Methods empty :: ResourceC m a # (<\|>) :: ResourceC m a -> ResourceC m a -> ResourceC m a # some :: ResourceC m a -> ResourceC m [a] # many :: ResourceC m a -> ResourceC m [a] #
Alternative (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods empty :: NonDetC m a # (<\|>) :: NonDetC m a -> NonDetC m a -> NonDetC m a # some :: NonDetC m a -> NonDetC m [a] # many :: NonDetC m a -> NonDetC m [a] #
Alternative m => Alternative (LiftC m) Source #
Instance details Defined in Control.Effect.Lift Methods empty :: LiftC m a # (<\|>) :: LiftC m a -> LiftC m a -> LiftC m a # some :: LiftC m a -> LiftC m [a] # many :: LiftC m a -> LiftC m [a] #
(Alternative m, Monad m) => Alternative (FreshC m) Source #
Instance details Defined in Control.Effect.Fresh Methods empty :: FreshC m a # (<\|>) :: FreshC m a -> FreshC m a -> FreshC m a # some :: FreshC m a -> FreshC m [a] # many :: FreshC m a -> FreshC m [a] #
Alternative m => Alternative (FailC m) Source #
Instance details Defined in Control.Effect.Fail Methods empty :: FailC m a # (<\|>) :: FailC m a -> FailC m a -> FailC m a # some :: FailC m a -> FailC m [a] # many :: FailC m a -> FailC m [a] #
Alternative (CutC m) Source #
Instance details Defined in Control.Effect.Cut Methods empty :: CutC m a # (<\|>) :: CutC m a -> CutC m a -> CutC m a # some :: CutC m a -> CutC m [a] # many :: CutC m a -> CutC m [a] #
Alternative (OnceC m) Source #
Instance details Defined in Control.Effect.Cull Methods empty :: OnceC m a # (<\|>) :: OnceC m a -> OnceC m a -> OnceC m a # some :: OnceC m a -> OnceC m [a] # many :: OnceC m a -> OnceC m [a] #
Alternative (CullC m) Source #
Instance details Defined in Control.Effect.Cull Methods empty :: CullC m a # (<\|>) :: CullC m a -> CullC m a -> CullC m a # some :: CullC m a -> CullC m [a] # many :: CullC m a -> CullC m [a] #
(Alternative m, Monad m) => Alternative (TraceByReturningC m) Source #
Instance details Defined in Control.Effect.Trace Methods empty :: TraceByReturningC m a # (<\|>) :: TraceByReturningC m a -> TraceByReturningC m a -> TraceByReturningC m a # some :: TraceByReturningC m a -> TraceByReturningC m [a] # many :: TraceByReturningC m a -> TraceByReturningC m [a] #
Alternative m => Alternative (TraceByIgnoringC m) Source #
Instance details Defined in Control.Effect.Trace Methods empty :: TraceByIgnoringC m a # (<\|>) :: TraceByIgnoringC m a -> TraceByIgnoringC m a -> TraceByIgnoringC m a # some :: TraceByIgnoringC m a -> TraceByIgnoringC m [a] # many :: TraceByIgnoringC m a -> TraceByIgnoringC m [a] #
Alternative m => Alternative (TraceByPrintingC m) Source #
Instance details Defined in Control.Effect.Trace Methods empty :: TraceByPrintingC m a # (<\|>) :: TraceByPrintingC m a -> TraceByPrintingC m a -> TraceByPrintingC m a # some :: TraceByPrintingC m a -> TraceByPrintingC m [a] # many :: TraceByPrintingC m a -> TraceByPrintingC m [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 (Ap f)	Since: base-4.12.0.0
Instance details Defined in Data.Monoid Methods empty :: Ap f a # (<\|>) :: Ap f a -> Ap f a -> Ap f a # some :: Ap f a -> Ap f [a] # many :: Ap f a -> Ap f [a] #
Alternative f => Alternative (Alt f)	Since: base-4.8.0.0
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] #
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, 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 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, Monad m) => Alternative (StateC s m) Source #
Instance details Defined in Control.Effect.State.Strict Methods empty :: StateC s m a # (<\|>) :: StateC s m a -> StateC s m a -> StateC s m a # some :: StateC s m a -> StateC s m [a] # many :: StateC s m a -> StateC s m [a] #
(Alternative m, Monad m) => Alternative (StateC s m) Source #
Instance details Defined in Control.Effect.State.Lazy Methods empty :: StateC s m a # (<\|>) :: StateC s m a -> StateC s m a -> StateC s m a # some :: StateC s m a -> StateC s m [a] # many :: StateC s m a -> StateC s m [a] #
Alternative m => Alternative (ReaderC r m) Source #
Instance details Defined in Control.Effect.Reader Methods empty :: ReaderC r m a # (<\|>) :: ReaderC r m a -> ReaderC r m a -> ReaderC r m a # some :: ReaderC r m a -> ReaderC r m [a] # many :: ReaderC r m a -> ReaderC r m [a] #
(Alternative m, Monad m) => Alternative (RandomC g m) Source #
Instance details Defined in Control.Effect.Random Methods empty :: RandomC g m a # (<\|>) :: RandomC g m a -> RandomC g m a -> RandomC g m a # some :: RandomC g m a -> RandomC g m [a] # many :: RandomC g m a -> RandomC g m [a] #
Alternative m => Alternative (InterpretC eff m) Source #
Instance details Defined in Control.Effect.Interpret Methods empty :: InterpretC eff m a # (<\|>) :: InterpretC eff m a -> InterpretC eff m a -> InterpretC eff m a # some :: InterpretC eff m a -> InterpretC eff m [a] # many :: InterpretC eff m a -> InterpretC eff m [a] #
Alternative m => Alternative (ErrorC e m) Source #
Instance details Defined in Control.Effect.Error Methods empty :: ErrorC e m a # (<\|>) :: ErrorC e m a -> ErrorC e m a -> ErrorC e m a # some :: ErrorC e m a -> ErrorC e m [a] # many :: ErrorC e m a -> ErrorC e m [a] #
Alternative m => Alternative (ResumableWithC err m) Source #
Instance details Defined in Control.Effect.Resumable Methods empty :: ResumableWithC err m a # (<\|>) :: ResumableWithC err m a -> ResumableWithC err m a -> ResumableWithC err m a # some :: ResumableWithC err m a -> ResumableWithC err m [a] # many :: ResumableWithC err m a -> ResumableWithC err m [a] #
Alternative m => Alternative (ResumableC err m) Source #
Instance details Defined in Control.Effect.Resumable Methods empty :: ResumableC err m a # (<\|>) :: ResumableC err m a -> ResumableC err m a -> ResumableC err m a # some :: ResumableC err m a -> ResumableC err m [a] # many :: ResumableC err m a -> ResumableC err m [a] #
(Alternative m, Monad m) => Alternative (WriterC w m) Source #
Instance details Defined in Control.Effect.Writer Methods empty :: WriterC w m a # (<\|>) :: WriterC w m a -> WriterC w m a -> WriterC w m a # some :: WriterC w m a -> WriterC w m [a] # many :: WriterC w m a -> WriterC w m [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 m, Monad m) => Alternative (InterpretStateC eff s m) Source #
Instance details Defined in Control.Effect.Interpret Methods empty :: InterpretStateC eff s m a # (<\|>) :: InterpretStateC eff s m a -> InterpretStateC eff s m a -> InterpretStateC eff s m a # some :: InterpretStateC eff s m a -> InterpretStateC eff s m [a] # many :: InterpretStateC eff s m a -> InterpretStateC eff s m [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, Applicative m) => NonDetC 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 NonDetC m a Source #

A carrier for NonDet effects based on Ralf Hinze’s design described in Deriving Backtracking Monad Transformers.

Constructors

NonDetC
Fields runNonDetC :: forall b. (a -> m b -> m b) -> m b -> m b A higher-order function receiving two parameters: a function to combine each solution with the rest of the solutions, and an action to run when no results are produced.

Instances

MonadTrans NonDetC Source #
Instance details Defined in Control.Effect.NonDet Methods lift :: Monad m => m a -> NonDetC m a #
Monad (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods (>>=) :: NonDetC m a -> (a -> NonDetC m b) -> NonDetC m b # (>>) :: NonDetC m a -> NonDetC m b -> NonDetC m b # return :: a -> NonDetC m a # fail :: String -> NonDetC m a #
Functor (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods fmap :: (a -> b) -> NonDetC m a -> NonDetC m b # (<$) :: a -> NonDetC m b -> NonDetC m a #
MonadFail m => MonadFail (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods fail :: String -> NonDetC m a #
Applicative (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods pure :: a -> NonDetC m a # (<>) :: NonDetC m (a -> b) -> NonDetC m a -> NonDetC m b # liftA2 :: (a -> b -> c) -> NonDetC m a -> NonDetC m b -> NonDetC m c # (>) :: NonDetC m a -> NonDetC m b -> NonDetC m b # (<*) :: NonDetC m a -> NonDetC m b -> NonDetC m a #
MonadIO m => MonadIO (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods liftIO :: IO a -> NonDetC m a #
Alternative (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods empty :: NonDetC m a # (<\|>) :: NonDetC m a -> NonDetC m a -> NonDetC m a # some :: NonDetC m a -> NonDetC m [a] # many :: NonDetC m a -> NonDetC m [a] #
MonadPlus (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods mzero :: NonDetC m a # mplus :: NonDetC m a -> NonDetC m a -> NonDetC m a #
(Carrier sig m, Effect sig) => Carrier (NonDet :+: sig) (NonDetC m) Source #
Instance details Defined in Control.Effect.NonDet Methods eff :: (NonDet :+: sig) (NonDetC m) (NonDetC m a) -> NonDetC m a Source #