fused-effects-0.2.0.1: A fast, flexible, fused effect system.

Safe HaskellNone
LanguageHaskell2010

Control.Effect.NonDet

Synopsis

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

A monoid on applicative functors.

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

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

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 :: 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] #

(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)
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 (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] #

(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

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

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.