Copyright	(c) Sjoerd Visscher 2014
License	BSD-style (see the file LICENSE)
Maintainer	sjoerd@w3future.com
Stability	experimental
Portability	non-portable
Safe Haskell	Trustworthy
Language	Haskell98

Data.Unfolder

Contents

Unfolder
- Unfolder instances
UnfolderTransformer
- UnfolderTransformer instances

Description

Unfolders provide a way to unfold data structures. They are basically Alternative instances, but the choose method allows the unfolder to do something special for the recursive positions of the data structure.

Synopsis

class Alternative f => Unfolder f where
chooseMonadDefault :: (Monad m, Unfolder m) => [m a] -> m a
chooseMapMonadDefault :: (Monad m, Unfolder m) => (a -> m b) -> [a] -> m b
between :: (Unfolder f, Enum a) => a -> a -> f a
betweenD :: (Unfolder f, Enum a) => a -> a -> f a
boundedEnum :: (Unfolder f, Bounded a, Enum a) => f a
boundedEnumD :: (Unfolder f, Bounded a, Enum a) => f a
newtype Random g m a = Random {
- getRandom :: StateT g m a
}
data Arb a = Arb Int (Gen (Maybe a))
arbUnit :: Arbitrary a => Arb a
newtype NumConst a x = NumConst {
- getNumConst :: a
}
data Nth a = Nth {
- size :: Integer
- getNth :: Integer -> a
}
class UnfolderTransformer t where
ala :: (UnfolderTransformer t, Unfolder f) => (t f b -> f b) -> (t f a -> t f b) -> f a -> f b
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
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
newtype DualA f a = DualA {
- getDualA :: f a
}
data NT f g = NT {
- getNT :: forall a. f a -> g a
}
newtype WithRec f a = WithRec {
- getWithRec :: ReaderT (Int -> NT f f) f a
}
withRec :: (Int -> NT f f) -> WithRec f a -> f a
limitDepth :: Unfolder f => Int -> WithRec f a -> f a
newtype BFS f x = BFS {
- getBFS :: (Int, Split) -> Maybe [f x]
}
type Split = Int -> [(Int, Int)]
bfs :: Unfolder f => BFS f x -> f x
bfsBySum :: Unfolder f => BFS f x -> f x

Unfolder

class Alternative f => Unfolder f where #

Unfolders provide a way to unfold data structures. The methods have default implementations in terms of Alternative, but you can implement chooseMap to act on recursive positions of the data structure, or simply to provide a faster implementation than 'foldr ((|) . f) empty'.

Methods

choose :: [f a] -> f a #

Choose one of the values from the list.

chooseMap :: (a -> f b) -> [a] -> f b #

Choose one of the values from the list and apply the given function.

chooseInt :: Int -> f Int #

Given a number n, return a number between '0' and 'n - 1'.

Instances

