-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Class of data structures that can be unfolded.
--   
--   Just as there's a Foldable class, there should also be an Unfoldable
--   class.
--   
--   This package provides one. Example unfolds are:
--   
--   <ul>
--   <li>Random values</li>
--   <li>Enumeration of all values (depth-first or breadth-first)</li>
--   <li>Convert from a list</li>
--   </ul>
--   
--   Some examples can be found in the examples directory.
@package unfoldable
@version 0.9


-- | Unfolders provide a way to unfold data structures. They are basically
--   <a>Alternative</a> instances, but the <a>choose</a> method allows the
--   unfolder to do something special for the recursive positions of the
--   data structure.
module Data.Unfolder

-- | Unfolders provide a way to unfold data structures. The methods have
--   default implementations in terms of <a>Alternative</a>, but you can
--   implement <a>chooseMap</a> to act on recursive positions of the data
--   structure, or simply to provide a faster implementation than 'asum .
--   map f'.
class Alternative f => Unfolder f where choose = chooseMap id chooseMap f = asum . map f chooseInt n = chooseMap pure [0 .. n - 1]

-- | Choose one of the values from the list.
choose :: Unfolder f => [f a] -> f a

-- | Choose one of the values from the list and apply the given function.
chooseMap :: Unfolder f => (a -> f b) -> [a] -> f b

-- | Given a number <tt>n</tt>, return a number between '0' and 'n - 1'.
chooseInt :: Unfolder f => Int -> f Int

-- | If an unfolder is monadic, <a>choose</a> can be implemented in terms
--   of <a>chooseInt</a>.
chooseMonadDefault :: (Monad m, Unfolder m) => [m a] -> m a

-- | If an unfolder is monadic, <a>chooseMap</a> can be implemented in
--   terms of <a>chooseInt</a>.
chooseMapMonadDefault :: (Monad m, Unfolder m) => (a -> m b) -> [a] -> m b

-- | If a datatype is enumerable, we can use <a>chooseInt</a> to generate a
--   value. This is the function to use if you want to unfold a datatype
--   that has no type arguments (has kind <tt>*</tt>).
between :: (Unfolder f, Enum a) => a -> a -> f a

-- | <a>betweenD</a> uses <a>choose</a> to generate a value. It chooses
--   between the lower bound and one of the higher values. This means that
--   f.e. breadth-first unfolding and arbitrary will prefer lower values.
betweenD :: (Unfolder f, Enum a) => a -> a -> f a

-- | If a datatype is also bounded, we choose between all possible values.
--   
--   <pre>
--   boundedEnum = between minBound maxBound
--   </pre>
boundedEnum :: (Unfolder f, Bounded a, Enum a) => f a

-- | <pre>
--   boundedEnumD = betweenD minBound maxBound
--   </pre>
boundedEnumD :: (Unfolder f, Bounded a, Enum a) => f a
newtype Random g m a
Random :: StateT g m a -> Random g m a
[getRandom] :: Random g m a -> StateT g m a

-- | A variant of Test.QuickCheck.Gen, with failure and a count of the
--   number of recursive positions.
data Arb a
Arb :: Int -> (Gen (Maybe a)) -> Arb a
arbUnit :: Arbitrary a => Arb a

-- | Variant of <a>Constant</a> that does multiplication of the constants
--   for <tt>&lt;*&gt;</tt> and addition for <tt>&lt;|&gt;</tt>.
newtype NumConst a x
NumConst :: a -> NumConst a x
[getNumConst] :: NumConst a x -> a

-- | An <a>UnfolderTransformer</a> changes the way an <a>Unfolder</a>
--   unfolds.
class UnfolderTransformer t

-- | Lift a computation from the argument unfolder to the constructed
--   unfolder.
lift :: (UnfolderTransformer t, Unfolder f) => f a -> t f a

-- | Run an unfolding function with one argument using an
--   <a>UnfolderTransformer</a>, given a way to run the transformer.
ala :: (UnfolderTransformer t, Unfolder f) => (t f b -> f b) -> (t f a -> t f b) -> f a -> f b

-- | Run an unfolding function with two arguments using an
--   <a>UnfolderTransformer</a>, given a way to run the transformer.
ala2 :: (UnfolderTransformer t, Unfolder f) => (t f c -> f c) -> (t f a -> t f b -> t f c) -> f a -> f b -> f c

