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


-- | Functor combinators with tries & zippers
--   
--   Simple functor combinators, their derivatives, and their use for tries
--   Maybe split out derivatives and/or tries later.
@package functor-combo
@version 0.3


-- | Regular data types
module FunctorCombo.Regular
class Functor (PF t) => Regular t where type family PF t :: * -> *
wrap :: Regular t => PF t t -> t
unwrap :: Regular t => t -> PF t t


-- | Standard building blocks for functors
module FunctorCombo.Functor
newtype Const a b :: * -> * -> *
Const :: a -> Const a b
getConst :: Const a b -> a

-- | Empty/zero type constructor (no inhabitants)
data Void a
voidF :: Void a -> b

-- | Unit type constructor (one inhabitant)
type Unit = Const ()

-- | The unit value
unit :: Unit ()

-- | Identity type constructor. Until there's a better place to find it.
--   I'd use <a>Control.Monad.Identity</a>, but I don't want to introduce a
--   dependency on mtl just for Id.
newtype Id a :: * -> *
Id :: a -> Id a
unId :: Id a -> a
inId :: (a -> b) -> Id a -> Id b
inId2 :: (a -> b -> c) -> Id a -> Id b -> Id c

-- | Sum on unary type constructors
data (:+:) f g a
InL :: (f a) -> :+: f g a
InR :: (g a) -> :+: f g a
eitherF :: (f a -> b) -> (g a -> b) -> (f :+: g) a -> b

-- | Product on unary type constructors
data (:*:) f g a
(:*:) :: f a -> g a -> :*: f g a
asProd :: (f a, g a) -> (f :*: g) a
asPair :: (f :*: g) a -> (f a, g a)

-- | Like <a>fst</a>
fstF :: (f :*: g) a -> f a

-- | Like <a>snd</a>
sndF :: (f :*: g) a -> g a

-- | Composition of unary type constructors
--   
--   There are (at least) two useful <a>Monoid</a> instances, so you'll
--   have to pick one and type-specialize it (filling in all or parts of
--   <tt>g</tt> and/or <tt>f</tt>).
--   
--   <pre>
--   -- standard Monoid instance for Applicative applied to Monoid
--   instance (Applicative (g :. f), Monoid a) =&gt; Monoid ((g :. f) a) where
--     { mempty = pure mempty; mappend = liftA2 mappend }
--   -- Especially handy when g is a Monoid_f.
--   instance Monoid (g (f a)) =&gt; Monoid ((g :. f) a) where
--     { mempty = O mempty; mappend = inO2 mappend }
--   </pre>
--   
--   Corresponding to the first and second definitions above,
--   
--   <pre>
--   instance (Applicative g, Monoid_f f) =&gt; Monoid_f (g :. f) where
--     { mempty_f = O (pure mempty_f); mappend_f = inO2 (liftA2 mappend_f) }
--   instance Monoid_f g =&gt; Monoid_f (g :. f) where
--     { mempty_f = O mempty_f; mappend_f = inO2 mappend_f }
--   </pre>
--   
--   Similarly, there are two useful <a>Functor</a> instances and two
--   useful <a>ContraFunctor</a> instances.
--   
--   <pre>
--   instance (      Functor g,       Functor f) =&gt; Functor (g :. f) where fmap = fmapFF
--   instance (ContraFunctor g, ContraFunctor f) =&gt; Functor (g :. f) where fmap = fmapCC
--   
--   instance (      Functor g, ContraFunctor f) =&gt; ContraFunctor (g :. f) where contraFmap = contraFmapFC
--   instance (ContraFunctor g,       Functor f) =&gt; ContraFunctor (g :. f) where contraFmap = contraFmapCF
--   </pre>
--   
--   However, it's such a bother to define the Functor instances per
--   composition type, I've left the fmapFF case in. If you want the fmapCC
--   one, you're out of luck for now. I'd love to hear a good solution.
--   Maybe someday Haskell will do Prolog-style search for instances,
--   subgoaling the constraints, rather than just matching instance heads.
newtype (:.) (g :: * -> *) (f :: * -> *) a :: (* -> *) -> (* -> *) -> * -> *
O :: g (f a) -> :. a

-- | Unwrap a '(:.)'.
unO :: :. g f a -> g (f a)