Unfolder [] #	Don't choose but return all items.
Instance details Defined in Data.Unfolder Methods choose :: [[a]] -> [a] # chooseMap :: (a -> [b]) -> [a] -> [b] # chooseInt :: Int -> [Int] #
Unfolder Maybe #	Always choose the first item.
Instance details Defined in Data.Unfolder Methods choose :: [Maybe a] -> Maybe a # chooseMap :: (a -> Maybe b) -> [a] -> Maybe b # chooseInt :: Int -> Maybe Int #
Unfolder Seq #	Don't choose but return all items.
Instance details Defined in Data.Unfolder Methods choose :: [Seq a] -> Seq a # chooseMap :: (a -> Seq b) -> [a] -> Seq b # chooseInt :: Int -> Seq Int #
Unfolder Arb #	Limit the depth of the generated data structure by dividing the given size by the number of recursive positions.
Instance details Defined in Data.Unfolder Methods choose :: [Arb a] -> Arb a # chooseMap :: (a -> Arb b) -> [a] -> Arb b # chooseInt :: Int -> Arb Int #
Unfolder Nth #
Instance details Defined in Data.Unfolder Methods choose :: [Nth a] -> Nth a # chooseMap :: (a -> Nth b) -> [a] -> Nth b # chooseInt :: Int -> Nth Int #
MonadPlus m => Unfolder (WrappedMonad m) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [WrappedMonad m a] -> WrappedMonad m a # chooseMap :: (a -> WrappedMonad m b) -> [a] -> WrappedMonad m b # chooseInt :: Int -> WrappedMonad m Int #
Unfolder f => Unfolder (Lift f) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [Lift f a] -> Lift f a # chooseMap :: (a -> Lift f b) -> [a] -> Lift f b # chooseInt :: Int -> Lift f Int #
(Functor m, Monad m) => Unfolder (MaybeT m) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [MaybeT m a] -> MaybeT m a # chooseMap :: (a -> MaybeT m b) -> [a] -> MaybeT m b # chooseInt :: Int -> MaybeT m Int #
Applicative f => Unfolder (ListT f) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [ListT f a] -> ListT f a # chooseMap :: (a -> ListT f b) -> [a] -> ListT f b # chooseInt :: Int -> ListT f Int #
Num a => Unfolder (NumConst a) #	Unfolds to a constant numeric value. Useful for counting shapes.
Instance details Defined in Data.Unfolder Methods choose :: [NumConst a a0] -> NumConst a a0 # chooseMap :: (a0 -> NumConst a b) -> [a0] -> NumConst a b # chooseInt :: Int -> NumConst a Int #
Applicative f => Unfolder (BFS f) #	Choose between values of a given depth only.
Instance details Defined in Data.Unfolder Methods choose :: [BFS f a] -> BFS f a # chooseMap :: (a -> BFS f b) -> [a] -> BFS f b # chooseInt :: Int -> BFS f Int #
Unfolder f => Unfolder (WithRec f) #	Applies a certain function depending on the depth at every recursive position.
Instance details Defined in Data.Unfolder Methods choose :: [WithRec f a] -> WithRec f a # chooseMap :: (a -> WithRec f b) -> [a] -> WithRec f b # chooseInt :: Int -> WithRec f Int #
Unfolder f => Unfolder (DualA f) #	Reverse the list passed to choose.
Instance details Defined in Data.Unfolder Methods choose :: [DualA f a] -> DualA f a # chooseMap :: (a -> DualA f b) -> [a] -> DualA f b # chooseInt :: Int -> DualA f Int #
(ArrowZero a, ArrowPlus a) => Unfolder (WrappedArrow a b) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [WrappedArrow a b a0] -> WrappedArrow a b a0 # chooseMap :: (a0 -> WrappedArrow a b b0) -> [a0] -> WrappedArrow a b b0 # chooseInt :: Int -> WrappedArrow a b Int #
Unfolder f => Unfolder (Reverse f) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [Reverse f a] -> Reverse f a # chooseMap :: (a -> Reverse f b) -> [a] -> Reverse f b # chooseInt :: Int -> Reverse f Int #
(Monoid w, Unfolder m) => Unfolder (WriterT w m) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [WriterT w m a] -> WriterT w m a # chooseMap :: (a -> WriterT w m b) -> [a] -> WriterT w m b # chooseInt :: Int -> WriterT w m Int #
(MonadPlus m, Unfolder m) => Unfolder (StateT s m) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [StateT s m a] -> StateT s m a # chooseMap :: (a -> StateT s m b) -> [a] -> StateT s m b # chooseInt :: Int -> StateT s m Int #
(Functor m, Monad m, Monoid e) => Unfolder (ExceptT e m) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [ExceptT e m a] -> ExceptT e m a # chooseMap :: (a -> ExceptT e m b) -> [a] -> ExceptT e m b # chooseInt :: Int -> ExceptT e m Int #
Unfolder f => Unfolder (Backwards f) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [Backwards f a] -> Backwards f a # chooseMap :: (a -> Backwards f b) -> [a] -> Backwards f b # chooseInt :: Int -> Backwards f Int #
(Functor m, Monad m, RandomGen g) => Unfolder (Random g m) #	Choose randomly.
Instance details Defined in Data.Unfolder Methods choose :: [Random g m a] -> Random g m a # chooseMap :: (a -> Random g m b) -> [a] -> Random g m b # chooseInt :: Int -> Random g m Int #
(Unfolder p, Unfolder q) => Unfolder (Product p q) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [Product p q a] -> Product p q a # chooseMap :: (a -> Product p q b) -> [a] -> Product p q b # chooseInt :: Int -> Product p q Int #
Unfolder m => Unfolder (ReaderT r m) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [ReaderT r m a] -> ReaderT r m a # chooseMap :: (a -> ReaderT r m b) -> [a] -> ReaderT r m b # chooseInt :: Int -> ReaderT r m Int #
(Unfolder p, Applicative q) => Unfolder (Compose p q) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [Compose p q a] -> Compose p q a # chooseMap :: (a -> Compose p q b) -> [a] -> Compose p q b # chooseInt :: Int -> Compose p q Int #
(Monoid w, MonadPlus m, Unfolder m) => Unfolder (RWST r w s m) #	Derived instance.
Instance details Defined in Data.Unfolder Methods choose :: [RWST r w s m a] -> RWST r w s m a # chooseMap :: (a -> RWST r w s m b) -> [a] -> RWST r w s m b # chooseInt :: Int -> RWST r w s m Int #