-- | Run an unfolding function with three arguments using an
--   <a>UnfolderTransformer</a>, given a way to run the transformer.
ala3 :: (UnfolderTransformer t, Unfolder f) => (t f d -> f d) -> (t f a -> t f b -> t f c -> t f d) -> f a -> f b -> f c -> f d

-- | <a>DualA</a> flips the <tt>&lt;|&gt;</tt> operator from
--   <a>Alternative</a>.
newtype DualA f a
DualA :: f a -> DualA f a
[getDualA] :: DualA f a -> f a

-- | Natural transformations
data NT f g
NT :: (forall a. f a -> g a) -> NT f g
[getNT] :: NT f g -> forall a. f a -> g a
newtype WithRec f a
WithRec :: ReaderT (Int -> NT f f) f a -> WithRec f a
[getWithRec] :: WithRec f a -> ReaderT (Int -> NT f f) f a

-- | Apply a certain function of type <tt>f a -&gt; f a</tt> to the result
--   of a <a>choose</a>. The depth is passed as <a>Int</a>, so you can
--   apply a different function at each depth. Because of a
--   <tt>forall</tt>, the function needs to be wrapped in a <a>NT</a>
--   constructor. See <a>limitDepth</a> for an example how to use this
--   function.
withRec :: (Int -> NT f f) -> WithRec f a -> f a

-- | Limit the depth of an unfolding.
limitDepth :: Unfolder f => Int -> WithRec f a -> f a

-- | Return a generator of values of a given depth. Returns <a>Nothing</a>
--   if there are no values of that depth or deeper. The depth is the
--   number of <a>choose</a> calls.
newtype BFS f x
BFS :: ((Int, Split) -> Maybe [f x]) -> BFS f x
[getBFS] :: BFS f x -> (Int, Split) -> Maybe [f x]
type Split = Int -> [(Int, Int)]

-- | Change the order of unfolding to be breadth-first, by maximum depth of
--   the components.
bfs :: Unfolder f => BFS f x -> f x

