module Control.Effect.NonDet
  ( NonDet(..)
  , Alternative(..)
  , runNonDetAll
  ) where

import Control.Applicative
import Control.Effect.Base
import Control.Effect.Internal (NonDet(..))

-- | Handles a 'NonDet' effect, collecting the results of all branches of the
-- computation. The results are collected __strictly__, which means that /all/
-- effects are evaluated (even if using an 'Alternative' that ignores subsequent
-- results, such as 'Maybe').
--
-- The result is also built using a __left-associated__ sequence of '<|>' calls,
-- which allows the result to be constructed in constant space if an appropriate
-- 'Alternative' instance is used, but can lead to very poor performance for
-- types with inefficient append operations, such as @[]@. Consider using a data
-- structure that supports efficient appends, such as @Data.Sequence.Seq@.
runNonDetAll :: Alternative f => Eff (NonDet ': effs) a -> Eff effs (f a)
runNonDetAll :: Eff (NonDet : effs) a -> Eff effs (f a)
runNonDetAll = (a -> Eff effs (f a))
-> (forall (effs' :: [(* -> *) -> * -> *]) b.
    (NonDet :< effs') =>
    NonDet (Eff effs') b -> Handle NonDet effs a (f a) effs' b)
-> Eff (NonDet : effs) a
-> Eff effs (f a)
forall (eff :: (* -> *) -> * -> *) a r
       (effs :: [(* -> *) -> * -> *]).
(a -> Eff effs r)
-> (forall (effs' :: [(* -> *) -> * -> *]) b.
    (eff :< effs') =>
    eff (Eff effs') b -> Handle eff effs a r effs' b)
-> Eff (eff : effs) a
-> Eff effs r
handle (f a -> Eff effs (f a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (f a -> Eff effs (f a)) -> (a -> f a) -> a -> Eff effs (f a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure) \case
  NonDet (Eff effs') b
Empty -> f a -> Handle NonDet effs a (f a) effs' b
forall r (eff :: (* -> *) -> * -> *) (effs :: [(* -> *) -> * -> *])
       i (effs' :: [(* -> *) -> * -> *]) a.
r -> Handle eff effs i r effs' a
abort f a
forall (f :: * -> *) a. Alternative f => f a
empty
  NonDet (Eff effs') b
Choose -> ((Bool -> Eff effs (f a)) -> Eff effs (f a))
-> Handle NonDet effs a (f a) effs' Bool
forall a (effs :: [(* -> *) -> * -> *]) r
       (eff :: (* -> *) -> * -> *) i (effs' :: [(* -> *) -> * -> *]).
((a -> Eff effs r) -> Eff effs r) -> Handle eff effs i r effs' a
control \Bool -> Eff effs (f a)
k -> (f a -> f a -> f a)
-> Eff effs (f a) -> Eff effs (f a) -> Eff effs (f a)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 f a -> f a -> f a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>) (Bool -> Eff effs (f a)
k Bool
True) (Bool -> Eff effs (f a)
k Bool
False)