chooseMonadDefault :: (Monad m, Unfolder m) => [m a] -> m a #

If an unfolder is monadic, choose can be implemented in terms of chooseInt.

chooseMapMonadDefault :: (Monad m, Unfolder m) => (a -> m b) -> [a] -> m b #

If an unfolder is monadic, chooseMap can be implemented in terms of chooseInt.

between :: (Unfolder f, Enum a) => a -> a -> f a #

If a datatype is enumerable, we can use chooseInt to generate a value. This is the function to use if you want to unfold a datatype that has no type arguments (has kind *).

betweenD :: (Unfolder f, Enum a) => a -> a -> f a #

betweenD uses choose 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.

boundedEnum :: (Unfolder f, Bounded a, Enum a) => f a #

If a datatype is also bounded, we can choose between all possible values.

boundedEnum = between minBound maxBound

boundedEnumD :: (Unfolder f, Bounded a, Enum a) => f a #

boundedEnumD = betweenD minBound maxBound

Unfolder instances

newtype Random g m a #

Constructors

Random
Fields getRandom :: StateT g m a

Instances

Monad m => Monad (Random g m) #
Instance details Defined in Data.Unfolder Methods (>>=) :: Random g m a -> (a -> Random g m b) -> Random g m b # (>>) :: Random g m a -> Random g m b -> Random g m b # return :: a -> Random g m a # fail :: String -> Random g m a #
Functor m => Functor (Random g m) #
Instance details Defined in Data.Unfolder Methods fmap :: (a -> b) -> Random g m a -> Random g m b # (<$) :: a -> Random g m b -> Random g m a #
Monad m => Applicative (Random g m) #
Instance details Defined in Data.Unfolder Methods pure :: a -> Random g m a # (<>) :: Random g m (a -> b) -> Random g m a -> Random g m b # liftA2 :: (a -> b -> c) -> Random g m a -> Random g m b -> Random g m c # (>) :: Random g m a -> Random g m b -> Random g m b # (<*) :: Random g m a -> Random g m b -> Random g m a #
(Functor m, Monad m, RandomGen g) => Alternative (Random g m) #
Instance details Defined in Data.Unfolder Methods empty :: Random g m a # (<\|>) :: Random g m a -> Random g m a -> Random g m a # some :: Random g m a -> Random g m [a] # many :: Random g m a -> Random g m [a] #
(Functor m, Monad m, RandomGen g) => MonadPlus (Random g m) #
Instance details Defined in Data.Unfolder Methods mzero :: Random g m a # mplus :: Random g m a -> Random g m a -> Random g m a #
(Functor m, Monad m, RandomGen g) => Unfolder (Random g m) #	Choose randomly.
Instance details Defined in Data.Unfolder Methods choose :: [Random g m a] -> Random g m a # chooseMap :: (a -> Random g m b) -> [a] -> Random g m b # chooseInt :: Int -> Random g m Int #