-- | Change the order of unfolding to be breadth-first, by the sum of
--   depths of the components.
bfsBySum :: Unfolder f => BFS f x -> f x
instance GHC.Show.Show a => GHC.Show.Show (Data.Unfolder.NumConst a x)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Unfolder.NumConst a x)
instance GHC.Base.Alternative f => GHC.Base.Alternative (Data.Unfolder.WithRec f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Data.Unfolder.WithRec f)
instance GHC.Base.Functor f => GHC.Base.Functor (Data.Unfolder.WithRec f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Data.Unfolder.DualA f)
instance GHC.Base.Functor f => GHC.Base.Functor (Data.Unfolder.DualA f)
instance GHC.Show.Show (f a) => GHC.Show.Show (Data.Unfolder.DualA f a)
instance GHC.Classes.Eq (f a) => GHC.Classes.Eq (Data.Unfolder.DualA f a)
instance GHC.Base.Monad m => GHC.Base.Monad (Data.Unfolder.Random g m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Data.Unfolder.Random g m)
instance GHC.Base.Functor m => GHC.Base.Functor (Data.Unfolder.Random g m)
instance GHC.Base.MonadPlus m => Data.Unfolder.Unfolder (Control.Applicative.WrappedMonad m)
instance (Control.Arrow.ArrowZero a, Control.Arrow.ArrowPlus a) => Data.Unfolder.Unfolder (Control.Applicative.WrappedArrow a b)
instance Data.Unfolder.Unfolder []
instance Data.Unfolder.Unfolder GHC.Base.Maybe
instance (Data.Unfolder.Unfolder p, Data.Unfolder.Unfolder q) => Data.Unfolder.Unfolder (Data.Functor.Product.Product p q)
instance (Data.Unfolder.Unfolder p, GHC.Base.Applicative q) => Data.Unfolder.Unfolder (Data.Functor.Compose.Compose p q)
instance Data.Unfolder.Unfolder f => Data.Unfolder.Unfolder (Data.Functor.Reverse.Reverse f)
instance Data.Unfolder.Unfolder f => Data.Unfolder.Unfolder (Control.Applicative.Backwards.Backwards f)
instance Data.Unfolder.Unfolder f => Data.Unfolder.Unfolder (Control.Applicative.Lift.Lift f)
instance (GHC.Base.Functor m, GHC.Base.Monad m, Control.Monad.Trans.Error.Error e) => Data.Unfolder.Unfolder (Control.Monad.Trans.Error.ErrorT e m)
instance (GHC.Base.Functor m, GHC.Base.Monad m, GHC.Base.Monoid e) => Data.Unfolder.Unfolder (Control.Monad.Trans.Except.ExceptT e m)
instance GHC.Base.Applicative f => Data.Unfolder.Unfolder (Control.Monad.Trans.List.ListT f)
instance (GHC.Base.Functor m, GHC.Base.Monad m) => Data.Unfolder.Unfolder (Control.Monad.Trans.Maybe.MaybeT m)
instance (GHC.Base.Monoid w, GHC.Base.MonadPlus m, Data.Unfolder.Unfolder m) => Data.Unfolder.Unfolder (Control.Monad.Trans.RWS.Lazy.RWST r w s m)
instance (GHC.Base.MonadPlus m, Data.Unfolder.Unfolder m) => Data.Unfolder.Unfolder (Control.Monad.Trans.State.Lazy.StateT s m)
instance Data.Unfolder.Unfolder m => Data.Unfolder.Unfolder (Control.Monad.Trans.Reader.ReaderT r m)
instance (GHC.Base.Monoid w, Data.Unfolder.Unfolder m) => Data.Unfolder.Unfolder (Control.Monad.Trans.Writer.Lazy.WriterT w m)
instance (GHC.Base.Functor m, GHC.Base.Monad m, System.Random.RandomGen g) => GHC.Base.Alternative (Data.Unfolder.Random g m)
instance (GHC.Base.Functor m, GHC.Base.Monad m, System.Random.RandomGen g) => GHC.Base.MonadPlus (Data.Unfolder.Random g m)
instance (GHC.Base.Functor m, GHC.Base.Monad m, System.Random.RandomGen g) => Data.Unfolder.Unfolder (Data.Unfolder.Random g m)
instance GHC.Base.Alternative f => GHC.Base.Alternative (Data.Unfolder.DualA f)
instance Data.Unfolder.Unfolder f => Data.Unfolder.Unfolder (Data.Unfolder.DualA f)
instance Data.Unfolder.UnfolderTransformer Data.Unfolder.DualA
instance Data.Unfolder.Unfolder f => Data.Unfolder.Unfolder (Data.Unfolder.WithRec f)
instance Data.Unfolder.UnfolderTransformer Data.Unfolder.WithRec
instance GHC.Base.Functor f => GHC.Base.Functor (Data.Unfolder.BFS f)
instance GHC.Base.Applicative f => GHC.Base.Applicative (Data.Unfolder.BFS f)
instance GHC.Base.Applicative f => GHC.Base.Alternative (Data.Unfolder.BFS f)
instance GHC.Base.Applicative f => Data.Unfolder.Unfolder (Data.Unfolder.BFS f)
instance Data.Unfolder.UnfolderTransformer Data.Unfolder.BFS
instance GHC.Base.Functor Data.Unfolder.Arb
instance GHC.Base.Applicative Data.Unfolder.Arb
instance GHC.Base.Alternative Data.Unfolder.Arb
instance Data.Unfolder.Unfolder Data.Unfolder.Arb
instance GHC.Base.Functor (Data.Unfolder.NumConst a)
instance GHC.Num.Num a => GHC.Base.Applicative (Data.Unfolder.NumConst a)
instance GHC.Num.Num a => GHC.Base.Alternative (Data.Unfolder.NumConst a)
instance GHC.Num.Num a => Data.Unfolder.Unfolder (Data.Unfolder.NumConst a)
instance Data.Unfolder.Unfolder Data.Sequence.Seq


-- | Class of data structures that can be unfolded.
module Data.Unfoldable