-- | Apply a unary function within the <a>O</a> constructor.
inO :: (g (f a) -> g' (f' a')) -> :. g f a -> :. g' f' a'

-- | Apply a binary function within the <a>O</a> constructor.
inO2 :: (g (f a) -> g' (f' a') -> g'' (f'' a'')) -> :. g f a -> :. g' f' a' -> :. g'' f'' a''

-- | Add pre- and post processing
(~>) :: Category cat => cat a' a -> cat b b' -> cat a b -> cat a' b'
(<~) :: Category cat => cat b b' -> cat a' a -> cat a b -> cat a' b'

-- | Add a bottom to a type
data Lift a
Lift :: a -> Lift a
unLift :: Lift a -> a

-- | Strict product functor
data (:*:!) f g a
(:*:!) :: !(f a) -> !(g a) -> :*:! f g a

-- | Strict sum functor
data (:+:!) f g a
InL' :: !(f a) -> :+:! f g a
InR' :: !(g a) -> :+:! f g a

-- | Case analysis on strict sum functor
eitherF' :: (f a -> c) -> (g a -> c) -> ((f :+:! g) a -> c)
pairF :: (f a, g a) -> (f :*: g) a
unPairF :: (f :*: g) a -> (f a, g a)
inProd :: ((f a, g a) -> (h b, i b)) -> ((f :*: g) a -> (h :*: i) b)
inProd2 :: ((f a, g a) -> (h b, i b) -> (j c, k c)) -> ((f :*: g) a -> (h :*: i) b -> (j :*: k) c)
class EncodeF f where type family Enc f :: * -> *
encode :: EncodeF f => f a -> Enc f a
decode :: EncodeF f => Enc f a -> f a
instance Traversable (Const b)
instance Foldable (Const b)
instance (Show (f a), Show (g a)) => Show ((:*:) f g a)
instance (Functor f, Functor g) => Functor (f :*: g)
instance (Show (f a), Show (g a)) => Show ((:+:) f g a)
instance (Functor f, Functor g) => Functor (f :+: g)
instance Functor Lift
instance (Functor f, Functor g) => Functor (f :*:! g)
instance (Functor f, Functor g) => Functor (f :+:! g)
instance (Traversable f, Traversable g) => Traversable (f :*: g)
instance (Foldable f, Foldable g) => Foldable (f :*: g)
instance (Functor f, Functor g, Monad f, Monad g) => Monad (f :*: g)
instance (Applicative f, Applicative g) => Applicative (f :*: g)
instance (Traversable f, Traversable g) => Traversable (f :+: g)
instance (Foldable f, Foldable g) => Foldable (f :+: g)
instance Functor Void


-- | Composable parallel scanning from
--   <a>http://conal.net/blog/posts/composable-parallel-scanning/</a>
module FunctorCombo.ParScan

-- | Parallel scans. <a>prefixScan</a> accumulates moving left-to-right,
--   while <a>suffixScan</a> accumulates moving right-to-left.
class Scan f
prefixScan :: (Scan f, Monoid m) => f m -> PreScanO f m
suffixScan :: (Scan f, Monoid m) => f m -> SufScanO f m
type PreScanO f a = (f a, a)
type SufScanO f a = (a, f a)
prefixScanEnc :: (EncodeF f, Scan (Enc f), Monoid m) => f m -> PreScanO f m
suffixScanEnc :: (EncodeF f, Scan (Enc f), Monoid m) => f m -> SufScanO f m
preScanTweak :: Functor f => (a -> b) -> PreScanO f a -> PreScanO f b
sufScanTweak :: Functor f => (a -> b) -> SufScanO f a -> SufScanO f b
prefixSums :: (Functor f, Scan f, Num a) => f a -> PreScanO f a
suffixSums :: (Functor f, Scan f, Num a) => f a -> SufScanO f a
instance (Scan g, Scan f, Functor f, Applicative g) => Scan (g :. f)
instance (Scan f, Scan g, Functor f, Functor g) => Scan (f :*: g)
instance (Scan f, Scan g) => Scan (f :+: g)
instance Scan Id
instance Scan (Const x)


-- | Pair functor
module FunctorCombo.Pair

-- | Uniform pairs
data Pair a
(:#) :: a -> a -> Pair a
fstP :: Pair a -> a
sndP :: Pair a -> a
swapP :: Unop (Pair a)
fromP :: Pair a -> (a, a)
toP :: (a, a) -> Pair a
inP :: Unop (a, a) -> Unop (Pair a)
firstP :: Unop a -> Unop (Pair a)
secondP :: Unop a -> Unop (Pair a)
zipA :: Applicative f => Pair (f a) -> f (Pair a)
unzipA :: Functor f => f (Pair a) -> Pair (f a)
inZipA :: Applicative f => Unop (f (Pair a)) -> Unop (Pair (f a))
curryP :: (Pair a -> b) -> (a -> a -> b)
uncurryP :: (a -> a -> b) -> (Pair a -> b)
preScanP :: (Functor f, Monoid o) => Pair (f o, o) -> (Pair (f o), o)
sufScanP :: (Functor f, Monoid o) => Pair (o, f o) -> (o, Pair (f o))
instance Functor Pair
instance Eq a => Eq (Pair a)
instance Show a => Show (Pair a)
instance Scan Pair
instance EncodeF Pair
instance Traversable Pair
instance Monad Pair
instance Applicative Pair
instance Foldable Pair


-- | Least upper bounds for functor combinators
module FunctorCombo.LubF
class HasLubF f
instance (HasLubF f, HasLubF g) => HasLubF (f :*: g)
instance HasLubF Id


-- | Derivatives (one-hole contexts) for standard Functor combinators
module FunctorCombo.Derivative

-- | A derivative, i.e., a one-hole context for a container f (probably a
--   functor).


-- | Filling and extracting derivatives (one-hole contexts)
module FunctorCombo.Holey

-- | Location, i.e., one-hole context and a value for the hole.
type Loc f a = (Der f a, a)

-- | Filling and creating one-hole contexts
class Functor f => Holey f
fillC :: Holey f => Der f a -> a -> f a
extract :: Holey f => f a -> f (Loc f a)

-- | Alternative interface for <a>fillC</a>.
fill :: Holey f => Loc f a -> f a
instance (Holey f, Holey g) => Holey (g :. f)
instance (Holey f, Holey g) => Holey (f :*: g)
instance (Holey f, Holey g) => Holey (f :+: g)
instance Holey Id
instance Holey (Const z)


-- | Filling and extracting derivatives (one-hole contexts)
module FunctorCombo.DHoley
class Functor f => Holey f where type family Der f :: * -> *
fillC :: Holey f => Der f a -> a -> f a
extract :: Holey f => f a -> f (Loc f a)

-- | Alternative interface for <a>fillC</a>.
fill :: Holey f => Loc f a -> f a
instance (Holey f, Holey g) => Holey (g :. f)
instance (Holey f, Holey g) => Holey (f :*: g)
instance (Holey f, Holey g) => Holey (f :+: g)
instance Holey Id
instance Holey (Const x)


-- | Zippers for functor fixpoints
module FunctorCombo.ZipperFix

-- | Context for functor fixpoints
--   
--   Context for a regular type
type Context f = [Der f (Fix f)]

-- | Zipper for a functor tree. Also called "location"
type Zipper f = (Context f, Fix f)

-- | Move upward. Error if empty context.
up :: Holey f => Zipper f -> Zipper f

-- | Variant of <a>up</a>. <a>Nothing</a> if empty context.
up' :: Holey f => Zipper f -> Maybe (Zipper f)
down :: Holey f => Zipper f -> f (Zipper f)


module FunctorCombo.ZipperReg

-- | Context for a regular type
type Context t = [Der (PF t) t]

-- | Zipper for a regular type. Also called "location"
type Zipper t = (Context t, t)

-- | Move upward. Error if empty context.
up :: (Regular t, Holey (PF t)) => Zipper t -> Zipper t

-- | Variant of <a>up</a>. <a>Nothing</a> if empty context.
up' :: (Regular t, Holey (PF t)) => Zipper t -> Maybe (Zipper t)
down :: (Regular t, Holey (PF t)) => Zipper t -> PF t (Zipper t)


-- | Functor-based memo tries (strict for now)
module FunctorCombo.StrictMemo

-- | Domain types with associated memo tries
class Functor (Trie (k)) => HasTrie k where type family Trie k :: * -> *
trie :: HasTrie k => (k -> v) -> (k :->: v)
untrie :: HasTrie k => (k :->: v) -> (k -> v)

-- | Memo trie from k to v
type (:->:) k v = Trie k v

-- | Trie-based function memoizer
memo :: HasTrie k => Unop (k -> v)

-- | Memoize a binary function, on its first argument and then on its
--   second. Take care to exploit any partial evaluation.
memo2 :: (HasTrie s, HasTrie t) => Unop (s -> t -> a)

-- | Memoize a ternary function on successive arguments. Take care to
--   exploit any partial evaluation.
memo3 :: (HasTrie r, HasTrie s, HasTrie t) => Unop (r -> s -> t -> a)
idTrie :: HasTrie k => k :->: k
onUntrie :: (HasTrie a, HasTrie b) => ((a -> a') -> (b -> b')) -> ((a :->: a') -> (b :->: b'))
onUntrie2 :: (HasTrie a, HasTrie b, HasTrie c) => ((a -> a') -> (b -> b') -> (c -> c')) -> ((a :->: a') -> (b :->: b') -> (c :->: c'))
instance Functor (Trie a) => Functor (TreeTrie a)
instance Functor (Trie a) => Functor (ListTrie a)
instance Regular (Tree a)
instance Regular [a]
instance HasTrie a => HasTrie (Pair a)
instance (HasTrie a, HasTrie (a :->: b)) => HasTrie (a -> b)
instance HasTrie Integer
instance HasTrie Int
instance HasTrie (PF (Tree a) (Tree a) :->: v) => HasTrie (TreeTrie a v)
instance HasTrie a => HasTrie (Tree a)
instance HasTrie (PF [a] [a] :->: v) => HasTrie (ListTrie a v)
instance HasTrie a => HasTrie [a]
instance HasTrie (g (f a)) => HasTrie ((:.) g f a)
instance (HasTrie (f a), HasTrie (g a)) => HasTrie ((:+:) f g a)
instance (HasTrie (f a), HasTrie (g a)) => HasTrie ((:*:) f g a)
instance HasTrie a => HasTrie (Id a)
instance HasTrie x => HasTrie (Const x a)
instance (HasTrie a, HasTrie b, HasTrie c, HasTrie d) => HasTrie (a, b, c, d)
instance (HasTrie a, HasTrie b, HasTrie c) => HasTrie (a, b, c)
instance HasTrie Bool
instance (HasTrie a, HasTrie b) => HasTrie (a, b)
instance (HasTrie a, HasTrie b) => HasTrie (Either a b)
instance HasTrie ()


-- | Strict products and sums.Strict
module FunctorCombo.Strict

-- | Strict pair
data (:*!) a b
(:*!) :: !a -> !b -> :*! a b

-- | Curry on strict pairs
curry' :: (a :*! b -> c) -> (a -> b -> c)

-- | Uncurry on strict pairs
uncurry' :: (a -> b -> c) -> ((a :*! b) -> c)

-- | Strict sum
data (:+!) a b
Left' :: !a -> :+! a b
Right' :: !b -> :+! a b

-- | Case analysis for strict sums. Like <a>either</a>.
either' :: (a -> c) -> (b -> c) -> (a :+! b -> c)


-- | Functor-based memo tries. See
--   <a>http://conal.net/blog/posts/details-for-nonstrict-memoization-part-1/</a>
module FunctorCombo.NonstrictMemo

-- | Domain types with associated memo tries
class Functor (STrie (k)) => HasTrie k where type family STrie k :: * -> *
sTrie :: HasTrie k => (k -> v) -> (k :-> v)
sUntrie :: (HasTrie k, HasLub (v)) => (k :-> v) -> (k -> v)
type (:->:) k v = Trie k v

-- | Trie-based function memoizer
memo :: HasLub (v) => HasTrie k => Unop (k -> v)

-- | Memoize a binary function, on its first argument and then on its
--   second. Take care to exploit any partial evaluation.
memo2 :: HasLub (a) => (HasTrie s, HasTrie t) => Unop (s -> t -> a)

-- | Memoize a ternary function on successive arguments. Take care to
--   exploit any partial evaluation.
memo3 :: HasLub (a) => (HasTrie r, HasTrie s, HasTrie t) => Unop (r -> s -> t -> a)
instance Functor (STrie a) => Functor (ListSTrie a)
instance Functor (STrie k) => Functor (Trie k)
instance Regular (Tree a)
instance Regular [a]
instance (HasTrie a, HasTrie (a :->: b), HasLub b) => HasTrie (a -> b)
instance HasTrie Integer
instance HasTrie Int
instance HasTrie a => HasTrie [a]
instance (HasTrie (f a), HasTrie (g a)) => HasTrie ((:+:!) f g a)
instance (HasTrie (f a), HasTrie (g a)) => HasTrie ((:*:!) f g a)
instance HasTrie (g (f a)) => HasTrie ((:.) g f a)
instance (HasTrie (f a), HasTrie (g a)) => HasTrie ((:+:) f g a)
instance (HasTrie (f a), HasTrie (g a)) => HasTrie ((:*:) f g a)
instance HasTrie a => HasTrie (Id a)
instance HasTrie x => HasTrie (Const x a)
instance (HasTrie a, HasTrie b, HasTrie c, HasTrie d) => HasTrie (a, b, c, d)
instance (HasTrie a, HasTrie b, HasTrie c) => HasTrie (a, b, c)
instance HasTrie Bool
instance HasTrie a => HasTrie (Lift a)
instance (HasTrie a, HasTrie b) => HasTrie (a :*! b)
instance (HasTrie a, HasTrie b) => HasTrie (a :+! b)
instance (HasTrie a, HasTrie b) => HasTrie (a, b)
instance (HasTrie a, HasTrie b) => HasTrie (Either a b)
instance HasTrie ()