Control.Effect.NonDet

Documentation

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

Constructors

Empty

Choose (Bool -> k)

Instances

Effect NonDet

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

HFunctor NonDet

Defined in Control.Effect.NonDet.Internal

Methods

fmap' :: (a -> b) -> NonDet m a -> NonDet m b

hmap :: (forall x. m x -> n x) -> NonDet m a -> NonDet n a

Functor (NonDet m)

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)

Defined in Control.Effect.Cull

Methods

ret :: a -> CullC m a

eff :: (Cull :+: (NonDet :+: sig)) (CullC m) (CullC m a) -> CullC m a

(Alternative m, Carrier sig m, Effect sig, Monad m) => Carrier (Cut :+: (NonDet :+: sig)) (CutC m)

Defined in Control.Effect.Cut

Methods

ret :: a -> CutC m a

eff :: (Cut :+: (NonDet :+: sig)) (CutC m) (CutC m a) -> CutC m a

(Alternative f, Carrier sig m, Effect sig, Traversable f, Monad f, Monad m) => Carrier (NonDet :+: sig) (OnceC f m)

Defined in Control.Effect.NonDet

Methods

ret :: a -> OnceC f m a

eff :: (NonDet :+: sig) (OnceC f m) (OnceC f m a) -> OnceC f m a

(Alternative f, Monad f, Traversable f, Carrier sig m, Effect sig, Applicative m) => Carrier (NonDet :+: sig) (AltC f m)

Defined in Control.Effect.NonDet

Methods

ret :: a -> AltC f m a

eff :: (NonDet :+: sig) (AltC f m) (AltC f m a) -> AltC f m a

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

Defined in GHC.Base

Methods

empty :: [a]

(<|>) :: [a] -> [a] -> [a]

some :: [a] -> [[a]]

many :: [a] -> [[a]]

Alternative Maybe

Since: base-2.1

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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)

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

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

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

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

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

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)

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

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)

Defined in Control.Effect.NonDet

Methods

ret :: a -> AltC f m a

eff :: (NonDet :+: sig) (AltC f m) (AltC f m a) -> AltC f m a

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

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

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)

Defined in Control.Effect.NonDet

Methods

ret :: a -> OnceC f m a

eff :: (NonDet :+: sig) (OnceC f m) (OnceC f m a) -> OnceC f m a

data Branch m e 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.

Constructors

None e

Pure a

Alt (m a) (m a)

Instances

Functor m => Functor (Branch m e)

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)

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)

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)

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)

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)

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

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

Interpret a Branch into an underlying Alternative context.