data Arb a #

A variant of Test.QuickCheck.Gen, with failure and a count of the number of recursive positions.

Constructors

Arb Int (Gen (Maybe a))

Instances

Functor Arb #
Instance details Defined in Data.Unfolder Methods fmap :: (a -> b) -> Arb a -> Arb b # (<$) :: a -> Arb b -> Arb a #
Applicative Arb #
Instance details Defined in Data.Unfolder Methods pure :: a -> Arb a # (<>) :: Arb (a -> b) -> Arb a -> Arb b # liftA2 :: (a -> b -> c) -> Arb a -> Arb b -> Arb c # (>) :: Arb a -> Arb b -> Arb b # (<*) :: Arb a -> Arb b -> Arb a #
Alternative Arb #
Instance details Defined in Data.Unfolder Methods empty :: Arb a # (<\|>) :: Arb a -> Arb a -> Arb a # some :: Arb a -> Arb [a] # many :: Arb a -> Arb [a] #
Unfolder Arb #	Limit the depth of the generated data structure by dividing the given size by the number of recursive positions.
Instance details Defined in Data.Unfolder Methods choose :: [Arb a] -> Arb a # chooseMap :: (a -> Arb b) -> [a] -> Arb b # chooseInt :: Int -> Arb Int #

arbUnit :: Arbitrary a => Arb a #

newtype NumConst a x #

Variant of Constant that does multiplication of the constants for <*> and addition for <|>.

Constructors

NumConst
Fields getNumConst :: a

Instances

Functor (NumConst a) #
Instance details Defined in Data.Unfolder Methods fmap :: (a0 -> b) -> NumConst a a0 -> NumConst a b # (<$) :: a0 -> NumConst a b -> NumConst a a0 #
Num a => Applicative (NumConst a) #
Instance details Defined in Data.Unfolder Methods pure :: a0 -> NumConst a a0 # (<>) :: NumConst a (a0 -> b) -> NumConst a a0 -> NumConst a b # liftA2 :: (a0 -> b -> c) -> NumConst a a0 -> NumConst a b -> NumConst a c # (>) :: NumConst a a0 -> NumConst a b -> NumConst a b # (<*) :: NumConst a a0 -> NumConst a b -> NumConst a a0 #
Num a => Alternative (NumConst a) #
Instance details Defined in Data.Unfolder Methods empty :: NumConst a a0 # (<\|>) :: NumConst a a0 -> NumConst a a0 -> NumConst a a0 # some :: NumConst a a0 -> NumConst a [a0] # many :: NumConst a a0 -> NumConst a [a0] #
Num a => Unfolder (NumConst a) #	Unfolds to a constant numeric value. Useful for counting shapes.
Instance details Defined in Data.Unfolder Methods choose :: [NumConst a a0] -> NumConst a a0 # chooseMap :: (a0 -> NumConst a b) -> [a0] -> NumConst a b # chooseInt :: Int -> NumConst a Int #
Eq a => Eq (NumConst a x) #
Instance details Defined in Data.Unfolder Methods (==) :: NumConst a x -> NumConst a x -> Bool # (/=) :: NumConst a x -> NumConst a x -> Bool #
Show a => Show (NumConst a x) #
Instance details Defined in Data.Unfolder Methods showsPrec :: Int -> NumConst a x -> ShowS # show :: NumConst a x -> String # showList :: [NumConst a x] -> ShowS #

data Nth a #

Constructors

Nth
Fields size :: Integer getNth :: Integer -> a

Instances