-- | Data structures that can be unfolded.
--   
--   For example, given a data type
--   
--   <pre>
--   data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--   </pre>
--   
--   a suitable instance would be
--   
--   <pre>
--   instance Unfoldable Tree where
--     unfold fa = choose
--       [ pure Empty
--       , Leaf &lt;$&gt; fa
--       , Node &lt;$&gt; unfold fa &lt;*&gt; fa &lt;*&gt; unfold fa
--       ]
--   </pre>
--   
--   i.e. it follows closely the instance for <a>Traversable</a>, but
--   instead of matching on an input value, we <a>choose</a> from a list of
--   all cases.
--   
--   Instead of manually writing the <a>Unfoldable</a> instance, you can
--   add a <tt>deriving</tt> <a>Generic1</a> to your datatype and declare
--   an <a>Unfoldable</a> instance without giving a definition for
--   <a>unfold</a>.
--   
--   For example the previous example can be simplified to just:
--   
--   <pre>
--   {-# LANGUAGE DeriveGeneric #-}
--   
--   import GHC.Generics
--   
--   data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) deriving Generic1
--   
--   instance Unfoldable Tree
--   </pre>
class Unfoldable t where unfold fa = to1 <$> choose (gunfold fa)

-- | Given a way to generate elements, return a way to generate structures
--   containing those elements.
unfold :: (Unfoldable t, Unfolder f) => f a -> f (t a)

-- | Given a way to generate elements, return a way to generate structures
--   containing those elements.
unfold :: (Unfoldable t, Generic1 t, GUnfold (Rep1 t), Unfolder f) => f a -> f (t a)

-- | Unfold the structure, always using <tt>()</tt> as elements.
unfold_ :: (Unfoldable t, Unfolder f) => f (t ())

-- | Breadth-first unfold, which orders the result by the number of
--   <a>choose</a> calls.
unfoldBF :: (Unfoldable t, Unfolder f) => f a -> f (t a)

-- | Unfold the structure breadth-first, always using <tt>()</tt> as
--   elements.
unfoldBF_ :: (Unfoldable t, Unfolder f) => f (t ())

-- | <tt>unfoldr</tt> builds a data structure from a seed value. It can be
--   specified as:
--   
--   <pre>
--   unfoldr f z == fromList (Data.List.unfoldr f z)
--   </pre>
unfoldr :: Unfoldable t => (b -> Maybe (a, b)) -> b -> Maybe (t a)

-- | Create a data structure using the list as input. This can fail because
--   there might not be a data structure with the same number of element
--   positions as the number of elements in the list.
fromList :: Unfoldable t => [a] -> Maybe (t a)

-- | Always choose the first constructor.
leftMost :: Unfoldable t => Maybe (t ())

-- | Always choose the last constructor.
rightMost :: Unfoldable t => Maybe (t ())

-- | Generate all the values depth-first.
allDepthFirst :: Unfoldable t => [t ()]

-- | Generate all the values upto a given depth, depth-first.
allToDepth :: Unfoldable t => Int -> [t ()]

-- | Generate all the values breadth-first.
allBreadthFirst :: Unfoldable t => [t ()]

-- | Generate a random value, can be used as default instance for
--   <a>Random</a>.
randomDefault :: (Random a, RandomGen g, Unfoldable t) => g -> (t a, g)

