HORIZON HASKELLDocslts/ghc-10.0.x8c2f8e82026-10-19Search names, modules, packages, or :: a typeCtrl K

GHC 10.0.0.20260917 · lts/ghc-10.0.x · 8c2f8e8 · 2026-10-19

Modulefused-effects-1.1.2.7Haskell2010

Control.Carrier.NonDet.Church

Provides NonDetC, a carrier for NonDet effects providing choice and failure.

Under the hood, it uses a Church-encoded structure and a binary tree to prevent the problems associated with a naïve list-based implementation.

  • 1 type
  • 3 values

NonDet carrier

4 declarations
valuerunNonDet
  1. :: (m b -> m b -> m b)

    Handles choice (<|>)

  2. -> (a -> m b)

    Handles embedding results (pure)

  3. -> m b

    Handles failure (empty)

  4. -> NonDetC m a

    A nondeterministic computation to execute

  5. -> m b
#

Run a NonDet effect, using the provided functions to interpret choice, leaf results, and failure.

runNonDet fork leaf nil (pure a <|> empty) = leaf a `fork` nil
valuerunNonDetA :: (Alternative f, Applicative m) => NonDetC 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, unless used with cull, this will still enumerate the entire search space before returning, meaning that it will diverge for infinite search spaces, even when using Maybe.

runNonDetA (pure a) = pure [a]

runNonDetA (pure a) = pure (Just a)
newtypenewtype NonDetC (m :: Type -> Type) a
#

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

Constructors

  • NonDetC (forall b. (m b -> m b -> m b) -> (a -> m b) -> m b -> m b)
Instances10MonadTrans, Monad, Functor, MonadFix, MonadFail, Applicative, …
  • MonadTrans NonDetCDefined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church
  • Monad (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church
  • Functor (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church
  • MonadFix m => MonadFix (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church

    Separate fixpoints are computed for each branch.

  • MonadFail m => MonadFail (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church
  • Applicative (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church
  • Alternative (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church
  • MonadPlus (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church
  • MonadIO m => MonadIO (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church
  • Algebra sig m => Algebra (NonDet :+: sig) (NonDetC m)Defined in fused-effects-1.1.2.7 · Control.Carrier.NonDet.Church

NonDet effects

0 declarations

module Control.Effect.NonDet