Functor Nth #
Instance details Defined in Data.Unfolder Methods fmap :: (a -> b) -> Nth a -> Nth b # (<$) :: a -> Nth b -> Nth a #
Applicative Nth #
Instance details Defined in Data.Unfolder Methods pure :: a -> Nth a # (<>) :: Nth (a -> b) -> Nth a -> Nth b # liftA2 :: (a -> b -> c) -> Nth a -> Nth b -> Nth c # (>) :: Nth a -> Nth b -> Nth b # (<*) :: Nth a -> Nth b -> Nth a #
Alternative Nth #
Instance details Defined in Data.Unfolder Methods empty :: Nth a # (<\|>) :: Nth a -> Nth a -> Nth a # some :: Nth a -> Nth [a] # many :: Nth a -> Nth [a] #
Unfolder Nth #
Instance details Defined in Data.Unfolder Methods choose :: [Nth a] -> Nth a # chooseMap :: (a -> Nth b) -> [a] -> Nth b # chooseInt :: Int -> Nth Int #

UnfolderTransformer

class UnfolderTransformer t where #

An UnfolderTransformer changes the way an Unfolder unfolds.

Minimal complete definition

lift

Methods

lift :: Unfolder f => f a -> t f a #

Lift a computation from the argument unfolder to the constructed unfolder.

Instances

UnfolderTransformer BFS #
Instance details Defined in Data.Unfolder Methods lift :: Unfolder f => f a -> BFS f a #
UnfolderTransformer WithRec #
Instance details Defined in Data.Unfolder Methods lift :: Unfolder f => f a -> WithRec f a #
UnfolderTransformer DualA #
Instance details Defined in Data.Unfolder Methods lift :: Unfolder f => f a -> DualA f a #

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 one argument using an UnfolderTransformer, 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 two arguments using an UnfolderTransformer, 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 #

Run an unfolding function with three arguments using an UnfolderTransformer, given a way to run the transformer.

UnfolderTransformer instances

newtype DualA f a #

DualA flips the <|> operator from Alternative.

Constructors

DualA
Fields getDualA :: f a

Instances

UnfolderTransformer DualA #
Instance details Defined in Data.Unfolder Methods lift :: Unfolder f => f a -> DualA f a #
Functor f => Functor (DualA f) #
Instance details Defined in Data.Unfolder Methods fmap :: (a -> b) -> DualA f a -> DualA f b # (<$) :: a -> DualA f b -> DualA f a #
Applicative f => Applicative (DualA f) #
Instance details Defined in Data.Unfolder Methods pure :: a -> DualA f a # (<>) :: DualA f (a -> b) -> DualA f a -> DualA f b # liftA2 :: (a -> b -> c) -> DualA f a -> DualA f b -> DualA f c # (>) :: DualA f a -> DualA f b -> DualA f b # (<*) :: DualA f a -> DualA f b -> DualA f a #
Alternative f => Alternative (DualA f) #
Instance details Defined in Data.Unfolder Methods empty :: DualA f a # (<\|>) :: DualA f a -> DualA f a -> DualA f a # some :: DualA f a -> DualA f [a] # many :: DualA f a -> DualA f [a] #
Unfolder f => Unfolder (DualA f) #	Reverse the list passed to choose.
Instance details Defined in Data.Unfolder Methods choose :: [DualA f a] -> DualA f a # chooseMap :: (a -> DualA f b) -> [a] -> DualA f b # chooseInt :: Int -> DualA f Int #
Eq (f a) => Eq (DualA f a) #
Instance details Defined in Data.Unfolder Methods (==) :: DualA f a -> DualA f a -> Bool # (/=) :: DualA f a -> DualA f a -> Bool #
Show (f a) => Show (DualA f a) #
Instance details Defined in Data.Unfolder Methods showsPrec :: Int -> DualA f a -> ShowS # show :: DualA f a -> String # showList :: [DualA f a] -> ShowS #

data NT f g #

Natural transformations

Constructors

NT
Fields getNT :: forall a. f a -> g a