-- | Provides a QuickCheck generator, can be used as default instance for
--   <a>Arbitrary</a>.
arbitraryDefault :: (Arbitrary a, Unfoldable t) => Gen (t a)
instance Data.Unfoldable.GUnfold GHC.Generics.V1
instance Data.Unfoldable.GUnfold GHC.Generics.U1
instance Data.Unfoldable.GUnfold GHC.Generics.Par1
instance Data.Unfoldable.Unfoldable f => Data.Unfoldable.GUnfold (GHC.Generics.Rec1 f)
instance (GHC.Enum.Bounded c, GHC.Enum.Enum c) => Data.Unfoldable.GUnfold (GHC.Generics.K1 i c)
instance Data.Unfoldable.GUnfold f => Data.Unfoldable.GUnfold (GHC.Generics.M1 i c f)
instance (Data.Unfoldable.GUnfold f, Data.Unfoldable.GUnfold g) => Data.Unfoldable.GUnfold (f GHC.Generics.:+: g)
instance (Data.Unfoldable.GUnfold f, Data.Unfoldable.GUnfold g) => Data.Unfoldable.GUnfold (f GHC.Generics.:*: g)
instance (Data.Unfoldable.GUnfold f, Data.Unfoldable.GUnfold g) => Data.Unfoldable.GUnfold (f GHC.Generics.:.: g)
instance Data.Unfoldable.Unfoldable []
instance Data.Unfoldable.Unfoldable GHC.Base.Maybe
instance (GHC.Enum.Bounded a, GHC.Enum.Enum a) => Data.Unfoldable.Unfoldable (Data.Either.Either a)
instance (GHC.Enum.Bounded a, GHC.Enum.Enum a) => Data.Unfoldable.Unfoldable ((,) a)
instance Data.Unfoldable.Unfoldable Data.Functor.Identity.Identity
instance (GHC.Enum.Bounded a, GHC.Enum.Enum a) => Data.Unfoldable.Unfoldable (Data.Functor.Constant.Constant a)
instance (Data.Unfoldable.Unfoldable p, Data.Unfoldable.Unfoldable q) => Data.Unfoldable.Unfoldable (Data.Functor.Product.Product p q)
instance (Data.Unfoldable.Unfoldable p, Data.Unfoldable.Unfoldable q) => Data.Unfoldable.Unfoldable (Data.Functor.Sum.Sum p q)
instance (Data.Unfoldable.Unfoldable p, Data.Unfoldable.Unfoldable q) => Data.Unfoldable.Unfoldable (Data.Functor.Compose.Compose p q)
instance Data.Unfoldable.Unfoldable f => Data.Unfoldable.Unfoldable (Data.Functor.Reverse.Reverse f)
instance Data.Unfoldable.Unfoldable Data.Sequence.Seq


-- | Class of data structures with 2 type arguments that can be unfolded.
module Data.Biunfoldable

-- | Data structures with 2 type arguments (kind <tt>* -&gt; * -&gt;
--   *</tt>) that can be unfolded.
--   
--   For example, given a data type
--   
--   <pre>
--   data Tree a b = Empty | Leaf a | Node (Tree a b) b (Tree a b)
--   </pre>
--   
--   a suitable instance would be
--   
--   <pre>
--   instance Biunfoldable Tree where
--     biunfold fa fb = choose
--       [ pure Empty
--       , Leaf &lt;$&gt; fa
--       , Node &lt;$&gt; biunfold fa fb &lt;*&gt; fb &lt;*&gt; biunfold fa fb
--       ]
--   </pre>
--   
--   i.e. it follows closely the instance for <tt>Bitraversable</tt>, but
--   instead of matching on an input value, we <a>choose</a> from a list of
--   all cases.
class Biunfoldable t

-- | Given a way to generate elements, return a way to generate structures
--   containing those elements.
biunfold :: (Biunfoldable t, Unfolder f) => f a -> f b -> f (t a b)

-- | Unfold the structure, always using <tt>()</tt> as elements.
biunfold_ :: (Biunfoldable t, Unfolder f) => f (t () ())

-- | Breadth-first unfold, which orders the result by the number of
--   <a>choose</a> calls.
biunfoldBF :: (Biunfoldable t, Unfolder f) => f a -> f b -> f (t a b)

-- | Unfold the structure breadth-first, always using <tt>()</tt> as
--   elements.
biunfoldBF_ :: (Biunfoldable t, Unfolder f) => f (t () ())

-- | <tt>biunfoldr</tt> builds a data structure from a seed value.
biunfoldr :: Biunfoldable t => (c -> Maybe (a, c)) -> (c -> Maybe (b, c)) -> c -> Maybe (t a b)

-- | Create a data structure using the lists as input. This can fail
--   because there might not be a data structure with the same number of
--   element positions as the number of elements in the lists.
fromLists :: Biunfoldable t => [a] -> [b] -> Maybe (t a b)

-- | Generate a random value, can be used as default instance for
--   <a>Random</a>.
randomDefault :: (Random a, Random b, RandomGen g, Biunfoldable t) => g -> (t a b, g)

-- | Provides a QuickCheck generator, can be used as default instance for
--   <a>Arbitrary</a>.
arbitraryDefault :: (Arbitrary a, Arbitrary b, Biunfoldable t) => Gen (t a b)
instance Data.Biunfoldable.Biunfoldable Data.Either.Either
instance Data.Biunfoldable.Biunfoldable (,)
instance Data.Biunfoldable.Biunfoldable Data.Functor.Constant.Constant