Safe Haskell | None |
---|---|
Language | Haskell2010 |
Synopsis
- data NonDet (m :: * -> *) k
- class Applicative f => Alternative (f :: Type -> Type) 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 {}
- data Branch m e 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 #
Instances
Effect NonDet Source # | |
HFunctor NonDet Source # | |
Functor (NonDet m) Source # | |
(Alternative m, Carrier sig m, Effect sig, Monad m) => Carrier (Cull :+: (NonDet :+: sig)) (CullC m) Source # | |
(Alternative m, Carrier sig m, Effect sig, Monad m) => Carrier (Cut :+: (NonDet :+: sig)) (CutC m) Source # | |
(Alternative f, Carrier sig m, Effect sig, Traversable f, Monad f, Monad m) => Carrier (NonDet :+: sig) (OnceC f m) Source # | |
(Alternative f, Monad f, Traversable f, Carrier sig m, Effect sig, Applicative m) => Carrier (NonDet :+: sig) (AltC f m) 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:
The identity of <|>
(<|>) :: f a -> f a -> f a infixl 3 #
An associative binary operation
One or more.
Zero or more.
Instances
Alternative [] | Since: base-2.1 |
Alternative Maybe | Since: base-2.1 |
Alternative IO | Since: base-4.9.0.0 |
Alternative Option | Since: base-4.9.0.0 |
Alternative ZipList | Since: base-4.11.0.0 |
Alternative ReadP | Since: base-4.6.0.0 |
Alternative P | Since: base-4.5.0.0 |
Alternative (U1 :: Type -> Type) | Since: base-4.9.0.0 |
MonadPlus m => Alternative (WrappedMonad m) | Since: base-2.1 |
Defined in Control.Applicative 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 |
Defined in Control.Arrow 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 |
(Member NonDet sig, Carrier sig carrier) => Alternative (Eff carrier) Source # | 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) |
Alternative f => Alternative (Rec1 f) | Since: base-4.9.0.0 |
(ArrowZero a, ArrowPlus a) => Alternative (WrappedArrow a b) | Since: base-2.1 |
Defined in Control.Applicative 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 |
Alternative f => Alternative (Alt f) | Since: base-4.8.0.0 |
(Functor m, Monad m, Error e) => Alternative (ErrorT e m) | |
(Alternative f, Alternative g) => Alternative (f :*: g) | Since: base-4.9.0.0 |
(Alternative f, Alternative g) => Alternative (Product f g) | Since: base-4.9.0.0 |
Alternative f => Alternative (M1 i c f) | Since: base-4.9.0.0 |
(Alternative f, Applicative g) => Alternative (f :.: g) | Since: base-4.9.0.0 |
(Alternative f, Applicative g) => Alternative (Compose f g) | Since: base-4.9.0.0 |
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
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
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.
Instances
Functor m => Functor (Branch m e) Source # | |
Foldable m => Foldable (Branch m e) Source # | |
Defined in Control.Effect.NonDet.Internal 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 # | |
Traversable m => Traversable (Branch m e) Source # | |
Defined in Control.Effect.NonDet.Internal | |
(Eq e, Eq a, Eq (m a)) => Eq (Branch m e a) Source # | |
(Ord e, Ord a, Ord (m a)) => Ord (Branch m e a) Source # | |
Defined in Control.Effect.NonDet.Internal | |
(Show e, Show a, Show (m a)) => Show (Branch m e a) Source # | |
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.