newtype WithRec f a #

Constructors

WithRec
Fields getWithRec :: ReaderT (Int -> NT f f) f a

Instances

UnfolderTransformer WithRec #
Instance details Defined in Data.Unfolder Methods lift :: Unfolder f => f a -> WithRec f a #
Functor f => Functor (WithRec f) #
Instance details Defined in Data.Unfolder Methods fmap :: (a -> b) -> WithRec f a -> WithRec f b # (<$) :: a -> WithRec f b -> WithRec f a #
Applicative f => Applicative (WithRec f) #
Instance details Defined in Data.Unfolder Methods pure :: a -> WithRec f a # (<>) :: WithRec f (a -> b) -> WithRec f a -> WithRec f b # liftA2 :: (a -> b -> c) -> WithRec f a -> WithRec f b -> WithRec f c # (>) :: WithRec f a -> WithRec f b -> WithRec f b # (<*) :: WithRec f a -> WithRec f b -> WithRec f a #
Alternative f => Alternative (WithRec f) #
Instance details Defined in Data.Unfolder Methods empty :: WithRec f a # (<\|>) :: WithRec f a -> WithRec f a -> WithRec f a # some :: WithRec f a -> WithRec f [a] # many :: WithRec f a -> WithRec f [a] #
Unfolder f => Unfolder (WithRec f) #	Applies a certain function depending on the depth at every recursive position.
Instance details Defined in Data.Unfolder Methods choose :: [WithRec f a] -> WithRec f a # chooseMap :: (a -> WithRec f b) -> [a] -> WithRec f b # chooseInt :: Int -> WithRec f Int #

withRec :: (Int -> NT f f) -> WithRec f a -> f a #

Apply a certain function of type f a -> f a to the result of a choose. The depth is passed as Int, so you can apply a different function at each depth. Because of a forall, the function needs to be wrapped in a NT constructor. See limitDepth for an example how to use this function.

limitDepth :: Unfolder f => Int -> WithRec f a -> f a #

Limit the depth of an unfolding.

newtype BFS f x #

Return a generator of values of a given depth. Returns Nothing if there are no values of that depth or deeper. The depth is the number of choose calls.

Constructors

BFS
Fields getBFS :: (Int, Split) -> Maybe [f x]

Instances

UnfolderTransformer BFS #
Instance details Defined in Data.Unfolder Methods lift :: Unfolder f => f a -> BFS f a #
Functor f => Functor (BFS f) #
Instance details Defined in Data.Unfolder Methods fmap :: (a -> b) -> BFS f a -> BFS f b # (<$) :: a -> BFS f b -> BFS f a #
Applicative f => Applicative (BFS f) #
Instance details Defined in Data.Unfolder Methods pure :: a -> BFS f a # (<>) :: BFS f (a -> b) -> BFS f a -> BFS f b # liftA2 :: (a -> b -> c) -> BFS f a -> BFS f b -> BFS f c # (>) :: BFS f a -> BFS f b -> BFS f b # (<*) :: BFS f a -> BFS f b -> BFS f a #
Applicative f => Alternative (BFS f) #
Instance details Defined in Data.Unfolder Methods empty :: BFS f a # (<\|>) :: BFS f a -> BFS f a -> BFS f a # some :: BFS f a -> BFS f [a] # many :: BFS f a -> BFS f [a] #
Applicative f => Unfolder (BFS f) #	Choose between values of a given depth only.
Instance details Defined in Data.Unfolder Methods choose :: [BFS f a] -> BFS f a # chooseMap :: (a -> BFS f b) -> [a] -> BFS f b # chooseInt :: Int -> BFS f Int #

type Split = Int -> [(Int, Int)] #

bfs :: Unfolder f => BFS f x -> f x #

Change the order of unfolding to be breadth-first, by maximum depth of the components.

bfsBySum :: Unfolder f => BFS f x -> f x #

Change the order of unfolding to be breadth-first, by the sum of depths of the components.